Fixpunktsatz von Lawvere

Der Fixpunktsatz v​on Lawvere, benannt n​ach dem Mathematiker William Lawvere, i​st eine mathematische Aussage a​us der Kategorientheorie. Er g​ibt eine Bedingung, w​ann Objekte e​iner Kategorie d​ie Fixpunkteigenschaft erfüllen, u​nd verallgemeinert d​amit Sätze w​ie den Satz v​on Cantor o​der den Rekursionssatz.

Aussage

Es sei ${\displaystyle {\mathcal {C}}}$ eine Kategorie mit endlichen Produkten und ${\displaystyle Y}$ ein ${\displaystyle {\mathcal {C}}}$-Objekt.

Wenn es ein Objekt ${\displaystyle A}$ und einen Pfeil ${\displaystyle g\colon A\times A\to Y}$ mit der Eigenschaft

${\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}$

gibt, dann hat ${\displaystyle Y}$ die Fixpunkteigenschaft: für jedes ${\displaystyle t\colon Y\to Y}$ gibt es einen „Fixpunkt“, d. h. einen Pfeil ${\displaystyle y\colon \mathbf {1} \to Y}$ mit ${\displaystyle t\circ y=y}$.

Beweis

Es gebe ${\displaystyle A}$ und ${\displaystyle g\colon A\times A\to Y}$ mit der geforderten Eigenschaft und ${\displaystyle t\colon Y\to Y}$ sei beliebig. Es gibt dann den speziellen Pfeil ${\displaystyle f\colon A\to Y}$, definiert durch

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

Für ihn wiederum gibt es ein ${\displaystyle c\colon \mathbf {1} \to A}$, für das gilt

${\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 }$.

Das heißt, ${\displaystyle g\circ \langle c,c\rangle }$ ist Fixpunkt von ${\displaystyle t}$.

Folgerungen

• Wenn ${\displaystyle {\mathcal {C}}}$ kartesisch abgeschlossen ist, kann statt ${\displaystyle g\colon A\times A\to Y}$ dessen transponierte Version ${\displaystyle {\tilde {g}}\colon A\to Y^{A}}$ herangezogen werden. Für diese wird die geforderte „Eigenschaft“ zu einer gewissen Form der Surjektivität, die mittels globalen Elementen definiert ist. Lawvere nennt sie weakly point-surjective. Die Aussage des Satzes ist dann: Wenn es ein weakly point-surjective ${\displaystyle A\to Y^{A}}$ gibt, haben alle Endomorphismen auf ${\displaystyle Y}$ einen Fixpunkt.
• Im Fall ${\displaystyle {\mathcal {C}}=\mathbf {Set} }$ und ${\displaystyle Y=\mathbf {2} }$ erhält man den Satz von Cantor per Kontraposition: Da ${\displaystyle \mathrm {not} \colon \mathbf {2} \to \mathbf {2} }$ keinen Fixpunkt hat, gibt es für keine Menge ${\displaystyle A}$ eine surjektive Funktion ${\displaystyle A\to \mathbf {2} ^{A}={\mathcal {P}}A}$.

Literatur

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