FOM: Re: comments on RT2 paper

Peter Cholak cholak at
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