> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/300-logic/terms/diagonal-lemma.md).

# 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