Lawvere's Fixed Point Theorem

The fixed point theorem Lawvere , named after the mathematician William Lawvere is a mathematical statement from the category theory . He gives a condition when objects of a category fulfill the fixed point property, and thereby generalizes sentences like Cantor's theorem or the recursion theorem .

statement

Let it be a category with finite products and an object. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle Y}$ ${\displaystyle {\mathcal {C}}}$

If there is an object and an arrow with the property ${\displaystyle A}$ ${\displaystyle g\colon A\times A\to Y}$

${\displaystyle \forall f\colon A\to Y.\ \exists c\colon \mathbf {1} \to A.\ \forall a\colon \mathbf {1} \to A.\ g\circ \langle c,a\rangle =f\circ a}$

then has the fixed point property : for each there is a "fixed point", i. H. an arrow with . ${\displaystyle Y}$ ${\displaystyle t\colon Y\to Y}$ ${\displaystyle y\colon \mathbf {1} \to Y}$ ${\displaystyle t\circ y=y}$

proof

There is and with the required quality and is arbitrary. Then there is the special arrow defined by ${\displaystyle A}$ ${\displaystyle g\colon A\times A\to Y}$ ${\displaystyle t\colon Y\to Y}$ ${\displaystyle f\colon A\to Y}$

${\displaystyle f=t\circ g\circ \langle \mathrm {id} ,\mathrm {id} \rangle }$.

For him, in turn, there is one that applies to ${\displaystyle c\colon \mathbf {1} \to A}$

${\displaystyle g\circ \langle c,c\rangle =f\circ c=t\circ g\circ \langle \mathrm {id} ,\mathrm {id} \rangle \circ c=t\circ g\circ \langle c,c\rangle }$.

That is, is fixed point of . ${\displaystyle g\circ \langle c,c\rangle }$ ${\displaystyle t}$

Inferences

• If Cartesian is closed, the transposed version can be used instead . For these, the required “property” becomes a certain form of surjectivity that is defined by means of global elements. Lawvere calls them weakly point-surjective . The statement of the sentence is then: If there is a weakly point-surjective , all endomorphisms have a fixed point. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle g\colon A\times A\to Y}$ ${\displaystyle {\tilde {g}}\colon A\to Y^{A}}$ ${\displaystyle A\to Y^{A}}$ ${\displaystyle Y}$
• In the case and one obtains Cantor's theorem by counterposing : Since it has no fixed point, there is no surjective function for any set . ${\displaystyle {\mathcal {C}}=\mathbf {Set} }$ ${\displaystyle Y=\mathbf {2} }$ ${\displaystyle \mathrm {not} \colon \mathbf {2} \to \mathbf {2} }$ ${\displaystyle A}$ ${\displaystyle A\to \mathbf {2} ^{A}={\mathcal {P}}A}$

literature

• William Lawvere : Diagonal arguments and cartesian closed categories . In: Lecture Notes in Mathematics, 92 . 1969, p. 134-145 ( reprint ).
• Noson S. Yanofsky: A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points . 2003, arxiv : math / 0305282 .