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.
 

Nagel & Newman’s Book: Gödel’s Proof

This page discusses Nagel & Newman’s book on Gödel’s incompleteness proof, entitled 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. (Note: the first publication of the book was in 1958.)) To follow this page, you should preferably have a copy of the book at hand. For convenience, we will refer to Nagel-Newman as though they are a singular person. It should be noted at this point that Nagel-Newman’s book is an informal exposition. It does not claim to be a proof, rather it is an overview of the main thrust of Gödel’s argument. Most of the book is in the form of a general discussion, rather than a detailed logical argument.

 

This page was written as a response to the many people who have asked where there is a flaw in Nagel-Newman’s book. One response to that might be that Nagel-Newman’s account is not a detailed logical argument, and hence cannot be said to be a proof at all. However, rather than use that as a convenient cop-out, I have tried to give an explanation of the flawed argument in Nagel-Newman’s account.

 

Note: Before dealing with Nagel-Newman’s overview, it might be pointed out that while most people take a ‘formula’ to be any mathematical expression, Nagel-Newman sometimes considers that a formula of the formal system can only be a symbol combination of the formal system that states a proposition, but at other times he uses the term more freely. It is worth bearing in mind the two different connotations that Nagel-Newman attaches to the term.

 

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.

 

Nagel-Newman’s proof of incompleteness

It might be noted that 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 - Hofstadter: Details.) gives a similar incompleteness proof to that in Nagel & Newman’s book, although Nagel & Newman can claim priority, as their book was published prior to Hofstadter’s. The proof in Hofstadter’s book is dealt with in detail on another webpage: Gödel, Escher, Bach. The argument presented on that page could equally well be applied to Nagel & Newman’s proof, and similarly, the argument below could be applied to Hofstadter’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.

 

In a discussion of a proof that involves a language making statements about another language, you might expect that the distinctions between any languages that are involved would be made absolutely clear. But Nagel-Newman, as with Gödel’s own proof, manages to confuse the language systems involved. There is a failure to ensure a clear delineation of the different systems in the proof, and in Nagel-Newman’s account, in common with Gödel’s, there is a consequent confusion of language systems. (Footnote: This aspect of the number-theoretic system being an object language to the meta-language is dealt with in more detail in the paper on Gödel’s proof, see The Fundamental Flaw in Gödel’s proof of his Incompleteness Theorem PDF.) The part of the book where this confusion becomes most evident is in the section VII, B ‘The arithmetization of meta-mathematics’, where Nagel-Newman introduces a function called sub(x, 17, x).

 

 

Nagel-Newman’s ‘Substitution’ Function

Before reading the rest of this section, the reader might like to first read the webpage Gödel’s Substitution Function which describes the substitution function that Gödel uses in his proof.

 

The confusion of language in Nagel-Newman’s account can be seen to center around the same functions as in Gödel’s proof, and the correspondences defined by the Gödel numbering system. Although Nagel-Newman’s book follows most of Gödel’s proof, the last part involving the use of the substitution function is somewhat different to Gödel’s proof. Nagel-Newman refers to a function sub(x, 17, x), with only one free variable, x, but does not give a precise definition of the function.

 

Nagel-Newman states that the function gives: the Gödel number of the formula obtained by taking the formula with Gödel number x and, wherever there are occurrences of the variable ‘y’ in that formula, replacing them by the numeral for x (where he means numeral to mean the number x in the format of the formal system).

 

However, it can be shown that what Nagel-Newman is referring to is the combination of two functions as used in Gödel proof, the function Sb and the function Z. By not having to give a detailed proof regarding the sub function, Nagel-Newman manages to obscure the fact that he is confusing different systems by his use of the composite function Sb(x, 17, Z(x)).

 

 

Flawed Assumptions

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

 

Nagel-Newman’s function sub(x, 17, x) cannot be Gödel’s function Sb(x, v, y), since that is defined so that if x is the Gödel number of a formula X, and y is the Gödel number of a formula Y, and v is the Gödel variable number for a variable V, then Sb(x, v, y) corresponds to the operation of substituting the symbol V where it occurs as a free variable within the symbol string X, by the symbol string Y. So if Nagel-Newman’s function could be Gödel’s function Sb(x, v, x), then x would be the Gödel number of a formula X, so the Sb function would correspond to the substitution of the variable V by the symbol string that is the formula X. But Nagel-Newman states that the sub function corresponds to the substitution of the variable of the formula by the Gödel number of the formula, and furthermore he assumes that there is such a purely number-theoretic function that corresponds to such a substitution.

 

Nagel-Newman therefore relies on the same flawed assumption as Gödel, that the composite function Sb(x, 17, Z(x)) as given in Gödel’s proof is a function that corresponds, by Gödel numbering to the substitution of the variable of a formula by the Gödel number of that formula itself. Nagel-Newman’s use of the function Sb(x, 17, Z(x)) is subtly different to Gödel’s, but Nagel-Newman’s use of the function also demonstrates a confusion of language systems. See also the webpage Gödel’s Proposition V which discusses Gödel’s use of the Sb(x, 17, Z(x)) function in detail.

 

Now, while the Gödel numbering function can define a relation between natural numbers that corresponds to a relationship between symbol strings of the formal system, it must be borne in mind that the Gödel numbering system itself is defined in terms of number-theoretic relations. That being the case, there is a possibility that certain number-theoretic relations can be confused with the definitions used to define the Gödel numbering function - since the definition of the Gödel numbering function includes definitions of number-theoretic relations. There is a possibility that certain propositions are context dependent - a characteristic which is most undesirable within logical arguments.

 

Having asserted that there is a number-theoretic function that precisely mirrors the substitution of a formula X by the Gödel number of that formula X, Nagel-Newman asserts that there is a formula of the formal system that expresses this function, and he denotes it by Sub[x, 17, x] (note the difference between the former sub and this Sub is by capitalization of the initial letter S). Since this function, as in Gödel’s proof, is an expression of the composite function of Gödel’s functions Sb and Z, we will denote the function as it is expressed in the formal system as:

 

SbFS[x, 17, ZFS(x)]

 

where x is the free variable of the formula, and ZFS is the formula in the formal system that expresses the function Z.

 

Nagel-Newman uses this function to construct a formula of the formal system, which we will call N:

 

N    ~(∃x)Dem{x, SbFS[x, 17, ZFS(x)]}

 

Nagel-Newman asserts that this formula has an associated proposition (by Gödel numbering) that is:

There is not a proof of the formula that has the Gödel number of SbFS[x, 17, ZFS(x)]

 

Nagel-Newman now states that this formula N above has some Gödel number, which we call n. We now substitute the value n for x in the formula N itself to give a new formula that Nagel-Newman calls G:

 

G:     ~(∃x)Dem{x, SbFS[n, 17, ZFS(n)]}

 

which Nagel-Newman asserts as having an associated proposition (by Gödel numbering) that is:

There is not a proof of the formula that has the Gödel number of SbFS[n, 17, ZFS(n)]

 

But crucially, Nagel-Newman also assumes that this is equivalent to a statement that we shall try to vaguely indicate by:

There is not a proof of the formula that has the Gödel number of SbFS[n, 17, the Gödel number of n]

 

By that we mean that Nagel-Newman asserts that the formula G corresponds to the notion of the substitution of the free variable x in the formula N by the Gödel number of N. You should note that the expression,

 

There is not a proof of the formula that has the Gödel number of SbFS[n, 17, the Gödel number of n]

 

is not a logically valid proposition, since there is no symbol string of the formal system that can express the concept of Gödel numbering, so that there is in fact no formal system symbol string that can express SbFS[n, 17, the Gödel number of n]. The occurrence of SbFS[n, 17, the Gödel number of n] within the above expression is not a logical construct.

 

For the purposes of logical analysis, it is a somewhat unfortunate consequence of human evolution that the human mind almost invariably attempts to attach a meaning to an expression, rather than subject it to precise logical analysis. Until the last few thousand years, all expressions were spoken, and so the human mind evolved to assume that all expressions are intended to convey a meaning, rather than logically analyze them. And so we have evolved to feel the need to attach a meaning to all expressions, even though there may be no logical justification for such a meaning. Similarly, people almost invariably attempt to attach a meaning to Nagel-Newman’s expression G that has no logical justification.

 

 

Distinct Systems

One way to demonstrate why Nagel-Newman’s assumptions have no logical justification is to consider as follows:

 

If the system of number-theoretic relations and the formal system are distinct systems, then there is nothing that forces any symbols of the two distinct systems to be identical, so that their symbols may be completely different. So, consider the case if we use symbols for the numbers that occur within the Gödel numbering system that are different to the symbols for numbers within the formal system. Then we can say that, for the formula SbFS[x, 17, ZFS(x)], the variable x can only be substituted by symbols strings of the formal system (since the formula is a formula of the formal system), and there can be a symbol string x of the formal system, and we can indicate the Gödel number of x by GN(x), where GN is the Gödel numbering function.

 

But Nagel-Newman’s assumption is that the ZFS(x) is equivalent to the correspondence function, which is the Gödel numbering function GN(x).

 

But that cannot be the case, since the function ZFS(x) always evaluates as a value that is a symbol string (for a number) of the formal system, whereas in this case the Gödel numbering function always evaluates as a value that is a numerical value, but is not a symbol string of the formal system - since we are using symbols for number-theoretic relations that are completely different to those of the formal system.

 

Hence the assumption by Nagel-Newman that the function ZFS(x) is defining an instance of the correspondence given by the Gödel numbering function is incorrect.

 

There is therefore no reason to suppose that the truth value of the proposition:

There is not a proof of the formula that has the Gödel number of SbFS[n, 17, ZFS(n)]

 

which is the proposition associated by the Gödel encoding to the formula G, which is

 

~(∃x)Dem{x, SbFS[n, 17, ZFS(n)]}

 

is in any way associated with a truth value of the expression:

 

There is not a proof of the formula that has the Gödel number of SbFS[n, 17, GN(n)]

 

an expression that has no logical validity, and no valid truth value.

 

When we use different symbols for the different systems, we can see that GN(n) has no valid syntax in this context, and hence there can be no truth value for the above expression, as it is not a logically valid proposition.

 

The reader might suppose that the above can be circumvented by forcing the formal system and the number-theoretic system to be a singular system. But the Gödel numbering function, is, by definition, a function that is in a language that is a meta-language to the formal system. And since that is the case, if those parts of the Gödel numbering function that are definitions within the system of number-theoretic relations are actually definitions within the formal system, then the Gödel numbering function is not correctly defined as a function of the meta-language, and the result is a definition that is not logically valid.

 

Hence, Nagel-Newman’s assumptions are a demonstration of a nonsensical confusion of language systems because of a misapplication of the encoding correspondence given by the Gödel numbering system, a confusion which is made possible by the use of some symbols that are the same for the formal system and for the system of number-theoretic relations.

 

Finally, you might be interested that Nagel-Newman discusses Richard’s paradox in detail, and points out the linguistic confusion that results in the paradox. He also observes that:

“The importance… of recognizing the distinction between mathematics and meta-mathematics cannot be overemphasized. Failure to respect it has produced paradoxes and confusion.”

 

Indeed - it is rather ironic that Nagel and Newman’s explanation of Gödel’s proof is itself an instance of the failure to observe that distinction, as is Gödel’s original proof.

 

 

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

Peter Smith’s ‘Proof’

It has come to my notice that, when asked about the demonstration of the flaw in his proof (see A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF), Smith refuses to engage in any logical discussion, and instead attempts to deflect attention away from any such discussion. If any other reader has tried to engage with Smith regarding my demonstration of the flaw, I would be interested to know what the outcome was.

 

 

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.

 

Previous Blog Posts  

 

13 May 2015 Good Math, Bad Math?

 

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 - 2017  
www.jamesrmeyer.com