DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

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 A₁ und A₂ und eine Partition von B in B₁ und B₂ so daß f(A₁)=B₁ und g(B₂)=A₂ 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:

• Eckenmenge ist die Menge aller geordneten Paare (x,y), x y M, wobei x und y unvergleichbar sind.
• (x,y) und (x',y') sind benachbart in G(P) falls gilt: Aus x x' folgt y y', und aus x' x folgt y' y.

.

[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