Lawvere's fixed-point theorem

In mathematics, the 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, Russel's paradox, Gödel's first incompleteness theorem and Turing's solution to the Entscheidungsproblem.

It was first proven by William Lawvere in 1969.

Statement

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

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\rightarrow B$ which has no fixed points, then there is no object $A$ with a point-surjective map $f:A\rightarrow A^{B}$. Some important corolaries 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