Does Godel's numbering system have to be so complex?

[andrewkirk]

This question is about two different ways of Godel numbering - assigning natural numbers to well-formed formulas in a formal language.

Godel uses an ingenious and complicated mapping involving Cantor's pairing function (which is a bijection between N and N x N) and the Chinese Remainder Theorem.

Douglas Hofstadter, in his book Godel Escher Bach, uses a much simpler mapping that is really just a transliteration. To every symbol in the formal language, he assignes a three digit code. Then the Godel number of a formula is just the number whose decimal representation is the string of numerals you get when you replace every symbol in the logical formula by its corresponding three digit code.

Hofstadter's map is much easier to understand, and trivial to implement - the Godel number for a formula can be written down in seconds. This contrasts with Godel's map, for which it took my brand new laptop 30 minutes to calculate the Godel number for the formula '0=0' (it's7,286,659, if we map the language symbols '0' and '=' to 0 and 1 respectively, in case anybody's interested).

Godel's map produces much smaller numbers, but that gives no practical advantage, as the numbers still become enormous very very quickly, and are usually impractical to calculate anyway.

Neither map is a surjection onto the natural numbers. Both are primitive recursive.

Both can be simply and naturally extended to map proofs to natural numbers.

So I wonder why Godel chose such a complex approach, rather than Hofstadter's simple and (to me) obvious one. This is made more intriguing by the fact that, in discussions of Godel's proof, I have seen the map he defined described as one of the most brilliant insights in it.

The only practical advantage of Godel's map over Hofstadter's that I can think of is that Godel's copes quite naturally with a language that has an infinite alphabet, which for instance allows for an unlimited number of different one-character symbols for variables, functions and predicates. Hofstadter's approach requires a finite alphabet - in fact his use of three-digit codes places a limit of 1,000 on the number of different characters that can be used.

However, I think the limitation of Hofstadter's map is easily overcome by using the prime character as many times as necessary, so that:
x, x', x'', x''', ... are names of different variables
f, f', f'', f''', ... are names of different functions
p, p', p'', p''', ... are names of different predicates

If that is correct then I am left perplexed as to why Godel chose such a complicated and confusing map. I am very impressed by his map. It would take a brilliantly creative mind to have thought of it. But I just can't see why he didn't take the simple route. Is there some flaw in or limitation of Hostadter's approach that I am missing?

 

[Preno]

Hofstadter's map is much easier to understand, and trivial to implement - the Godel number for a formula can be written down in seconds. This contrasts with Godel's map, for which it took my brand new laptop 30 minutes to calculate the Godel number for the formula '0=0' (it's7,286,659, if we map the language symbols '0' and '=' to 0 and 1 respectively, in case anybody's interested).

Godel's map produces much smaller numbers, but that gives no practical advantage, as the numbers still become enormous very very quickly, and are usually impractical to calculate anyway.

The purpose of Godel numbering is not to write down or calculate the Godel numbers of formulas, it's to allow us to prove things about them. The coding you suggest as an alternative does not work for this purpose for the simple reason that exponentiation (which you need in order to define it properly) is not prima facie expressible in the language of Peano Arithmetic, which consists of the constant 0, the unary function symbol S and two binary function symbols +,*. Once you have a way of coding finite sequences of numbers, it is quite easy to define exponentiation, but the point of Godel numbering is precisely that it allows us to talk about finite sequences of numbers. (Once you can do that, yes, it's absolutely immaterial which representation you choose, but Godel's numbering is simpler, as it is just a sequence of the numbers of the symbols, whereas to define the alternative numbering you suggest, you need to define exponentiation.)

Iow, what Godel shows in this part of the proof is essentially that you can use recursive definitions in PA.

Afaict, Hofstadter presents Godel's theorems in terms of some theory of strings he calls "TNT", not in terms of arithmetic. This circumvents the above difficulty, but then of course the challenge remains to show that you can interpret arithmetic in this theory.

 

[andrewkirk]

Iow, what Godel shows in this part of the proof is essentially that you can use recursive definitions in PA.

Edit: I think I've found the answer to the question I'm asking here. See at bottom.

Do you know whether that's a feature specific to the order in which Godel chose to lay out his proof, or a necessary feature of any proof of the Godel-Rosser theorem?

The proof of Godel-Rosser I've been reading ("web.yonsei.ac.kr/bkim/goedel.pdf" ) proves the Representability Theorem without appearing to use Godel Numbering, which he defines and proves later on. As the representability theorem tells us that any recursive function or relation on the natural numbers can be represented in the language of PA, that would seem to allow a representation of any recursive function, which would include exponentiation, in PA without having to add any axioms or symbols (I think it is assumed that the symbols of the Hilbert system (\forall, \neg, \to) are also available. In fact they are used in stating the nine axioms of arithmetic).

Have I misinterpreted something there?

Edit: I found on revisiting the document that, although the proof doesn't use Godel numbering to prove the Representability Theorem, it does use the function that maps sequences of numbers to a single number, which will subsequently be used as the basis for the Godel numbering of formulas and proofs. That function draws on all the fancy machinery in Godel's system, including the Chinese Remainder Theorem and Cantor's pairing function. So I can see that, in order to be able to represent recursive functions and relations in PA, we need to have most of the elements of Godel's numbering system defined, even if we haven't yet taken the final step to apply it to formulas in the formal language.

 

[Preno]

Have I misinterpreted something there?

I don't think so, other than the fact that (first-order) Peano Arithmetic has infinitely many axioms, not nine - the axiom schema of Induction is, well, an axiom schema (in fact, PA can be proved not to be finitely axiomatizable).

 

[andrewkirk]

Yes I actually meant to refer to PA minus the axiom schema of induction. Is there a standard name for that?

 

[Preno]

Robinson Arithmetic (Q) or Minimal Arithmetic (R), depending on how you want to axiomatize PA.