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

  • FD ↔ ∃y[A(y) ∧ y = B(k)], and from this
  • FDA(B(k)), i.e.,
  • FDA(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.

Copyright © 2015 by
Panu Raatikainen <panu.raatikainen@helsinki.fi>

Open access to the SEP is made possible by a world-wide funding initiative.
Please Read How You Can Help Keep the Encyclopedia Free