View source for Lawvere's fixed-point theorem

{{short description|Theorem in category theory}}
In [[Mathematics|mathematics]], '''Lawvere's fixed-point theorem''' is an important result in [[Category theory|category theory]].<ref>{{cite journal |last1=Soto-Andrade |first1=Jorge |last2=J. Varela |first2=Francisco |title=Self-Reference and Fixed Points: A Discussion and an Extension of Lawvere's Theorem |journal=Acta Applicandae Mathematicae |date=1984 |volume=2 |doi=10.1007/BF01405490 |url=https://link.springer.com/article/10.1007/BF01405490}}</ref> 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 proof|Turing's solution to the Entscheidungsproblem]].<ref name = "yanofsky">{{cite journal |last1=Yanofsky |first1=Noson |title=A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points |journal=The Bulletin of Symbolic Logic |date=September 2003 |volume=9 |issue=3 |pages=362–386 |doi=10.2178/bsl/1058448677}}</ref>

It was first proven by [[Biography:William Lawvere|William Lawvere]] in 1969.<ref>{{cite book |last1=Lawvere |first1=Francis William |title=Category Theory, Homology Theory and their Applications II (Lecture Notes in Mathematics, vol 92) |date=1969 |publisher=Springer |location=Berlin |url=https://link.springer.com/chapter/10.1007/BFb0080769 |chapter=Diagonal arguments and Cartesian closed categories}}</ref><ref>{{cite journal |last1=Lawvere |first1=William |author1-link=William Lawvere |title=Diagonal arguments and cartesian closed categories with author commentary |journal=Reprints in Theory and Applications of Categories |date=2006 |issue=15 |pages=1–13 |url=http://tac.mta.ca/tac/reprints/articles/15/tr15abs.html}}</ref>

== Statement ==
Lawvere's theorem states that, for any [[Cartesian closed category|cartesian closed category]] <math>\mathcal{C}</math> and given an object <math>B</math> in it, if there is weakly point-surjective [[Morphism|morphism]] <math>f</math>  from some object <math>A</math> to the [[Exponential object|exponential object]] <math>A^B</math>, then every [[Endomorphism|endomorphism]]<math>g: B \rightarrow B</math> has a fixed point. That is, there exists a morphism <math> s : 1 \rightarrow B</math> (where <math>1</math> is a terminal object in <math>\mathcal{C}</math> ) such that <math>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>B</math> in the category such that there is an endomorphism <math>g: B \rightarrow B</math> which has no fixed points, then there is no object <math>A</math> with a point-surjective map <math>f : A \rightarrow A^B </math>. Some important corolaries of this are:<ref name="yanofsky" /> 
* [[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
* [[Kleene's recursion theorem#Rogers's fixed-point theorem|Roger's fixed-point theorem]]
* [[Rice's theorem]]

==References==
{{Reflist}}

[[Category:Category theory]]
[[Category:Mathematical theorems]]

{{Sourceattribution|Lawvere's fixed-point theorem}}