This page is keyboard accessible:
• Use Tab, Shift + Tab keys to traverse the main menu. To enter a sub-menu use the Right Arrow key. To leave a sub-menu use the Left Arrow or the Escape key.
• The Enter or the Space key opens the active menu item.
• To skip the menu and move to the main content, press Tab after the page loads to reveal a skip button.
• To get back to the top of the page anytime, press the Home key.
• For more information, click here: Accessibility   Close this tip.

Note: Full functionality of this web page 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 deception 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 Gödel’s Proof: Details.) 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 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 a 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 a 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.

 

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.

 

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 flawed step of the 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 in support of the argument presented.

 

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.

 

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. 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 defect in his presentation, presenting it as a logical argument in exactly the same way as the rest of his book.

 

 

Footnotes:

 

 

Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked (comments will be checked before appearing on this site). Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - this will only be used to notify you of replies to your comments - it will never be used for any other purpose, will never be displayed and does not require verification. Comments are common to the entire website, so please indicate what section of the site you are commenting on.

 

If you cannot see any comments below, it may be that a plug-in on your browser is blocking Disqus comments from loading. Avast anti-virus in particular is known to do this, especially with Internet Explorer and Safari. See Disqus Browser plug-in/extension conflicts or Why isn’t the comment box loading?.

 

 

Please wait for comments to load …  

 

The Lighter Side

 

NEWS

There’s something about Gödel by Francesco Berto

There is a new addition to the page Yet another flawed incompleteness proof, where Berto’s proof of incompleteness in his book There’s something about Gödel comes under scrutiny.

 

 

Easy Footnotes

I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).

 

 

O’Connor’s “computer checked” proof

I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.

 

 

New page on Chaitin’s Constant

There is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.

 

 

Updated: Diagonal Lemma

Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.

Previous Blog Posts  

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

31 Mar 2015 Cranks and Crackpots

 

30 Apr 2015 The Chinese Room

 

Links  

 

For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem

 

– a page with general links:

Gödel Links

 

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

 

Printer Friendly

 

All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.


Note: for some browsers JavaScript must be enabled for this to operate correctly.

 

Comments

 

Comments on this site are welcome, please see the comment section.

 

Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.

 

If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.

 

Feedback about site design would also be appreciated so that I can improve the site.

 


Copyright © James R Meyer 2012 - 2016  
www.jamesrmeyer.com