Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Fixpunktsätze in geordneten Mengen

Eine geordnete Mengen (M,) hat die Fixpunkteigenschaft, falls jeder Homomorphismus f: M M einen Fixpunkt, d.h. ein x M mit f(x)=x, hat.

Die Frage, welche geordneten Mengen diese Fixpunkteigenschaft besitzen ist schwierig (NP-vollständig, Duffus/Goddard), aber für gewisse Klassen geordneter Mengen kann die Eigenschaft nachgewiesen werden:

[Abian/Brown 1961] Die geordnete Menge (X, ) habe die Eigenschaft, daß jede nichtleere wohlgeordnete Kette ein Supremum hat. Es gebe ein x X mit x f(x).
Dann hat (X, ) die Fixpunkteigenschaft.

Aus obigem Fixpunktsatz folgt, da in vollständigen Verbänden stets 0 f(0) gilt,

Fixpunktsatz von Knaster/Tarski Jeder vollständige Verband (V, ) hat die Fixpunkteigenschaft.
direkter Beweis

Übungsaufgabe: Beweisen Sie mit Hilfe des Fixpunktsatzes von Knaster/Tarski Banach's Decomposition Theorem: Zu je zwei Mengen A und B und je zwei Abbildungen f: A B, g: B A, gibt es eine Partition von A in A1 und A2 und eine Partition von B in B1 und B2 so daß f(A1)=B1 und g(B2)=A2 gilt. Hinweis

Die Frage nach der Fixpunkteigenschaft läßt sich auf ein Cliquenproblem in Graphen zurückführen: Zu gegebener geordneter Menge P = (M,) konstruieren wir einen Graphen G(P) wie folgt:

Hier sehen sie zwei geordnete Mengen und die dazugehörigen G(P)s.

[Schröder] Die endliche geordnete Menge P = (M,) hat genau dann die Fixpunkteigenschaft, wenn der eben definierte Graph G(P) keinen vollständigen Graphen mit |M| Ecken enthält.

Ein etwas anderer Typ ist folgender Satz. Hier ist f kein Homomorphismus, sondern vergrößert alle Elemente.
[Abian/Brown 1961, Birkhoff, Bourbaki 1950] Die geordnete Menge (X, ) habe die Eigenschaft, daß jede nichtleere wohlgeordnete Kette ein Supremum hat. f: X X sei eine Selbstabbildung, mit "x X: x f(x).
Dann hat f einen Fixpunkt. Beweis

Weiter zu ...
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.