Fixpunktsatz von Tarski und Knaster

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Fixpunktsatz von Tarski und Knaster, benannt nach Bronisław Knaster und Alfred Tarski, ist ein mathematischer Satz aus dem Gebiet der Verbandstheorie. Er wurde in der vorliegenden Allgemeinheit von Tarski 1939 gefunden[1] und wird daher auch Fixpunktsatz von Tarski genannt.

Seien ein vollständiger Verband und eine bzgl. ordnungserhaltende Abbildung und sei weiter die Menge der Fixpunkte von in .

Dann ist nicht leer und ebenfalls ein vollständiger Verband.[1]

sei die Supremum-Operation von , und die Infimum-Operation von .

Die folgenden Schritte zeigen, dass für beliebige Teilmengen von ein Infimum und ein Supremum in liefert.

  1. ist Fixpunkt von , und zwar der größte in . Somit ist dies das -Supremum von .
  2. Dual zu Schritt 1: ist Fixpunkt von , und zwar der kleinste in .
  3. Für beliebige Teilmengen soll es ein -Supremum geben. Die Fälle 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 eine monotone Funktion ist, die nach Schritt 2 einen kleinsten Fixpunkt in hat. Dieser ist das -Supremum von . In Formeln: .
  4. Dual zu Schritt 3 wird gezeigt, dass beliebige Teilmengen von ein -Infimum haben.

Eine oft verwendete Konsequenz ist die der Existenz von kleinsten und größten Fixpunkten von bezüglich monoton wachsenden Abbildungen. Damit lässt sich beispielsweise der Satz von Cantor-Bernstein-Schröder leicht beweisen.[2]

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

Besitzt in einem Verband jede monotone Abbildung einen Fixpunkt, so ist ein vollständiger Verband.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications. 1955, S. 286.
  2. Roland Uhl: Tarski's Fixed Point Theorem. In: MathWorld (englisch). Beispiel 3.
  3. George Grätzer: General Lattice Theory. 1998, S. 73
  4. L. A. Skornjakow: Elemente der Verbandstheorie. 1973, S. 73
  5. Anne C. Davis: A characterization of complete lattices. In: Pacific Journal of Mathematics. Band 5, 1955, S. 311–319 (MR0074377).