[FOM] Beta(N)

[Andreas Blass]

Harvey Friedman quotes:

> For instance, one may use information about the topological and 
> algebraic
> structure of beta(N) to conclude the following:  If N is partitioned 
> into
> finitely many classes, one cell of the partition will contain each of 
> the
> following:
>
> (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 
> ii)-iv)?
> 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 
exponential.)

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).)

Andreas Blass