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
![P \vdash \psi\leftrightarrow\phi([\psi])](../../../math/2/7/3/27300b42a2188aa488ae6d8d3c9bcab4.png)
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.
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
