Logic and Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2020 https://www.jamesrmeyer.com

Note: Full functionality of this website requires JavaScript to be enabled in your browser.
 

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: 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.

 

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.

 

The reader might like to also read the webpage Gödel’s Substitution Function which describes the substitution function that Gödel uses in his proof, and also the webpage Gödel’s Proposition V 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 flavours 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.

section divider

Footnotes:

section divider

 

 

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Frivolous, irrelevant comments.
Comments devoid of logical basis.
Derogatory comments.
Long-winded comments.
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.


Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous usernames for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.


Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

 

Note: a password enables editing of comments, an email enables notification of replies

HashOver logoBased on HashOver Comment System by Jacob BarkdullHashOver logo

Copyright   James R Meyer   2012 - 2020
https://www.jamesrmeyer.com