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

Ali Enayat enayat at american.edu
Sat Apr 3 12:57:33 EST 2004

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
is incomplete, essentially because Q weakly represents all recursive
Q does not prove the totality of the exponential function since Q is a weak
of the theory I-Delta_0 (also known as bounded arithmetic), whose provably
functions are dominated by polynomial functions (as a consequence of a
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

More information about the FOM mailing list