- Fixpunktsatz von Tarski und Knaster
-
Der Fixpunktsatz von Tarski und Knaster, benannt nach Bronisław Knaster und Alfred Tarski, ist ein Satz aus der Ordnungstheorie.
Inhaltsverzeichnis
Aussage
Sei
ein vollständiger Verband,
monoton, und
die Menge der Fixpunkte von f in A. Unter diesen Voraussetzungen ist
ebenfalls ein vollständiger Verband.
Beweisidee
sei die Supremum-Operation von
, und
die Infimum-Operation von
.
Die folgenden Schritte zeigen, dass
für beliebige Teilmengen von P ein Infimum und ein Supremum in P liefert.
ist Fixpunkt von f, und zwar der größte in A. Somit ist dies das
-Supremum von P.
- Dual zu Schritt 1:
ist Fixpunkt von f, und zwar der kleinste in A.
- Für beliebige Teilmengen
, soll es ein
-Supremum geben. Die Fälle Y = P und
sind bereits in den Schritten 1 und 2 gezeigt. Betrachtet werden nun die anderen Fälle. Dazu wird ausgenutzt, dass
mit
wieder ein vollständiger Verband ist, und f | U eine monotone Funktion
ist, die nach Schritt 2 einen kleinsten Fixpunkt in U hat. Dieser ist das
-Supremum von Y. In Formeln:
.
- Dual zu Schritt 3 wird gezeigt, dass beliebige Teilmengen von P ein
-Infimum haben.
Konsequenzen
Eine oft verwendete Konsequenz ist die der Existenz von kleinsten und größten Fixpunkten von monotonen Funktionen, welche die Ordnung einer halbgeordneten Menge respektieren.
Literatur
Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications. In: Pacific Journal of Mathematics. 5:2, 1955, S. 285–309.
Wikimedia Foundation.