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