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.
Dann hat jeder Homomorphismus f von X in X, zu dem es ein x X mit x f(x) gibt, einen Fixpunkt. |
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:
.
[B. Schröder 97] 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. |
[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 |