ablass at umich.edu
Thu Feb 23 10:26:11 EST 2006
Harvey Friedman quotes:
> For instance, one may use information about the topological and
> structure of beta(N) to conclude the following: If N is partitioned
> finitely many classes, one cell of the partition will contain each of
> (i) Arithmetic progressions of every finite length.
> (ii) Geometric progressions of every finite length.
> (iii) An infinite set A and every finite sum with distinct summands
> from A.
> (iv) An infinite set B and every finite product with distinct factors
and then asks (among other things):
> What about ii-iv? Have they been proved with similar explicitness?
> What would be involved in trying to eliminate the use of beta(N) in
> Is there a down to earth treatment?
An explicit proof of (i) immediately gives an explicit proof of (ii),
because the function "x maps to 2^x" sends arithmetic progressions to
geometric ones. The bounds one gets this way for the associated finite
versions will be exponentially worse for (ii) than for (i). I don't
know whether one can do better for (ii). (Nor do I know whether the
bounds for (i) are already so big that I wouldn't worry about one more
Hindman's original proof of (iii) can be formalized in the theory
ACA_0^+, which is like ACA_0 except that, instead of asserting the
existence of the Turing jump of each set (and therefore finitely
iterated Turing jumps), it asserts the existence of the omega-iterated
Turing jump of each set. This is in a joint paper of Jeff Hirst, Steve
Simpson, and me ("Logical analysis of some theorems of combinatorics
and topological dynamics," in "Logic and Combinatorics", Contemporary
Math. 65 (1987), edited by Steve Simpson.) My recollection is that the
proof of (iii) in ACA_0^+ was worked out by Jeff; Steve my have had a
hand in it too, but my contribution to that paper is disjoint from this
result. As far as I know, it remains an open question whether (iii)
can be proved in ACA_0.
Again, the 2^x idea lets you deduce (iv) from (iii).
Despite all this, I remain a great fan of beta(N), and I emphasize that
the proof of (iii) using beta(N) is far easier than the proof in
ACA_0^+. (Here "easy" refers to mathematics, not to the philosophical
effort of believing in beta(N).)
More information about the FOM