Lawvere's fixed-point theorem

Template:Short description In mathematics, Lawvere's fixed-point theorem is an important result in category theory. It is a broad abstract generalization of many diagonal arguments in mathematics and logic, such as Cantor's diagonal argument, Cantor's theorem, Russell's paradox, Gödel's first incompleteness theorem, Turing's solution to the Entscheidungsproblem, and Tarski's undefinability theorem.

It was first proven by William Lawvere in 1969.

Statement

Lawvere's theorem states that, for any Cartesian closed category $𝐂$ and given an object $B$ in it, if there is a weakly point-surjective morphism $f$ from some object $A$ to the exponential object $B^A$, then every endomorphism $g:B\to B$ has a fixed point. That is, there exists a morphism $b:1\to B$ (where $1$ is a terminal object in $𝐂$ ) such that $g\circ b=b$.

This can be further generalized to a much broader class of categories. Let $𝐂$ be a category equipped with a functor $\mathrm{♯}:𝐂\times 𝐂\to 𝐂$, a chosen object $t$, and natural transformation $\delta :i{d}_{𝐂}\Rightarrow \mathrm{♯}\circ {\mathrm{\Delta }}_C$. Let $F:A\mathrm{♯}A\to C$ and $\sigma :C\to C$ be morphisms in $𝐂$ such that, $\mathrm{\exists }{a}_0:t\to A,\mathrm{\forall }a:t\to A$, such that $\sigma \circ F\circ {\delta }_A\circ a=F\circ (a_0\mathrm{♯}a)\circ {\delta }_t$. Then the map $c:=F\circ \delta \circ a_0:t\to C$ satisfies $\sigma \circ c=c$.

Applications

The theorem's contrapositive is particularly useful in proving many results. It states that if there is an object $B$ in the category such that there is an endomorphism $g:B\to B$ that has no fixed points, then there is no object $A$ with a weakly point-surjective map $f:A\to B^A$. Some important corollaries of this are:

• Cantor's theorem
• Cantor's diagonal argument
• Diagonal lemma
• Russell's paradox
• Gödel's first incompleteness theorem
• Tarski's undefinability theorem
• Turing's proof
• Löb's paradox
• Roger's fixed-point theorem
• Rice's theorem