The Diagonal Lemma

Page last updated 17 Jan 2025

It is claimed that a statement that is commonly called the Diagonal Lemma, or the Diagonalization Lemma, proves the existence of self-referential sentences in formal systems of natural numbers, and that it can be used to prove incompleteness of certain formal systems. The Diagonal Lemma essentially states, that for any given formula of the formal system with one free variable, that formal system can prove a certain proposition regarding the Gödel numbering system.

The formulas of the formal system have no way of referring to the Gödel numbering function, since, by definition, it is a function that is defined in a meta-language to the formal system. So the idea that it is possible to prove that the formal system can prove a proposition regarding the Gödel numbering system is one that deserves careful scrutiny.

The following proofs of the Diagonal ‘Lemma’ are examined here:

1. A proof given in the book, ‘Computability and Logic’, by George Boolos, John Burgess, and Richard Jeffrey
2. A proof given in the book, ‘Introduction to Mathematical Logic’, by Elliott Mendelson
3. A proof on the Wikipedia website
4. A proof on the ProofWiki website
5. A proof by Panu Raatikainen on the Stanford website
6. A proof by Vann McGee of MIT

There is also a proof of the lemma in the book, ‘An Introduction to Gödel’s Theorems’. (Footnote: Peter Smith. An Introduction to Gödel’s Theorems. Cambridge University Press, 2006.
ISBN: 9780521857840 See An Introduction to Gödel’s Theorems: Details.) by convicted paedophile ex-professor Peter Smith, and there is also a downloadable cut-down version of his book at PDF Logic Matters: Peter Smith’s Gödel Without (Too Many) Tears. The error in Smith’s “proof ” of the lemma is the same error that is dealt with in detail in the paper PDF A Fundamental Flaw in an Incompleteness Proof by Peter Smith. As in the generic proof below, Smith’s error is to assume that certain functions/relations are primitive recursive number-theoretic functions/relations despite the fact that their actual definition defines them as not being primitive recursive number-theoretic functions/relations.

Please note:

• The rest of the content of this page requires a basic knowledge of symbolic logic.
• Some of the symbols used on this page may not display correctly on older browsers.

The Generic Proof of the Diagonal ‘Lemma’

While the proofs mentioned above are all slightly different, the main core is the same, and they all rely on the same elementary error. Because the main core is the same in all the proofs, a generic proof can be written, and which contains the essence of the four proofs mentioned above. This generic proof of the Diagonal ‘Lemma’ is as follows:

The flaw in the proof is obvious. For there to be a formula in the system T that expresses the relation δ, the function f must satisfy certain conditions (as in step (3) above). But in the above, at step (17), the function f (x) is defined as the function GN[β(x)], and so is defined in terms of the Gödel numbering function. Because the Gödel numbering function is a function in the meta-language to the system T, there cannot be any such relation δ in the system T that contains the information of the definition of the Gödel numbering function and which can unambiguously reference formulas of its own formal system T. A full proof of this is given in the paper PDF The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System.

Thus step (17) is a logical absurdity. This absurdity is disguised in the proofs mentioned above by their presentation, which serves to obscure the inherent absurdity.

An unresolvable circular definition

The flaw can also be demonstrated by observing that the definition of the function β(x) is not a valid definition since there is no expression of the formal system that can correspond to it, viz:

Boolos’ Proof of the Diagonal Lemma

This proof is found in the book, ‘Computability and Logic’, by George Boolos, John Burgess, and Richard Jeffrey, (Footnote: G Boolos, J Burgess, R Jeffrey. Computability and Logic. Cambridge University Press, 5th Edition, 2007.
ISBN‑13 978‑0511366680 Computability and Logic - Boolos: Details.) and is given as a proof of the lemma 17.1 in the book.

The rest of Boolos’ proof follows the general outline as given in the generic proof above, generating the inevitable result of:

├ _T G ⇔ B( ^⌐G^¬ )

a result which is completely dependent on the fallacy that the function diag can be at the same time a primitive recursive number-theoretic function and also be defined at the same time as the Gödel number of the diagonalization of A, that is, as ∃x(x = ^⌐A^¬ & A).

It will be seen that the main part of the proof has nothing whatsoever to do with proving self-reference, and that the self-reference in the proof is that brought about by the invalid introduction of the definition of diag as indicated above.

Mendelson’s Proof of the Diagonal Lemma

Mendelson’s proof of the Diagonal Lemma is given in Chapter 3 of his book ‘Introduction to Mathematical Logic’. (Footnote: E Mendelson. Introduction to Mathematical Logic. Chapman & Hall/CRC, 6th edition, 2015
ISBN 9781482237726 Introduction to Mathematical Logic - Mendelson: Details.)

Note: Some of the symbols used by Mendelson appear somewhat differently in HTML code. Note also that Mendelson uses an overscore (such as q for q ) to indicate the format of numbers within the formal system.

In his section Proposition 3.27, Mendelson defines a primitive recursive function with one free varaible as D(u) , and he calls this the “diagonal function”.

Then, in his Proposition 3.34 (Diagonalization Lemma).he gives his statement of the Diagonal Lemma as:

where ^⌐𝒞^¬ represents the Gödel numbering function, that is, it represents the Gödel number of 𝒞.

The proof proceeds as follows:

The pertinent information here is that the relation 𝒟 is intended to be an precise representation of D within the system K.

Now, Mendelson provides a proof that D is a primitive recursive number-theoretic function in the section entitled Proposition 3.27, where he defines:

and he had previously defined the function Sub as a primitive recursive number-theoretic function in his Proposition 3.26 (10). Thus Mendelson defines D in purely number-theoretic terms as a primitive recursive number-theoretic function. (Footnote: It might be noted that Mendelson also makes references to Gödel numbering along with the actual definitions of primitive recursive number-theoretic relations. However, it is only the actual definitions that have applicability in any logical analysis.)

In his proof of the Diagonal Lemma, Mendelson sets out by logical steps, as in the generic proof given above, that given that:

𝒞 is a relation defined by (∀x₂) [𝒟( m, x₂) ⇒ ℰ (x₂)],

ℰ is any relation of the system K with one free variable,

𝒟( m, x₂)   ≡   x₂ = D(m)

D is a primitive recursive number theoretic function as defined above, and

q = D(m),

then it can be shown that:

├ _K 𝒞 ⇔ ℰ (q).

However, while Mendelson states that the function D is a primitive recursive number-theoretic function, he also states that q is the Gödel number of the formula 𝒞, that is, he is asserting that:

q = GN((∀x₂) [𝒟( m, x₂) ⇒ ℰ (x₂)]) and at the same time q = D(m)

in other words, that

D(m) = GN((∀x₂) [𝒟( m, x₂) ⇒ ℰ (x₂)]).

Here, Mendelson’s proof is logically absurd. It cannot be the case that D is defined to be a primitive recursive number-theoretic function, and, at the same time, be defined in terms of the Gödel number of a formula of the system K. The definition of q as the Gödel number of a formula is a definition that includes the Gödel numbering function, a function of the meta-language, not of the system K.

As in the Boolos proof, the main part of the proof has nothing whatsoever to do with proving self-reference; the self-reference in the proof is that brought about by the invalid assumption that the function D can be at the same time a primitive recursive number-theoretic function, and at the same time, a function that is defined in terms of a meta-language to the system K.

The Wikipedia Proof of the Diagonal Lemma

This proof of the lemma is that given in Wikipedia, as of 15 August 2012. The current page is Wikipedia - The Diagonal Lemma. The text of the proof of 15 August 2012 is given Wikipedia - The original text: below.

Note: The Wikipedia proof uses underlines to indicate the numeric notation of the formal system (such as m for m); these have been omitted here, as they are secondary to the demonstration of the error in the proof.

The statement of the Lemma is given as:

Let T be a first-order theory in the language of arithmetic and capable of representing all computable functions. Let ψ be a formula in the theory T with one free variable. The diagonal lemma states that there is a sentence φ such that φ ⇔ ψ(#(φ)) is provable in T (Here, # denotes the Gödel numbering function, that is, #(φ) represents the Gödel number of φ).

The Proof of the Lemma commences as:

This proof is nonsensical from the outset. Regardless of the details of the system T, all formulas of the system T must be constructed from a clearly defined set of symbols. The Gödel numbering function must reference this entire set of symbols and must be in a meta-language to the system T, and because of this, it is impossible for a formula of the system T to include the definition of the Gödel numbering function.

This proof is yet another example of a ‘proof’ of self-reference being simply an assertion of the existence of self-reference included amongst a few lines of formulas that are dressed up to look like a logical proof.

It might be remarked of the given function that is defined as the outset of the proof by:

that a similar function can be defined in purely number-theoretic terms. For the first part of the definition (2), the value of the input to the function can be defined as a number that satisfies the condition that it can be factored into consecutive prime numbers (i.e: 2^a· 3^b· 5^c· 7^d· 11^e· 13^f … ), and that the exponents of the prime factors must follow certain conditions. The value of the function if the input satisfies these conditions is a value that can be stated in purely numerical terms.

And, given this purely number-theoretic definition, you can define, in the meta-language, a particular Gödel numbering function. You can then state, in the meta-language, that your previously defined number-theoretic function corresponds to this one particular Gödel numbering function (there are infinitely many Gödel numbering functions). But it must be borne in mind that this is stated in the meta-language, not in the language that this particular Gödel numbering function refers to.

As is the case for the other proofs mentioned here, you cannot have it both ways. You either define the function in terms of the Gödel numbering function, and accept that it is not a function that can be expressed by the formal system in question - or you define a function in purely number-theoretic terms and accept that it is not a function that refers to the Gödel numbering function.

The ProofWiki Proof of the Diagonal Lemma

This proof of the lemma is that as given in ProofWiki as of 15 August 2012. The current page is ProofWiki - The Diagonal Lemma. The text of the proof of 15 August 2012 is given ProofWiki - The original text: below.

Note: Where the notation for the Gödel numbering function occurs in the original, for example as , this has been replaced by #(A), which denotes the Gödel number of A.

The statement of the Lemma is:

The ProofWiki proof proceeds as follows:

As for the Wikipedia proof, the proof is nonsensical from the outset. Although the proof states that diag is a primitive recursive function, the function diag is actually defined in terms of the Gödel numbering function. And, regardless of the details of the system T, all formulas of the system T must be constructed from a clearly defined set of symbols. The Gödel numbering function must reference this entire set of symbols and must be in a meta-language to the system T, and because of this, it is impossible for a formula of the system T to include the definition of a Gödel numbering function. Hence it is impossible for there to be a purported formula, Diag(x, y) as defined above, in the system T.

Incidentally, this proof includes another quite elementary error. At one step (see ProofWiki Step 6 below) the author of the proof adds the formula G as an axiom to the system T to create a different system T ′. Similarly, at another step (see ProofWiki Step 12 below), the author of the proof adds the formula B(#(G)) as an axiom to the system T to create a different system T ′.

However, in the first case, this assumes that the system T does not already prove the negation of G for any formula B, and in the second case, that the system T does not already prove the negation of B(#(G)) for any formula B. No justification is given to support these assumptions.

Panu Raatikainen’s Proof of the Diagonal Lemma

In the article The Diagonalization Lemma on the Stanford Encyclopedia of Philosophy website, Panu Raatikainen, an associate professor at the University of Helsinki, gives a ‘proof’ of the Diagonalization Lemma. He proceeds as follows:

Here, Raatikainen claims that ^⌐A(n)^¬ can be expressed in the “language of arithmetic”, but he declines to furnish any proof of this claim, nor does he provide any sort of logical argument to support the claim. In fact it can be shown that the Gödel numbering function cannot be expressed in the language of arithmetic, see PDF The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System. By simply assuming that ^⌐A(n)^¬ can be expressed in the language of arithmetic, Raatikainen has assumed that the language of arithmetic can self-reference, and the subsequent self-referential result is a trivial consequence of that assumption. You will see this sort of assumption time and time again used as a cheap trick in order to obtain self-reference.

Vann McGee’s Proof of the Diagonal Lemma

PDF Vann McGee is a professor of philosophy at MIT. Among his lecture course notes the following can be found on the MIT website at PDF Gödel’s First Incompleteness Theorem by Vann McGee.

In it McGee starts off by saying (he refers to the Diagonal Lemma as the Self-referential Lemma):

Then he goes on to say:

Well, in fact, it is very easy to have a very clear understanding of why the Diagonal Lemma does not work. It’s because it simply assumes that the Gödel numbering function can be expressed by the formal system, whereas the reality is that every Gödel-type numbering function is a meta-language function, and the formal language cannot express it (see the paper PDF The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System ). And that’s why it might appear to have a “rabbit-out-of-a-hat” quality - because just like a magician pulling a rabbit out of an empty hat, there is a trick that makes it appear that that is happening, whereas the reality is far more prosaic.

In McGee’s subsequent ‘proof’, he defines a function where he simply assumes that the formal system can express the Gödel numbering function. So in effect his ‘proof’ amounts to:

We prove that the formal system can represent itself by first assuming that the formal system can represent itself.

Incidentally, McGee is incorrect in stating that Gödel wrote down that formula; in fact it appears that it was Carnap who first came up with an expression that can be considered to be a representation of the Diagonal Lemma formula. (Footnote: Rudolf Carnap. Logische Syntax der Sprache, Springer Verlag, Vienna, 1934, English translation by A. Smeaton. The logical syntax of language. Routledge and Kegan Paul, 1937.)