Diagonalization lemma
From Wikipedia, the free encyclopedia
In mathematical logic, the diagonalization lemma states that for any well formed formula φ(x)
with a free variable x, there is a sentence ψ such that
where [ψ] is the Gödel number for ψ.
Informally, the diagonalization lemma states that ψ can refer to itself in any (first-order) way it wishes. Notice the similarity between the diagonalization lemma and Kleene's recursion theorem.
Gödel's first incompleteness theorem can be proved via the diagonalization lemma.
It takes its name from Cantor's diagonal argument to prove that the real numbers are uncountable.