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. Er wurde in der vorliegenden Allgemeinheit von Tarski 1939 gefunden^[1] und wird daher auch Fixpunktsatz von Tarski genannt.

Aussage

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

Dann ist ${\displaystyle P}$ nicht leer und ${\displaystyle {\mathcal {P}}:=\langle P,\leq _{|P}\rangle }$ ebenfalls ein vollständiger Verband.^[1]

Beweisidee

${\displaystyle \textstyle \bigcup _{\mathcal {A}}}$ sei die Supremum-Operation von ${\displaystyle {\mathcal {A}}}$, und ${\displaystyle \textstyle \bigcap _{\mathcal {A}}}$ die Infimum-Operation von ${\displaystyle {\mathcal {A}}}$.

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

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

Konsequenzen

Eine oft verwendete Konsequenz ist die der Existenz von kleinsten und größten Fixpunkten von bezüglich ${\displaystyle \subseteq }$ monoton wachsenden Abbildungen. Damit lässt sich beispielsweise der Satz von Cantor-Bernstein-Schröder leicht beweisen.^[2]

Umkehrung

Der Fixpunktsatz besitzt eine gewisse Umkehrung in einem Satz, den Anne C. Davis im Jahre 1955 vorgelegt hat:^[3][4][5]

Besitzt in einem Verband ${\displaystyle {\mathcal {A}}}$ jede monotone Abbildung ${\displaystyle f\colon {\mathcal {A}}\to {\mathcal {A}}}$ einen Fixpunkt, so ist ${\displaystyle {\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). 

Einzelnachweise

1. Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications. 1955, S. 286. 
2. Roland Uhl: Tarski's Fixed Point Theorem. In: MathWorld (englisch). Beispiel 3.
3. George Grätzer: General Lattice Theory. 1998, S. 73
4. L. A. Skornjakow: Elemente der Verbandstheorie. 1973, S. 73
5. Anne C. Davis: A characterization of complete lattices. In: Pacific Journal of Mathematics. Band 5, 1955, S. 311–319 (MR0074377).