[FOM] Exponentiation and Goedel's incompleteness theorems (II)

[d.isles@comcast.net]

In an earlier (April 3, 2004) mailing to FOM, I asked a question about exponentiation and the proof of the (first) Goedel incompleteness theorem. The replies I received have caused me to restate my question(s) in a way which, I hope, makes them clearer.

1. Suppose we represent the natural numbers NN either in (Robinson's) system Q or on a Turing machine tape as numerals NUM (i.e. using unary notation) and then proceed to Goedel number Turing machine  programs, tape expressions, etc. or logical expressions, derivations, etc. This can be done using:
a. exponentiation via decomposition into primes (as Kleene does in "Introduction to Metamathematics" or Enderton in "Introduction to Mathematical Logic"); or
b. a direct coding into place notation (for example, base 10). This route is followed by Boolos and Jeffrey in "Computability and Logic", Lewis and Papadamitriou in "Elements of the Theory of Computation", Nelson in "Predicative Arithjmetic"; or 
c. (for encoding Turing machines) a listing of Tuyring machines as in Roger's "Recursive Functions and Effective Computability". That is, Rogers takes as the Goedel number of a TM its location in some standard listing of all TMs (say as printed out by a computer.)

Now in order to carry out the arguments which show either the unsolvability of the Halting Problem or the underivability of the Goedel formula in Q, one must, in cases a and b, be able to claim that the exponential codes of logical expressions or of TMs are equal to (evaluate to) a natural number in NUMERAL FORM. In case c, you must be able to assert that the TM program of the "contradictory" TM has a location in the list. Since this location is denoted by a numeral (after all, one generates one after the other the various TM programs and tallies them) this is tantamounbt to claiming that the numerals are closed under exponentiation.

QUESTION 1: In these circumstances is it possible to avoid the assumption that the numerals are closed under exponentation? 

2. Suppose that you encode NN on TM tapes or in logical expressions by using, say, base 10 notation and that you Goedelize as in b above. Then it seems that you can prove the unsolvability of the Halting Problem or the incompleteness of Q  without running into the difficulty mentioned above. But now there seems to be a question of how you justify mathematical induction (n to n+1) over the set of base 10 notations ordered, as usual, lexicographically. It seems to me that to simply assert the validity of induction over this ordering is also to claim the closure of the numerals under exponentiation and, at the moment, I see no way of establishing this validity without sneaking in this assumption.

QUESTION 2: Is it possible to show that mathematical induction (n to n+1) is valid over the lexicographic ordering of base 10 notations without assuming that the numerals NUM are closed under exponentiation?

                                                                       David Isles