Lawvere's fixed-point theorem explained

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

It was first proven by William Lawvere in 1969.^{[3] [4]}

Statement

C 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 → B has a fixed point. That is, there exists a morphism b : 1 → B (where 1 is a terminal object in C ) such that g \circ b = b .

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 → B which has no fixed points, then there is no object A with a weakly point-surjective map f : A → 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

Notes and References

1. Soto-Andrade . Jorge . J. Varela . Francisco . Self-Reference and Fixed Points: A Discussion and an Extension of Lawvere's Theorem . Acta Applicandae Mathematicae . 1984 . 2 . 10.1007/BF01405490 .
2. Yanofsky . Noson . A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points . The Bulletin of Symbolic Logic . September 2003 . 9 . 3 . 362–386 . 10.2178/bsl/1058448677. math/0305282 .
3. Book: Lawvere . Francis William . William Lawvere . Category Theory, Homology Theory and their Applications II (Lecture Notes in Mathematics, vol 92) . 1969 . Springer . Berlin . Diagonal arguments and Cartesian closed categories.
4. Lawvere . William . William Lawvere . Diagonal arguments and cartesian closed categories with author commentary . Reprints in Theory and Applications of Categories . 2006 . 15 . 1–13 .