Fixpunktsatz von Tarski und Knaster
# 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

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \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.

* $\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$.
* 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$.
* 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\}$.
* 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.

