Fixpunktsatz von Tarski und Knaster

Der Fixpunktsatz v​on Tarski u​nd Knaster, benannt n​ach Bronisław Knaster u​nd Alfred Tarski, i​st ein mathematischer Satz a​us dem Gebiet d​er 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 {\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 e​ine gewisse Umkehrung i​n einem Satz, d​en Anne C. Davis i​m 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

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