FOM: Re: comments on RT2 paper

Rick Sommer sommer at Csli.Stanford.EDU
Fri Oct 23 13:37:40 EDT 1998


Peter Cholak asks:

   What I do not know is if a theory proves the Ackermann function is
   total must it show ISigma_2?  Clearly it is strongly than RCA_0 but
   how much strong must it be?

RCA_0 + "Ackermann's function is total" does not imply ISigma_2. A
statement that is provable in the latter, but not the former is:

  F_{\alpha} is total implies F_{alpha + \omega} is total

where F_{alpha} is the alpha-th function in the fast-growing
hierarchy. 

Note that the statement F_alpha is total is Pi^0_2; the theory
ISigma_n can be axiomatized by a single Pi^0_{n+2} sentence, and it
can be shown that, over RCA_0, there is no Pi^0_{n+1} sentence that
implies ISigma_n.

--Rick Sommer




More information about the FOM mailing list