Wohlordnungen
Definition (Wohlordnung)
Eine lineare Ordnung 〈 W, < 〉 heißt eine Wohlordnung, falls jede nichtleere Teilmenge von W ein <-kleinstes Element besitzt.
Die Relation < ⊆ W2 heißt dann eine Wohlordnung auf W oder von W.
Wir unterdrücken im Folgenden oftmals wieder die Angabe der Ordnung, und nennen dann kurz W statt 〈 W, < 〉 eine Wohlordnung.
Weiter definieren wir:
Definition (Nachfolger, Supremum, Nachfolgerelement, Limeselement)
Sei W eine Wohlordnung.
(a) | Ist W ≠ ∅, so sei 0W das kleinste Element von W. 0W heißt das Anfangselement von W. |
(b) | Ist x ∈ W und gibt es ein y ∈ W mit x < y, so ist der Nachfolger von x in W, in Zeichen x + 1, definiert durch: x + 1 = „das kleinste y ∈ W mit x < y“. x heißt umgekehrt der Vorgänger von x + 1 in W. |
(c) | Ist X ⊆ W und gibt es ein y ∈ W mit X ≤ y, so ist das Supremum von X in W, in Zeichen sup(X), definiert durch: sup(X) = „das kleinste y ∈ W mit X ≤ y“. |
(d) | x ∈ W heißt ein Limeselement von W, falls x ≠ 0W und x = sup({ y ∈ W | y < x }). |
(e) | x ∈ W heißt ein Nachfolgerelement von W, falls es ein y ∈ W gibt mit x = y + 1. |
Fast offensichtlich ist:
Übung
Sei W eine Wohlordnung, und sei x ∈ W, x ≠ 0W. Dann ist x entweder ein Limeselement oder ein Nachfolgerelement von W.
Injektive Funktionen übertragen wie üblich Strukturen:
Definition (induzierte Wohlordnung)
Seien W eine Wohlordnung, M eine Menge, und sei f : M → W injektiv.
Dann heißt { (x, y) ∈ M2 | f (x) < f (y) } die von f induzierte Wohlordnung auf M.
Ist W′ ⊆ W, N eine Menge und g : W′ → N bijektiv, so heißt { (x, y) ∈ N2 | g−1(x) < g−1(y) } die von g induzierte Wohlordnung auf N.
Teilmengen einer Wohlordnung sind wohlgeordnet unter der ererbten Ordnung. Am wichtigsten sind hierunter die Anfangsstücke der Ordnung, da sie beim Vergleich zweier Wohlordnungen eine zentrale Rolle spielen:
Definition (Anfangsstück einer Wohlordnung)
Sei W eine Wohlordnung, und sei x ∈ W. Dann heißt
Wx = { y ∈ W | y < x }
das durch x gegebene Anfangsstück von W.
Definition (gleichlang und kürzer für Wohlordnungen)
Seien W1 und W2 Wohlordnungen.
(a) | W1 und W2 heißen gleichlang, falls W1 ≡ W2, d. h. falls ein Ordnungsisomorphismus zwischen W1 und W2 existiert. |
(b) | W1 heißt kürzer als W2, in Zeichen W1 ≺ W2, falls W1 gleichlang zu einem Anfangsstück von W2 ist, d. h. falls es ein x ∈ W2 gibt mit W1 ≡ (W2)x. |
Wie zu erwarten gilt:
Lemma (Wohlordnungen sind nicht gleichlang zu ihren Anfangsstücken)
Sei W eine Wohlordnung. Dann existiert kein x ∈ W mit W ≡ Wx.
Beweis
Annahme doch für ein x. Sei f : W → Wx ein Ordnungsisomorphismus.
Dann ist f (x) < x wegen f (x) ∈ Wx. Sei also y = min({ z ∈ W | f (z) < z }).
Dann ist f (y) < y, also f (f (y)) < f (y), da f Ordnungsisomorphismus.
Dann ist aber y ≤ f (y) nach Definition von y, Widerspruch.
Das Argument des Beweises zeigt auch, dass die Identität der einzige Ordnungsisomorphismus g : W → W ist. Hieraus wiederum folgt die Eindeutigkeit des Ordnungsisomorphismuses zwischen gleichlangen Wohlordnungen (!).
Es gibt darüber hinaus zwei fundamentale Sätze über Wohlordnungen. Der eine ist:
Satz (Vergleichbarkeitssatz für Wohlordnungen von Cantor)
Seien W1, W2 Wohlordnungen. Dann gilt genau einer der drei Fälle:
W1 ≺ W2 oder W1 ≡ W2 oder W2 ≺ W1.
Der Beweis, den wir hier nicht geben, verwendet das Auswahlaxiom nicht.
Der Leser versuche, eine gegebene Wohlordnung W beginnend mit ihrem kleinsten Element 0W über 0W + 1, 0W + 1 + 1, usw. zu immer größeren Elementen schrittweise zu durchwandern, und dabei zu Limeselementen zu springen, wann immer ihm die Wanderung zu langweilig wird. Wird dieses Verfahren mit zwei nebeneinander gelegten Wohlordnungen W1 und W2 simultan und gleichmäßig durchgeführt, so liefert es eine gute Intuition über die Gültigkeit des Vergleichbarkeitssatzes: Alles, was die beiden Wohlordnungen neben der speziellen Natur ihrer Elemente unterscheiden kann, ist, dass die eine evtl. früher endet als die andere. Die Entdeckung der Reichhaltigkeit des „Immerweiter“, des Springens zu immer komplexeren Limeselementen und die Frage, wie weit dieser Weg eigentlich geht, führt unmittelbar in die mathematische Grundlagenforschung.
Der zweite zentrale Satz lautet schlicht:
Satz (Wohlordnungssatz von Zermelo)
Sei M eine Menge. Dann existiert eine Wohlordnung < auf M.
Beweis
Sei P = { < | < ⊆ M2 ist eine Wohlordnung eines N ⊆ M }.
Wir ordnen P durch Inklusion. Das Zornsche Lemma findet Anwendung (!).
Sei also < ein ⊆-maximales Element von P, und sei N ⊆ M die durch < wohlgeordnete Teilmenge von M.
Dann ist N = M und damit < eine Wohlordnung auf M wie gewünscht:
Denn andernfalls existiert ein y ∈ M − N. Dann ist aber
<* = < ∪ { (x, y) | x ∈ N }, also die Enderweiterung von < um y,
ein Element von P, im Widerspruch zur Maximalität von <.
Der Wohlordnungssatz garantiert insbesondere die Existenz langer Wohlordnungen, etwa solcher auf 𝒩, ℝ oder sogar ℘(𝒩). Das Auswahlaxiom wird essentiell verwendet, wenn man z. B. eine Wohlordnung auf ℝ oder 𝒩 konstruieren will. Jedoch lässt sich die Existenz von Wohlordnungen auf gewissen großen, nun aber nicht mehr beliebigen Mengen auch ohne Auswahlaxiom zeigen. Wir werden unten eine überabzählbare Wohlordnung elementar konstruieren − eine nichttriviale Aufgabe mit einer überraschend einfachen Lösung.
Von zentraler Bedeutung in vielen Argumenten ist die Existenz einer Wohlordnung auf einer Menge M mit minimaler Länge. Allgemein gilt:
Satz (Existenz kürzester Wohlordnungen)
Sei 𝒲 eine nichtleere Menge von Wohlordnungen.
Dann existiert ein W ∈ 𝒲 mit:
(+) Für alle W′ ∈ 𝒲 gilt: W ≺ W′ oder W ≡ W′.
Beweis
Sei W ∈ 𝒲 beliebig. Gilt (+) für W, so sind wir fertig.
Andernfalls definieren wir x ∈ W durch
x = min({ y ∈ W | Wy ≡ W′ für ein W′ ∈ 𝒲 }).
Sei nun W* ∈ 𝒲 mit W* ≡ Wx. Dann ist W* wie gewünscht.
Zusammen mit dem Vergleichbarkeitssatz können wir also sagen: Die Wohlordnungen werden modulo ≡ durch ≺ wohlgeordnet. (Die Äquivalenzklassen 〈 W, < 〉/≡ sind echte Klassen, sodass diese Sprechweise etwas salopp ist.)
Korollar (Existenz von Wohlordnungen auf einer Menge mit minimaler Länge)
Sei M eine Menge. Dann existiert eine Wohlordnung < auf M mit:
Für alle x ∈ M ist |Mx| < |M|.
Beweis
Sei 𝒲 = { 〈 M, < 〉 | < ist eine Wohlordnung auf M }.
Sei 〈 M, < 〉 ∈ 𝒲 wie im Satz oben. Dann ist 〈 M, < 〉 wie gewünscht:
Denn andernfalls ist |M| = |Mx| für ein x ∈ M.
Sei dann g : M → Mx bijektiv, und sei <* die von g und der Wohlordnung 〈 Mx, < 〉 induzierte Wohlordnung auf M.
Dann ist 〈 M, <* 〉 ∈ 𝒲 und 〈 M, <* 〉 ≡ 〈 Mx, < 〉 ≺ 〈 M, < 〉, im Widerspruch zur minimalen Wahl von 〈 M, < 〉.