Fixpunktsatz von Tarski und Knaster

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Aussage[Bearbeiten]

Sei \mathcal A:=\langle A,\leq\rangle ein vollständiger Verband, f\colon A\to A monoton, und P:=\{x\in A\mid f(x)=x\} die Menge der Fixpunkte von f in A. Unter diesen Voraussetzungen ist P\neq \emptyset und \mathcal P := \langle P, \leq\rangle ebenfalls ein vollständiger Verband.

Beweisidee[Bearbeiten]

\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[Bearbeiten]

Eine oft verwendete Konsequenz ist die der Existenz von kleinsten und größten Fixpunkten von bezüglich \subseteq monotonen Funktionen.

Literatur[Bearbeiten]