Diagonal lemma

https://en.wikipedia.org/wiki/Diagonal_lemma

In mathematical logic, the diagonal lemma establishes the existence of self-referential sentences in certain formal theories of the natural numbers - specifically those theories that are strong enough to represent all computable functions.

The sentences whose existence is secured by the diagonal lemma can then, in turn, be used to prove fundamental limitative results such as Gödel's incompleteness theorems and Tarski's undefinability theorem.

AKA: diagonalization lemma, self-reference lemma, fixed point theorem

Last updated