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

Page last updated 04 Sept 2023

This page discusses Nagel & Newman’s book on Gödel’s incompleteness proof, entitled Gödel’s Proof. (Footnote: PDF E Nagel and J Newman: Gödel’s Proof. New York University Press, revised edition, 2001. ISBN: 0814758169.) 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.

It is also worth pointing out that Nagel-Newman’s erroneous proof has spawned a plethora of copies, claiming to be proofs of incompleteness while glossing over Nagel-Newman’s fudge in exactly the same way as Nagel-Newman does, see for example: How Gödel’s Proof Works.

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 web-page: 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 PDF The Fundamental Flaw in Gödel’s proof of his Incompleteness Theorem.) 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 web-page 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 web-page 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:

Sb_FS[x, 17, Z_FS(x)]

where x is the free variable of the formula, and Z_FS 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:    ~⁠(∃y)Dem{y, Sb_FS[x, 17, Z_FS(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 Sb_FS[x, 17, Z_FS(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:   ~⁠(∃y)Dem{y, Sb_FS[n, 17, Z_FS(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 Sb_FS[n, 17, Z_FS(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 Sb_FS[n, 17, the Gödel number of n]’

which is the same as:

‘There is not a proof of the formula that has the Gödel number of

Sb_FS[the Gödel number of N, 17, the Gödel number of the Gödel number of N]’

which is the same as:

‘There is not a proof of the formula that has the Gödel number of

Sb_FS[the Gödel number of ~⁠(∃y)Dem{y, Sb_FS[x, 17, Z_FS(x)]}, 17, the Gödel number of the Gödel number of ~⁠(∃y)Dem{y, Sb_FS[x, 17, Z_FS(x)]}]’

This is not a logically valid proposition - there is no symbol string of the formal system that can express the concept of Gödel numbering, never mind the concept of the Gödel number of a Gödel number of a formal expression - so that there is in fact no formal system symbol string that can express the above expressions.

With regard to 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 Sb_FS[x, 17, Z_FS(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 Z_FS(x) is equivalent to the correspondence function, which is the Gödel numbering function GN(x) is precisely the same assumption that Godel uses in his original proof of incompleteness. The assumption is untenable, since the function Z_FS(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 Z_FS(x) is defining an instance of the correspondence given by the Gödel numbering function is incorrect. You can see an in-depth examination of this assumption of equivalence at The Flaw in Gödel’s proof of his Incompleteness theorem, and also at Gödel’s Proposition V: The Z function which describes the contradictions in Gödel’s use of the Z function.

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 Sb_FS[n, 17, Z_FS(n)]’

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

~⁠(∃y)Dem{y, Sb_FS[n, 17, Z_FS(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 Sb_FS[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.