Fixpunktsatz von Tarski und Knaster

Der Fixpunktsatz von Tarski und Knaster, benannt nach Bronisław Knaster und Alfred Tarski, ist ein Satz aus der Ordnungstheorie.

Aussage

Sei $\mathcal A:=\langle A,\leq\rangle$ ein vollständiger Verband, $f\colon A\to A$ monoton, und $P:=\{x\in A\mid f(x)=x\}$ die Menge der Fixpunkte von f in A. Unter diesen Voraussetzungen ist $\mathcal P := \langle P, \leq\rangle$ ebenfalls ein vollständiger Verband.

Beweisidee

$\textstyle\bigcup_\mathcal A$ sei die Supremum-Operation von $\mathcal A$, und $\textstyle\bigcap_\mathcal A$ die Infimum-Operation von $\mathcal A$.

Die folgenden Schritte zeigen, dass $\mathcal P$ für beliebige Teilmengen von P ein Infimum und ein Supremum in P liefert.

1. $\textstyle\bigcup_\mathcal A \{x\in A\mid x\leq f(x)\}$ ist Fixpunkt von f, und zwar der größte in A. Somit ist dies das $\mathcal P$-Supremum von P.
2. Dual zu Schritt 1: $\textstyle\bigcap_\mathcal A \{x\in A\mid f(x)\leq x\}$ ist Fixpunkt von f, und zwar der kleinste in A.
3. Für beliebige Teilmengen $Y\subseteq P$, soll es ein $\mathcal P$-Supremum geben. Die Fälle Y = P und $Y=\emptyset$ sind bereits in den Schritten 1 und 2 gezeigt. Betrachtet werden nun die anderen Fälle. Dazu wird ausgenutzt, dass $\langle U,\leq\rangle$ mit $\textstyle U := \{x\in A\mid \bigcup_\mathcal A Y\leq x\}$ wieder ein vollständiger Verband ist, und f | _U eine monotone Funktion $U\to U$ ist, die nach Schritt 2 einen kleinsten Fixpunkt in U hat. Dieser ist das $\mathcal P$-Supremum von Y. In Formeln: $\textstyle\bigcup_\mathcal P Y := \bigcap_\mathcal A\{x\in A\mid \bigcup_\mathcal A Y \cup f(x)\ \leq\ x\}$.
4. Dual zu Schritt 3 wird gezeigt, dass beliebige Teilmengen von P ein $\mathcal P$-Infimum haben.

Konsequenzen

Eine oft verwendete Konsequenz ist die der Existenz von kleinsten und größten Fixpunkten von monotonen Funktionen, welche die Ordnung einer halbgeordneten Menge respektieren.

Literatur

Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications. In: Pacific Journal of Mathematics. 5:2, 1955, S. 285–309.