FOM: Re: comments on RT2 paper
Peter Cholak
cholak at nd.edu
Fri Oct 23 10:41:07 EDT 1998
This makes sense. In fact, Stan Wainer and various others have a whole
sequence of results which show certain functions are provability total in
ISigma_n. I believe that they have an characterization of such functions.
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?
> 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).
More information about the FOM
mailing list