FOM: Re: comments on RT2 paper

[Stephen G Simpson]

 > From: Peter Cholak <cholak at nd.edu>
 > 
 > I am very interested in Jeff's result that RT(2,<infinity) implies
 > the totality of the Ackermann function, over RCA_0.  I would like
 > to see it's proof.  Could Jeff's result be improved to RT(2,2)?
 > (See Question 13.2 in our paper.)

Actually, as Jeff Hirst pointed out in his thesis, totality of the
Ackermann function and many other multiply-recursive functions is
implied by Sigma^0_2 induction, which by Kirby-Paris is implied by
BPi^0_2, which by Hirst is implied by RT(2,<infinity).

>From the f.o.m. viewpoint, we could formulate it this way: The
strength of Ramsey's theorem for pairs goes far beyond finitism.

What about RT(2,2)?  Well, Hirst explicitly left this as an open
question in his thesis, and apparently it's still open (C-J-S Question
13.2).  Thus Hirst was apparently the first to explicitly raise the
possibility that RT(2,<infinity) and RT(2,2) might differ in logical
strength.  He didn't prove this at the time, 1987, but now it has been
proved, in the Cholak-Jockusch-Slaman paper.

Of course the Cholak-Jockusch-Slaman paper also contains many other
wonderful new results, e.g. that the logical strength of
RT(2,<infinity) is strictly and measurably less than that of PA.

-- Steve