How to prove the diagonal Lemma

Question

I am interested in understanding the proof of Gödel’s Incompleteness theorems. The diagonal Lemma is used to prove the existence of self-referential statements. But as I read the proof of the Diagonal Lemma, it looks to me like it is already invoking self reference. My question is basically, how can the diagonal Lemma prove the self referential statements when it is arrived at using an indirect form of self reference?

Answer 1

First, it is worth saying that there is no such thing as the proof of Gödel's incompleteness theorem. And not all proofs go via an explicit Diagonalization Lemma (that includes Gödel's own original one). Indeed, not all go via straightforward applications of the idea of diagonalization more widely construed.

OK, that said, what about the Diagonalization Lemma? Here's a standard version. Assuming some system of Gödel-numbering is in play,

If $T$ includes enough arithmetic, and $\varphi(\cdot)$ is a one-place open sentence of $T$’s language, then there is sentence $\delta$ of the language such that $T \vdash \delta \leftrightarrow \varphi(\overline{\ulcorner\delta\urcorner})$

where as is usual, corner quotes indicate Gödel-numbering and overlining indicates a formal numeral for a number, so $\overline{\ulcorner\delta\urcorner}$ is the formal numeral for the Gödel number of the sentence $\delta$.

Now note, it is not strictly right to say the Diagonalization Lemma “is used to prove the existence of self-referential statements”. The Lemma says that, for each $\varphi$, there is $\delta$ which is provably equivalent to a wff (not about $\delta$ but) about $\delta$'s Gödel-number, saying $\varphi(\cdot)$ is true of that number. There is no strict self-reference here.

You can say that that involves “indirect” self reference if you must; but that can be distracting -- for there's nothing in the least mysterious or suspicious or circular about the proof of the Lemma. It is in fact remarkably elementary once you've got the idea of Gödel-numbering, and seen how a $T$ which includes enough arithmetic can represent primitive recursive relations like the “diagonalization” relation between the Gödel-number of a formula $\varphi$ and the Gödel-number of the corresponding $\varphi(\overline{\ulcorner\varphi\urcorner})$. You'll find an accessible version of the proof of the Lemma which should make things clear in Episode 10 of these freely available notes, Gödel Without Tears (and note, Episode 10 comes after the first incompleteness theorem is initially proved).