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

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 }$ monotonen Funktionen.

Umkehrung

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

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

• 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). 
• 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. 

Einzelnachweise

1. ↑ George Grätzer: General Lattice Theory. 1998, S. 73
2. ↑ L. A. Skornjakow: Elemente der Verbandstheorie. 1973, S. 73
3. ↑ Anne C. Davis: A characterization of complete lattices. In: Pacific Journal of Mathematics. Band 5, 1955, S. 311–319 (MR0074377).