Note: Full functionality of this website 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
) 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.
) 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:

**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**: ** ~(∃x)Dem{x, 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**: **~(∃x)Dem{x, 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]**’

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* **Sb _{FS}[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 **Sb _{FS}[n, 17, the Gödel number of n]**. The occurrence of

**Sb**within the above expression is not a logical construct.

_{FS}[n, 17, the Gödel number of n]

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 **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)**.

But that cannot be the case, 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.

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

**~(∃x)Dem{x, 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.

Footnotes:

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