Footnotes:
Nagel & Newman’s Book: Gödel’s Proof
Page last updated 16 Feb 2024
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 only about numbers, not about any 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.
A language that makes statements about another language is called a meta-language, while a language that a meta-language makes statements about is called an object or sub-language. 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.) 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. The Gödel numbering system is a function takes any expression of the formal language and outputs a number that corresponds uniquely to that expression, for example if we call the function GN, then GN[w] gives a unique number for w as some expression of the formal 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. He also says that there is a function Sub(x, 17, x) in the formal system that functions in exactly the same way as the function sub(x, 17, x).
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).
Flawed Assumptions
So, what Nagel-Newman is referring to by his use of Sub(x, 17, x) is the combination of two functions. And in exactly the same way as Gödel does in his proof, Nagel-Newman simply assumes that the function Sub(x, 17, x) contains within itself a purely number-theoretic function that exactly replicates the Gödel numbering function, and that this function, even though it is within a purely number-theoretic system, is able to assert that a number is the Godel number of an expression of the formal system - i.e, Nagel-Newman assumes that there is a purely number-theoretic function that we can call Z(x), and that Z(x) = GN[x], provided that x is a number, and which is contained within his Sub(x, 17, x) function.
But this is absurd, since the two functions Z(x) and GN[x] belong to two different language systems. The function GN[x] is defined as being a function that is defined outside of the formal system, whereas the function Z(x) id defined within the formal system itself.
Previously, I have gone into detail regarding this absurdity on different pages, but since I have already demonstrated it in detail elsewhere, it seems more sensible to direct the reader to that page rather than trying to maintain several different pages saying essentially the same thing.
And since Nagel-Newman is simply following Gödel’s account (while leaving out many details), the reader is therefore directed to Gödel’s Substitution Function which gives a detailed explanation of the absurdity of the assumption of equivalence of the two functions Z and GN.
Summary
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 statements that have no logical justification.
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.
Rationale: Every logical argument must be defined in some language, and every language has limitations. Attempting to construct a logical argument while ignoring how the limitations of language might affect that argument is a bizarre approach. The correct acknowledgment of the interactions of logic and language explains almost all of the paradoxes, and resolves almost all of the contradictions, conundrums, and contentious issues in modern philosophy and mathematics.
Site Mission
Please see the menu for numerous articles of interest. Please leave a comment or send an email if you are interested in the material on this site.
Interested in supporting this site?
You can help by sharing the site with others. You can also donate at where there are full details.