Lawvere's fixed-point theorem
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, Russel'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
Lawvere's theorem states that, for any cartesian closed category [math]\displaystyle{ \mathcal{C} }[/math] and given an object [math]\displaystyle{ B }[/math] in it, if there is weakly point-surjective morphism [math]\displaystyle{ f }[/math] from some object [math]\displaystyle{ A }[/math] to the exponential object [math]\displaystyle{ A^B }[/math], then every endomorphism[math]\displaystyle{ g: B \rightarrow B }[/math] has a fixed point. That is, there exists a morphism [math]\displaystyle{ s : 1 \rightarrow B }[/math] (where [math]\displaystyle{ 1 }[/math] is a terminal object in [math]\displaystyle{ \mathcal{C} }[/math] ) such that [math]\displaystyle{ g \circ s = s }[/math].
Applications
The theorem's contrapositive is particularly useful in proving many results. It states that if there is an object [math]\displaystyle{ B }[/math] in the category such that there is an endomorphism [math]\displaystyle{ g: B \rightarrow B }[/math] which has no fixed points, then there is no object [math]\displaystyle{ A }[/math] with a point-surjective map [math]\displaystyle{ f : A \rightarrow A^B }[/math]. Some important corolaries of this are:[2]
- 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
References
- ↑ Soto-Andrade, Jorge; J. Varela, Francisco (1984). "Self-Reference and Fixed Points: A Discussion and an Extension of Lawvere's Theorem". Acta Applicandae Mathematicae 2. doi:10.1007/BF01405490. https://link.springer.com/article/10.1007/BF01405490.
- ↑ 2.0 2.1 Yanofsky, Noson (September 2003). "A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points". The Bulletin of Symbolic Logic 9 (3): 362–386. doi:10.2178/bsl/1058448677.
- ↑ Lawvere, Francis William (1969). "Diagonal arguments and Cartesian closed categories". Category Theory, Homology Theory and their Applications II (Lecture Notes in Mathematics, vol 92). Berlin: Springer. https://link.springer.com/chapter/10.1007/BFb0080769.
- ↑ Lawvere, William (2006). "Diagonal arguments and cartesian closed categories with author commentary". Reprints in Theory and Applications of Categories (15): 1–13. http://tac.mta.ca/tac/reprints/articles/15/tr15abs.html.
 |  |
