DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

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 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.

[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.

[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