Fixpunktsatz von Lawvere

Der Fixpunktsatz von Lawvere, benannt nach dem Mathematiker William Lawvere, ist eine mathematische Aussage aus der Kategorientheorie. Er gibt eine Bedingung, wann Objekte einer Kategorie die Fixpunkteigenschaft erfüllen, und verallgemeinert damit Sätze wie den Satz von Cantor oder den Rekursionssatz.

Aussage

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

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

$\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 $Y$ die Fixpunkteigenschaft: für jedes $t\colon Y\to Y$ gibt es einen „Fixpunkt“, d. h. einen Pfeil $y\colon \mathbf {1} \to Y$ mit $t\circ y=y$.

Beweis

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

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

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

$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, $g\circ \langle c,c\rangle$ ist Fixpunkt von $t$.

Folgerungen

• Wenn ${\mathcal {C}}$ kartesisch abgeschlossen ist, kann statt $g\colon A\times A\to Y$ dessen transponierte Version ${\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 $A\to Y^{A}$ gibt, haben alle Endomorphismen auf $Y$ einen Fixpunkt.
• Im Fall ${\mathcal {C}}=\mathbf {Set}$ und $Y=\mathbf {2}$ erhält man den Satz von Cantor per Kontraposition: Da $\mathrm {not} \colon \mathbf {2} \to \mathbf {2}$ keinen Fixpunkt hat, gibt es für keine Menge $A$ eine surjektive Funktion $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.