Hofstadter’s ‘Gödel, Escher, Bach’

Douglas Hofstadter’s book ‘Gödel, Escher, Bach’  (Footnote: Douglas Hofstadter. ‘Gödel, Escher, Bach’. Basic Books, 1999, ISBN‑13: 978‑0465026562 Gödel, Escher, Bach: An Eternal Golden Braid - Hofstadter: Details.) has regularly been the subject of extravagant recommendations as an excellent guide to Gödel’s proof of incompleteness, and has apparently sold more than 400,000 copies. But if you are expecting it to provide you with a dependable guide to Gödel’s proof, you may be surprised to discover that Hofstadter’s explanation of Gödel’s proof fudges the crucial step of the proof, so that the result of the proof is obtained by a deceptive error rather than a valid logical argument.

Number-theoretic expressions

Note: the term ‘number-theoretic’ is used below. Many people are put off by this term, which sounds more complex than it actually is - it simply indicates that a number-theoretic expression is an expression about numbers, not about other things. See also number-theoretic.

Hofstadter’s proof of incompleteness

Hofstadter’s account of an incompleteness proof is overall quite similar to that given in Nagel and Newman’s book, Gödel’s Proof. (Footnote: PDF E Nagel and J Newman: Gödel’s Proof New York University Press, revised edition, 2001. ISBN: 0814758169.) Nagel & Newman’s book was published several years before Hofstadter’s. The proof in Nagel and Newman’s book is dealt with in detail on another webpage: Nagel & Newman. The argument presented on the Nagel & Newman page could equally well be applied to Hofstadter’s proof, and similarly, the argument below regarding the flaw could be applied to Nagel & Newman’s proof. They are simply different ways of demonstrating the confusion of language that is inherent in the proofs, which is a common feature of many incompleteness proofs.

Douglas Hofstadter

The principal thrust of Hofstadter’s proof relies on the fact that for certain statements about symbol strings of his formal system TNT, (Footnote: Note: TNT is the formal system for which Hofstadter is attempting to prove incompleteness.) there can be corresponding relations about numbers, and which are purely number-theoretic relations. (Footnote: Note: Hofstadter uses the term ‘isomorphic’ rather than ‘corresponding’.) The correspondence between these number-theoretic relations and statements about TNT symbol strings is given by a Gödel numbering system, so that the statement about symbol strings of the formal system correspond to relations of numbers, where those numbers are the Gödel numbers of these symbol combinations. (Footnote: Strictly speaking, Hofstadter’s numbering system is not a Gödel numbering system; it is not defined in terms of exponents of prime numbers, but we will call it a Gödel numbering system here for convenience.)

For convenience we will use GN to represent the numbering system used in Hofstadter’s book, so that GN(X) represents the Gödel number of some combination of symbols X of Hofstadter’s formal system TNT, where the numbering system is the one Hofstadter uses in his book. GN(X) is a function in a language that is a meta-language to the formal system TNT.

Hofstadter’s ‘Substitution leads to the second idea’

In the section ‘Substitution leads to the second idea’, Hofstadter defines a number-theoretic relation. When Hofstadter talks about this relation, he states that it defines an operation on the free variable of a formal formula which is the:

‘replacement of all free variables by a specific numeral’

Hofstadter then gives an example:

If a=a is a formal formula, and if we replace the variable a in a=a by SS0, then the resulting formula is SS0=SS0.

Then given that:

1. The corresponding Gödel number of the formula a=a is 262,111,262, and
2. The corresponding Gödel number of SS0 is 123,123,666, and
3. The corresponding Gödel number of the resultant formula SS0=SS0 is 123,123,666,111,123,123,666,

Hofstadter says that there is a purely number-theoretic relation that can be applied to these three Gödel numbers 262,111,262,  123,123,666 and 123,123,666,111,123,123,666, and that this relation is true if the relationship between the formula a=a, the substituted symbols SS0, and the resultant formula SS0=SS0 is true.

Note that in the following, we use red capitals to indicate symbol strings of the formal system, e.g. X.

Hofstadter does not give the above relation a name, so for convenience we will call it sub(a, a′, a″), where a, a′ and a″ are all variables for numbers. From his example, we see that if A, A′ and A″ are symbol strings of the formal system, then the number-theoretic relation sub corresponds, by Gödel numbering, to the substitution of the free variable of a formal formula A by a combination of formal symbols A′, to give a new formal formula A″, where a = GN(A), a′ = GN(A′), and a″ = GN(A″). (Footnote: Note: This function operates in essentially the same way as Sb, the Relation 31 in Gödel’s original proof.)

So, for the above example,

A is a=a and GN(a=a) is 262,111,262,

A′ is SS0 and GN(SS0) is 123,123,666,

A″ is SS0=SS0 and GN(SS0=SS0) is 123,123,666,111,123,123,666.

Note that if the formula A does not contain a variable, then there can be no substitution, and the resulting formula will be simply the formula A.

If sub is a number-theoretic relation, then the formal system can express that relation, so there will be a formula of the formal system that expresses that relation precisely. Hofstadter calls that formula SUB(a, a′, a″). (Footnote: Note: The relation is also what is called primitive recursive - the details are not important for our purposes here.)

Hofstadter’s ‘Arithmoquining’

In the section ‘Arithmoquining’, Hofstadter talks about the notion of substituting the free variable of a formal formula by the Gödel number of that formula itself, and then proceeds to assert that the corresponding number-theoretic relation is the already mentioned sub relation, except that the first two variables of the relation are the same, viz: sub(a″, a″, a′), and so the formula of the formal system that expresses this relation is SUB(a″, a″, a′). Hofstadter states:

‘If we wanted to speak about arithmoquining inside TNT, we would use the formula SUB(a″, a″, a′), where the first two variables are the same’.

But the sub(a, a′, a″) relation, as defined, corresponds, by Gödel numbering to the substitution of the free variable of a formal formula A by a combination of formal symbols A′, where a = GN(A), and a′ = GN(A′). So, if these first two variables of sub (or SUB) are identical, as Hofstadter asserts, then the corresponding formal symbol strings must also be identical.

But if there is to be a substitution, then the first variable of sub/SUB must be a number that corresponds to a formula with a variable (i.e: the number must be the Gödel number of a formula with a variable) - and so the second variable of sub/SUB must also be a number that corresponds to a formula with a variable (i.e: the number must be the Gödel number of a formula with a variable).

But if that is the case, then the second variable cannot be a number that corresponds to a formal symbol combination for a number, which would simply be of the form SSS…0, and which cannot contain a variable. This is a crucial error and it means that the proof is flawed beyond retrieval.

Hofstadter’s Evasion

Of course, what Hofstadter intends, but evades the implications of his intention, is that the formula SUB is not actually as he has defined it, but rather that it is a formula that corresponds to the substitution of a formula by the Gödel number of a formal symbol combination. We can express his intention as:

SUB(a″, GN(a″), a′)

The problem with this, of course, is that this cannot actually be a formula of the formal system, since the function GN is not an expression of the formal system, but an expression of the meta-language. Now, although no formal formula can include the Gödel numbering function as in SUB(a″, GN(a″), a′), let’s assume that Hofstadter is saying that there is some other formal formula that is similar to the Gödel numbering function, and which we will call Z, to give us the formula SUB(a″, Z(a″), a′). (Footnote: Note: This is similar to the composite function Sb(a ^b/_Z(c)) in Gödel’s original proof.)

Given that that is the case, then for the number-theoretic relation SUB(a″, Z(a″), a′), the corresponding relationship between symbol strings of the formal system is a relation between the symbol strings A″ and A′, where a″ = GN(A″) and a′ = GN(A′).

Recall that the Gödel numbering system is the function that defines the correspondence between:

1. A relationship between numbers (a number-theoretic relation), the numbers a″ and a′,

   and

2. A relationship between symbol strings of the formal system, the strings A″ and A′.

The correspondence, of course, works in both directions - that is, given a relationship between symbol strings of the formal system, then one can apply the Gödel numbering function to give the corresponding numbers for the corresponding number-theoretic relation - and given a number-theoretic relation, then one can apply the inverse of the Gödel numbering function to the numbers to give the corresponding symbol strings of the formal system for the corresponding relationship between symbol strings of the formal system.

What Hofstadter wants us to do is to apply the inverse of the Gödel numbering function to this number-theoretic relation SUB(a″, Z(a″), a′). So, suppose we substitute a″ by GN(A″), and a′ by GN(A′) respectively, which gives:

SUB{GN(A″), Z[GN(A″)], GN(A′)} (here we disregard for the moment that we cannot actually logically do this, since SUB is a formula of the formal system, which cannot express the GN function). If we now apply the inverse of the Gödel numbering function, we can say that the formula SUB corresponds, by the inverse of the Gödel numbering function to a relationship between the symbol strings A″ and A′ - since these are the inputs to the GN function in the above.

But Hofstadter wants us to believe that the Z function is the Gödel correspondence function, and that the formula SUB(a″, Z(a″), a′) corresponds, by the inverse of the Gödel numbering function to a relationship between the symbol strings A″, GN(A″) and A′- since, for Z[GN(A″)], GN(A″) is the input to the Z function - so if the Z function is the Gödel correspondence function, then the formula SUB(a″, Z(a″), a′) corresponds to a relationship between the symbol strings A″, GN(A″) and A′

This is, of course, complete and utter nonsense. The Z function cannot be the Gödel correspondence function GN, since all the variables of the function can only be variables for numbers, whereas the free variable of the GN function is a variable for all the symbols of the formal system. You can see an in-depth examination of this assumption of equivalence at The Flaw in Gödel’s proof of his Incompleteness theorem.

The reader might like to also read the webpage Gödel’s Substitution Function which describes in detail the substitution function that Gödel uses in his proof, and how he uses the false equivalence of his Z function and the Gödel numbering function to generate an apparent self-reference within the formal system. Also see the webpage Gödel’s Proposition V: The Z function which describes the contradictions in Gödel’s use of the Z function.

Summary

Since Hofstadter simply glosses over this material, what he presents isn’t in any way a logical proof. You might wonder why Hofstadter has evaded the key point of the proof, since he painstakingly provided a very detailed explanation of his argument up to this point in the preceding 400+ pages. But Hofstadter manages to evade the crucial flaw in his proof by skimming through the crucial section ‘Arithmoquining’ in just two pages. And although Hofstadter said at the outset of this chapter that it will be ‘more intuitive’ than Gödel’s paper, that does not excuse the use of an evasive trick to try to disguise the error in the argument that he presents.

Of course, when one becomes familiar with all the different flavors of Gödel’s proof, one will see that, time and time again, it is this key step which is glossed over. It happens in Gödel’s original paper, and in Nagel & Newman’s book, ‘Gödel’s Proof’, the first book to popularize Gödel’s proof. And, of course, the reason that it is glossed over is because it is logically unsustainable - it is an irredeemable error.

The notion that Hofstadter has that there actually is a formula of TNT for which Hofstadter claims that we must interpret it as asserting that it is itself both ‘true’ and unprovable in TNT has no logical evidence to support it. It is entirely reliant on intuitive assumptions where logic and the use of language is set aside to allow the underhand trick to appear to work by glossing over the flaw. But if there is no logical proof, then that is all it is, just a trick. And while you can fool some of the people all of the time, and you can fool all of the people some of the time, you can’t fool all of the people all of the time. When a sneaky underhand trick is exposed for what it is, only foolish people will insist on remaining fooled by the trick.

Apologists for Hofstadter say in defence of Hofstadter that the book was not meant to be as rigorous as Gödel’s proof itself. But if that was the case, then Hofstadter should have simply said something like, ‘we assume at this point that…’ . But he doesn’t - he makes no mention whatsoever of the error in his presentation, presenting it as a logical argument in exactly the same way as the rest of his book.