## Supplement: The Diagonalization Lemma

The proof of the Diagonalization Lemma centers on the operation of substitution (of a numeral for a variable in a formula): If a formula with one free variable, $$A(x)$$, and a number $$\boldsymbol{n}$$ are given, the operation of constructing the formula where the numeral for $$\boldsymbol{n}$$ has been substituted for the (free occurrences of the) variable $$x$$, that is, $$A(\underline{n})$$, is purely mechanical. So is the analogous arithmetical operation which produces, given the Gödel number of a formula (with one free variable) $$\ulcorner A(x)\urcorner$$ and of a number $$\boldsymbol{n}$$, the Gödel number of the formula in which the numeral $$\underline{n}$$ has been substituted for the variable in the original formula, that is, $$\ulcorner A(\underline{n})\urcorner$$. The latter operation can be expressed in the language of arithmetic. Note, in particular, that nothing prevents $$\boldsymbol{n}$$ from being the Gödel number of $$A(x)$$ itself, that is, $$\ulcorner A(x)\urcorner$$ (in the usual coding schemes, though, $$\boldsymbol{n}$$ cannot be $$\ulcorner A(\underline{n})\urcorner)$$. This operation of substitution is applied here again and again.

Let us refer to the arithmetized substitution function as $$\textit{substn}(\ulcorner A(x)\urcorner , \boldsymbol{n}) = \ulcorner A(\underline{n})\urcorner$$, and let $$S(x, y, z)$$ be a formula which strongly represents this operation, as a relation, in the language of our theory $$F$$. In other words, $$S$$ is true of $$x, y$$, and $$z$$, if and only if:

$x = \ulcorner A(x)\urcorner , y = \boldsymbol{n}, \text{ and } z = \ulcorner A(\underline{n})\urcorner.$

Again, nothing prevents us from considering $$\textit{substn}(\ulcorner A(x)\urcorner , \ulcorner A(x)\urcorner)$$, or, analogously, $$S(x, x, y)$$.

Given any formula $$A(x)$$, we can now construct another formula $$\exists y[A(y) \wedge S(x, x, y)$$] with one free variable $$x$$. Let us abbreviate it as $$B(x)$$.

This formula has a Gödel number, say, $$\boldsymbol{k} = \ulcorner B(x)\urcorner$$. By substituting the numeral $$\underline{k}$$ denoting it for $$x$$ in $$B(x)$$, we get $$B(\underline{k})$$; let us call this sentence $$D$$. Looking back the chain definitions, we see that:

$D := B(\underline{k}) := \exists y[A(y) \wedge S(\underline{k}, \underline{k}, y)].$

If $$\boldsymbol{m} = \ulcorner B(\underline{k})\urcorner$$, then $$\textit{substn}(\boldsymbol{k}, \boldsymbol{k}) = \boldsymbol{m}$$, and (assuming $$F$$ contains a sufficient amount of arithmetic; $$F$$ can then also prove that the result of the arithmetized substitution function is unique)

$F \vdash \forall y[S(\underline{k},\underline{k}, y) \leftrightarrow y = \underline{m}]$

As $$\boldsymbol{k}$$ was the Gödel number of the formula $$B(x)$$ and $$\boldsymbol{m}$$ is the Gödel number of the sentence which results when $$\underline{k}$$ is substituted for $$x$$ in $$B(x)$$, i.e., $$\boldsymbol{m} = \ulcorner B(\underline{k})\urcorner$$, we can write this as:

$F \vdash \forall y[S(\underline{k},\underline{k}, y) \leftrightarrow y = \ulcorner B(\underline{k})\urcorner]$

By a little logic, we have

\begin{align} F &\vdash D \leftrightarrow \exists y[A(y) \wedge y = \ulcorner B(\underline{k})\urcorner], \text{ and from this } \\ F &\vdash D \leftrightarrow A(\ulcorner B(\underline{k})\urcorner), \text{ i.e.,} \\ F &\vdash D \leftrightarrow A(\ulcorner D\urcorner). \end{align}

This completes the proof.

For the relations of the Gödelian Diagonalization Lemma to Cantor’s method of diagonalization in set theory, see Gaifman 2006.