Supplement to Gödel’s Incompleteness Theorems
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 n are given, the operation of constructing the formula where the numeral for n has been substituted for the (free occurrences of the) variable x, that is, A(n), is purely mechanical. So is the analogous arithmetical operation which produces, given the Gödel number of a formula (with one free variable) ^{⌈}A(x)^{⌉} and of a number n, the Gödel number of the formula in which the numeral n has been substituted for the variable in the original formula, that is, ^{⌈}A(n)^{⌉}. The latter operation can be expressed in the language of arithmetic. Note, in particular, that nothing prevents n from being the Gödel number of A(x) itself, that is, ^{⌈}A(x)^{⌉} (in the usual coding schemes, though, n cannot be ^{⌈}A(n)^{⌉}). This operation of substitution is applied here again and again.
Let us refer to the arithmetized substitution function as substn(^{⌈}A(x)^{⌉}, n) = ^{⌈}A(n)^{⌉}, 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 = ^{⌈}A(x)^{⌉}, y = n, and z = ^{⌈}A(n)^{⌉}.
Again, nothing prevents us from considering substn(^{⌈}A(x)^{⌉}, ^{⌈}A(x)^{⌉}), or, analogously, S(x, x, y).
Given any formula A(x), we can now construct another formula ∃y[A(y) ∧ S(x, x, y)] with one free variable x. Let us abbreviate it as B(x).
This formula has a Gödel number, say, k = ^{⌈}B(x)^{⌉}. By substituting the numeral k denoting it for x in B(x), we get B(k); let us call this sentence D. Looking back the chain definitions, we see that:
- D := B(k) := ∃y[A(y) ∧ S(k, k, y)].
If m = ^{⌈}B(k)^{⌉}, then substn(k, k) = 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 ⊢ ∀y[S(k,k, y) ↔ y = m]
As k was the Gödel number of the formula B(x) and m is the Gödel number of the sentence which results when k is substituted for x in B(x), i.e., m = ^{⌈}B(k)^{⌉}, we can write this as:
- F ⊢ ∀y[S(k,k, y) ↔ y = ^{⌈}B(k)^{⌉}]
By a little logic, we have
- F ⊢ D ↔ ∃y[A(y) ∧ y = ^{⌈}B(k)^{⌉}], and from this
- F ⊢ D ↔ A(^{⌈}B(k)^{⌉}), i.e.,
- F ⊢ D ↔ A(^{⌈}D^{⌉}).
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.