[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
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
More information about the FOM
mailing list