[FOM] Re: Exponentiation and Goedel's incompleteness theorems

[Ali Enayat]

This is a reply to D. Isle's question regarding the role of totality of the
exponential function in the proof of Goedel's first incompleteness theorem.

It is known that the finitely axiomatized theory Q (known as "Robinson's
arithmetic")
is incomplete, essentially because Q weakly represents all recursive
functions.
Q does not prove the totality of the exponential function since Q is a weak
fragment
of the theory I-Delta_0 (also known as bounded arithmetic), whose provably
total
functions are dominated by polynomial functions (as a consequence of a
classical
theorem of Rohit Parikh).

More impressively, the SECOND incompleteness theorem also can be proved for
Q, see:

A. Bezboruah, John C. Shepherdson
Godel's Second Incompleteness Theorem for Q. 503-512
Journal of Symbolic Logic, Volume 41 (1976)

I also recommend the following excellent text for related work:

Hajek, Petr, Pudlak, Pavel
Metamathematics of First-Order Arithmetic
Springer Verlag, December 1992
(Reprinted by Assn for Symbolic Logic, 1998)

*****************************************************************

Ali Enayat
Dept of Math/Stat
American University
Washington, DC 20016