[FOM] Exponentiation and Goedel's incompleteness theorems
d.isles at comcast.net
Fri Apr 2 09:21:09 EST 2004
I'd appreciate knowing whether it is possible to prove Goedel's "first" incompleteness theorem without making the assumption that
# the exponentiation function (or some function of "similar" growth rate) is total on the numerals (the natural numbers in unary notation?)
Let me clarify the question by referring to Theorem 28 on page 207 of Kleene's book "Introduction to Metamathematics" (1971) which states that if PA is (simply) consistent then (x)notBew(num(p),x) is not provable in PA. Here num(p) is the unary representation in PA of the Goedel number p of the formula (x)notBew(y,x). The proof consists in arguing that were this formula provable in PA then it would have a formal proof in PA which could then be encoded using an exponential expression e (based on the uniqueness of prime factorization; see section 52 in Kleene). Then making use of # we can conclude that e evaluates to a numeral num(e) and hence that Bew(num(p), num(e)) is provable in PA.
More information about the FOM