Fixpunktsatz von Tarski und Knaster

Der Fixpunktsatz von Tarski und Knaster, benannt nach Bronisław Knaster und Alfred Tarski, ist ein mathematischer Satz aus dem Gebiet der Verbandstheorie.

Aussage

Seien ${\mathcal {A}}:=\langle A,\leq \rangle$ ein vollständiger Verband und $f\colon A\to A$ eine bzgl. $\leq$ ordnungserhaltende Abbildung und sei weiter $P:=\{x\in A\mid f(x)=x\}$ die Menge der Fixpunkte von $f$ in ${\mathcal {A}}$.

Dann ist $P$ nicht leer und ${\mathcal {P}}:=\langle P,\leq _{|P}\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 bezüglich $\subseteq$ monotonen Funktionen.

Umkehrung

Der Fixpunktsatz besitzt eine gewisse Umkehrung in einem Satz, den Anne C. Davis im Jahre 1955 vorgelegt hat:

Besitzt in einem Verband ${\mathcal {A}}$ jede monotone Abbildung $f\colon {\mathcal {A}}\to {\mathcal {A}}$ einen Fixpunkt, so ist ${\mathcal {A}}$ ein vollständiger Verband.

Literatur

• Garrett Birkhoff: Lattice Theory. 3. Auflage. American Mathematical Society, Providence, Rhode Island 1979. 
• George Grätzer: General Lattice Theory. 2. Auflage. Birkhäuser Verlag, Basel, Boston, Berlin 1998, ISBN 3-7643-5239-6 (MR1670580). 
• L. A. Skornjakow: Elemente der Verbandstheorie (= Wissenschaftliche Taschenbücher, Reihe Mathematik/Physik. Band 130). Akademie Verlag, Berlin 1973, ISBN 3-7643-5239-6. 
• Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications. In: Pacific Journal of Mathematics. Vol. 5:2, 1955, S. 285–309 (englisch, projecteuclid.org).