Wohlordnung

mathematische Eigenschaft

Eine Wohlordnung auf einer Menge ist eine totale Ordnung, bei der jede nichtleere Teilmenge von ein kleinstes Element bezüglich dieser Ordnung hat, also eine totale fundierte Ordnung. Das Paar der Menge zusammen mit der Wohlordnung heißt dann eine wohlgeordnete Struktur oder unpräzise eine wohlgeordnete Menge, wobei die Ordnung implizit ist. Die Begriffe stammen aus der Mengenlehre von Cantor.

EigenschaftenBearbeiten

In einer wohlgeordneten Struktur   gibt es keine unendlich lange absteigende Kette, d. h. keine unendliche Folge   in  , sodass für alle   gilt  . Unter Verwendung des Axioms der abhängigen Auswahl folgt auch die Umkehrung: Wenn es in   keine unendliche absteigende Folge (bezüglich  ) gibt, so ist   eine wohlgeordnete Struktur.

Im Kontext einer Wohlordnung gibt es die Begriffe von (direktem/unmittelbarem) Vorgänger und (direktem/unmittelbarem) Nachfolger.[Anm. 1] Für   heißt   der Vorgänger von   und gleichwertig   der Nachfolger von  , falls zwischen   und   keine Elemente liegen. In einer wohlgeordneten Menge gibt es stets mindestens ein Element ohne Vorgänger, unter anderem das kleinste Element von   selbst. Der Nachfolger eines Elements ist immer eindeutig bestimmt: Falls er existiert, ist er das eindeutige Minimum der Menge der Elemente, die größer sind. Es kann höchstens ein größtes Element geben, das keinen Nachfolger hat. Mehrere Elemente ohne Nachfolger sind nicht möglich. Dagegen kann es beliebig viele Elemente ohne direkten Vorgänger geben.

Wenn eine Menge wohlgeordnet ist, dann kann die Technik der transfiniten Induktion genutzt werden, um zu zeigen, dass eine gegebene Aussage für alle Elemente dieser Menge zutrifft. Die vollständige Induktion ist ein Spezialfall der transfiniten Induktion.

Der Wohlordnungssatz besagt, dass jede Menge wohlgeordnet werden kann. Unter Zugrundelegung der übrigen mengentheoretischen Axiome ist dieser Satz äquivalent zum Auswahlaxiom.

Der einzige Isomorphismus einer Wohlordnung (Ordnungsisomorphismus) auf sich selbst ist die Identität, und eine Wohlordnung ist niemals isomorph zu einem echten Anfangssegment ihrer selbst. Zwei Wohlordnungen sind entweder isomorph, oder genau eine ist isomorph zu einem echten Anfangssegment der anderen. Die jeweiligen Isomorphismen sind dann eindeutig. Betrachtet man nun die Äquivalenzklassen bezüglich Isomorphie, so gibt es in jeder einen kanonischen Vertreter, die zugehörige Ordinalzahl. Jede Wohlordnung ist also isomorph zu genau einer Ordinalzahl. Die Klasse der Ordinalzahlen selbst ist auch wohlgeordnet.[1]

Anmerkungen

  1. Manchmal werden alle Elemente, die kleiner als das betrachtete Element sind, als die Vorgänger bezeichnet, also auch die indirekten (= mittelbaren); analog für Nachfolger. Siehe Ordnungsrelation §Vorgänger und Nachfolger.
    Wiebke Petersen: Mathematische Grundlagen der Computerlinguistik – Ordnungsrelationen, 4. Foliensatz, Heinrich-Heine-Universität Düsseldorf, Institute of Language and Information, PDF: WS 2011/12 S. 93 WS 2013/14 S. 90, abgerufen am 21. April 2018.

BeispieleBearbeiten

Einfache Beispiele und GegenbeispieleBearbeiten

Die normale Anordnung der natürlichen Zahlen ist bereits eine Wohlordnung, aber weder die normale Anordnung der ganzen Zahlen noch die der positiven reellen Zahlen ist eine Wohlordnung.

Auf einer endlichen Menge   ist mit   eine Wohlordnung definiert. Gilt aber auch noch  , so gibt es einen Zyklus und es liegt keine Wohlordnung mehr vor.

Mehrere Elemente ohne VorgängerBearbeiten

Die natürlichen Zahlen sollen so geordnet sein, dass jede gerade Zahl größer ist als jede ungerade Zahl. Untereinander sollen die geraden und die ungeraden Zahlen wie üblich geordnet sein, also in der folgenden Art:

 

Offenbar ist das eine wohlgeordnete Menge: Enthält eine Teilmenge irgendwelche ungeraden Zahlen, so ist die kleinste von ihnen auch kleinste Zahl der Teilmenge (alle geraden Zahlen sind größer); enthält sie nur gerade Zahlen, so ist die kleinste aus diesen auch die kleinste im Sinne der Wohlordnung, denn ungerade Zahlen, die kleiner wären, sind ja nicht vorhanden. Die Ordinalzahl zu dieser Wohlordnung wird üblicherweise mit   oder   bezeichnet. Es gibt hier kein größtes Element, aber zwei Elemente ohne Vorgänger: die Eins und die Zwei.

Wohlgeordnete KlassenBearbeiten

Die obige Definition lässt sich wie folgt auf Klassen erweitern:

Eine wohlgeordnete Klasse ist eine Klasse   mit einer fundierten linearen Ordnung < auf  , die vorgängerklein ist. Das bedeutet, dass für alle   die Klasse   der Vorgänger von   eine Menge (d. h. keine eigentliche Klasse) ist.[2]

LiteraturBearbeiten

ReferenzenBearbeiten

  1. Thomas Jech: Set Theory. Hrsg.: Samuel Eilenberg und Hyman Bass. 1. Auflage. Academic Press Inc., 1978, ISBN 0-12-381950-4, S. 13–14 (englisch).
  2. Martin Ziegler: Vorlesung über Mengenlehre, Universität Freiburg, 1992–2014, Seite 12