# Concrete example for diagonal lemma

Diagonal lemma says that in a theory with enough assumption for any formula $A(x)$ there exist a sentence $B$ such that $B$ $\iff$ $A(\#(B))$ is a theorem in that theory, in which $\#(B)$ represents the numeral of Gödel number of $B$. I have no problem with the proof of this lemma, but I ask you to give me a concrete example for application of this lemma for a given formula $A(x)$ such as : $x$ is an even number. I want this example to enhance my intuition for this lemma. I want to ask you what is the intuitive idea behind this lemma? i.e. in spite of its mathematical proof, is this lemma expectable and intuitive for you that for any coding of formulas $B$ $\iff$ $A(\#(B))$ is a theorem in that theory or this lemma isn't expectable and intuitive? Please explain it more intuitively. Thank you very much.

-

With :

give me a concrete example of ...

are you menaing : write down the formula ?

If so, as per Asaf'answer, we have to start with a language and an encoding of it.

We can "play with" the first step of the proof, trying to "enhance our intuition".

See Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001).

See page 235 for the diagonal (or fixed-point) lemma :

Fixed-Point Lemma : Given any formula $\beta$ in which only $v_1$ occurs free, we can find a sentence $\sigma$ such that $\vdash \sigma \leftrightarrow \beta(S^{\ulcorner \sigma \urcorner}0)$.

See page 183 for the language of $\mathcal N$ :

$\mathcal N = (\mathbb N; 0, S, <, +, \cdot, E)$ (where $E$ stands for "exponentiation").

See page 225 for the encoding :

$0$ is "$\forall$"; $1$ is "("; $2$ is $0$; $3$ is ")"; $4$ is $S$; $5$ is $\lnot$; $6$ is "<"; $7$ is "$\rightarrow$"; $8$ is "$+$"; $9$ is "$=$"; $10$ is "$\cdot$"; $11$ is "$v_1$"; $12$ is "$E$" and $13$, ... are "$v_2$", ...

See bottom page 225 for the example of "encoding" : $(\exists v_3 v_3 = 0)$ which is (in "primitive" notation) : $(\lnot \forall v_3 (\lnot = v_30))$.

We have that $\ulcorner (\lnot \forall v_3 (\lnot = v_30)) \urcorner = 2^2 \cdot 3^6 \cdot 5^1 \cdot 7^{16} \cdot 11^2 \cdot 13^6 \cdot 17^{10} \cdot 19^{16} \cdot 23^3 \cdot 29^4 \cdot 31^4$.

This is a large number, being of the order of $1.3 \times 10^{75}$.

Now we have to "encode" the formula $\beta := Even(v_1)$.

But :

$Even(x)$ is $\exists y (x = y \cdot 2)$;

thus, we have to "encode" : $(\exists v_2 v_1 = v_2 \cdot SS0)$ i.e. :

$(\lnot \forall v_2 (\lnot = v_1 \cdot v_2 SS0))$.

Its encoding will be : $2^2 \cdot 3^6 \cdot 5^1 \cdot 7^{14} \cdot 11^2 \cdot 13^6 \cdot 17^{10} \cdot 19^{14} \cdot 23^{12} \cdot 29^{11} \cdot 31^{14} \cdot 37^5 \cdot 39^5 \cdot 43^3 \cdot 47^4 \cdot 53^4$,

... I hope.

Ant this was the "easy" part : we have computed $\ulcorner \beta \urcorner$, i.e. the so-called Gödel number for the formula $\beta$.

At this point, we can try the "mental exercise" of considering the formula $\beta(v_1) := Even(v_1)$, and use its Gödel number $\ulcorner \beta \urcorner$ just defined to "compute" the Gödel number of $\beta(\ulcorner \beta \urcorner)$.

But this is not enough. For the proof of the diagonal lemma, we have to build up the formula [see page 235] :

(*) $\forall v_3(\theta(v_1, v_1, v_3) \rightarrow \beta(v_3))$

where $\theta$ [see page 228] is the formula which "functionally represent" the "substitution" function $S_b$ such that for a term or formula $\alpha$, variable $x$, and term $t$ :

$S_b (\ulcorner \alpha \urcorner, \ulcorner x \urcorner, \ulcorner t \urcorner) = \ulcorner \alpha(x/t) \urcorner)$.

We have to note that the above formula has only $v_1$ free. Thus, it defines in $\mathcal N$ a set to which $\ulcorner \alpha \urcorner$ belongs iff $\ulcorner \alpha(S^{\ulcorner \alpha \urcorner}0) \urcorner$ is in the set defined by $\beta$.

Let $q$ be the Gödel number of (*). Let $\sigma$ be $\forall v_3[\theta (S^q0, S^q0, v_3) \rightarrow \beta(v_3)]$.

Thus $\sigma$ is obtained from (*) by replacing $v_1$, by $S^q0$.

What have we attained so far ?

We have showed that, for every expression of the system, we can "effectively" produce a very long formula of number theory which - in principle - we can "calculate" in order to find the "enormous" Gödel number of the original expression.

The system is a language for number theory and the "trick" of encoding (or arithmetization of syntax) allows us to use the expressive capabilities of the system to "speak of" facts regarding the system itself.

Simplifying a lot, we can say that the way in which the system "speak of" is through computing numbers.

Thus, the encoding translates facts "about" the system, like the "provability" relation, into facts "into" the system, i.e.computations.

The diagonal lemma allows us to find (i.e.to "compute" the value of the encoding of), for any formula $\beta$ in which only $v_1$ occurs free, a sentence $\sigma$ such that ...

I think that there is nothing intuitive in the proof of the lemma; in fact, it was necessary the presence of a genius like Gödel to have the intuition that we can "encode" facts about the system into the system itself.

But the intuition must be "trained" through the long and tedious proof of all the preliminary lemmas necessary to complete the task of encoding.

-
Thank you very much for your attention. Ok. You are right, but I want to ask you what is the intuitive idea behind this lemma? i.e. in spite of its mathematical proof, is this lemma expectable and intuitive for you that for any coding of formulas B ⇔ A(#(B)) is a theorem in that theory or this lemma isn't expectable and intuitive ?Please explain it more intuitively. –  aminliverpool Jun 2 at 9:02
As an aside, the general diagonalization lemma is due to Carnap. One nice summary is the comment by Peter Milne at logicmatters.net/2012/01/… . –  Carl Mummert Jun 2 at 11:50
@aminliverpool: I doubt copying and pasting portions of your original questions on people's answers is going to make them give you anything more enlightening. –  Malice Vidrine Jun 2 at 14:47

In the case where $A(n)$ means that $n$ is even there are two options:

1. True sentence whose Godel number is even.
2. False sentence whose Godel number is odd.

Of course this depends on the encoding of formulas into numbers, since there are many ways of doing that, there are many ways to solve this.

The lemma assures you that regardless to the way that you coded the formulas (as long as it's reasonable), there will be a true sentence whose code is even or there will be a false sentence whose code is odd. And quite possibly, both options can be true.

-
Thank you very much for your attention. Ok. You are right, but I want to ask you what is the intuitive idea behind this lemma? i.e. in spite of its mathematical proof, is this lemma expectable and intuitive for you that for any coding of formulas B ⇔ A(#(B)) is a theorem in that theory or this lemma isn't expectable and intuitive ?Please explain it more intuitively. –  aminliverpool Jun 2 at 8:58
Interestingly, we already know that there is a true sentence whose number is even, or a false sentence whose number is odd, for otherwise the set of all sentences with odd numbers would be the set of true sentences. But the former set is computable and the latter isn't. –  Carl Mummert Jun 2 at 11:52

I do not believe there is any easy intuition that would guide you to a proof of the diagonal lemma (e.g. the on on Wikipedia). This proof is simply one of those things that seems to appear out of the blue; you find it amazing that the construction works; and after you learn the method you genuinely know more than you did before.

Although the rudiments of the diagonal lemma are in Gödel's work, the diagonal lemma itself was first proved by Carnap, not by Gödel. More of the historical story, and references, are given in a comment by Peter Milne here. I think this emphasizes that even when the incompleteness theorems were first proven the diagonal lemma was not an obvious intuition. The lemma was only discovered later upon reflection. So there is no reason to think, as a student, that the lemma will be entirely intuitive at first.

-