Wohlordnung

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

Eigenschaften

In einer wohlgeordneten Struktur $(S,<)$ gibt es keine unendlich lange absteigende Kette, d. h. keine unendliche Folge $(a_{i})_{i\in \mathbb {N} }$ in $S$ , sodass für alle $i$ gilt $a_{i+1}<a_{i}$ . Unter Verwendung des Axioms der abhängigen Auswahl folgt auch die Umkehrung: Wenn es in $S$ keine unendliche absteigende Folge (bezüglich ${<}$ ) gibt, so ist $(S,<)$ eine wohlgeordnete Struktur.

Im Kontext einer Wohlordnung gibt es die Begriffe von (direktem/unmittelbarem) Vorgänger und (direktem/unmittelbarem) Nachfolger.^{[Anm. 1]} Für $a<b$ heißt $a$ der Vorgänger von $b$ und gleichwertig $b$ der Nachfolger von $a$ , falls zwischen $a$ und $b$ keine Elemente liegen. In einer wohlgeordneten Menge gibt es stets mindestens ein Element ohne Vorgänger, unter anderem das kleinste Element von $S$ 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

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

Beispiele

Einfache Beispiele und Gegenbeispiele

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 $\{x_{1},\dots ,x_{n}\}$ ist mit $x_{i}<x_{i+1}$ eine Wohlordnung definiert. Gilt aber auch noch $x_{n}<x_{1}$ , so gibt es einen Zyklus und es liegt keine Wohlordnung mehr vor.

Mehrere Elemente ohne Vorgänger

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:

1<3<5<\cdots \;<\;2<4<6<\cdots

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 $\omega +\omega$ oder $\omega \cdot 2$ bezeichnet. Es gibt hier kein größtes Element, aber zwei Elemente ohne Vorgänger: die Eins und die Zwei.

Wohlgeordnete Klassen

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

Eine wohlgeordnete Klasse ist eine Klasse $S$ mit einer fundierten linearen Ordnung < auf $S$ , die vorgängerklein ist. Das bedeutet, dass für alle $b\in S$ die Klasse $\{a\in S|a<b\}$ der Vorgänger von $b$ eine Menge (d. h. keine eigentliche Klasse) ist.^[2]

Literatur

Oliver Deiser: Einführung in die Mengenlehre, Springer, 2004, ISBN 978-3-540-20401-5, Seiten 222–230

Einzelnachweise

↑ 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).
↑ Martin Ziegler: Vorlesung über Mengenlehre, Universität Freiburg, 1992–2014, Seite 12

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

[2] 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).

[3] Martin Ziegler: Vorlesung über Mengenlehre, Universität Freiburg, 1992–2014, Seite 12

[Anm. 1]

[1]

[2]