Abzählbare Ordinalzahlen und ω1
Ordinalzahlen sind der traditionellen Intuition zufolge „das Gemeinsame“ aller Wohlordnungen gleicher Länge. Die Ordinalzahlen, die zu den unendlichen Wohlordnungen gehören, adelt man dann romantisch mystifizierend als „transfinite Zahlen“. Wir stehen hier vor ähnlichen Problemen wie bei der Definition einer Kardinalzahl κ. Die gröbste Methode wäre, die Elemente einer beliebigen, aber fixierten überabzählbaren wohlgeordneten Menge als Ordinalzahlen zu bezeichnen, was für ein Segment der transfiniten Theorie im Prinzip ausreichen würde. Neben einiger Willkür würde hier durch den Rückgriff auf den Wohlordnungssatz aber das Auswahlaxiom in die Definition der Ordinalzahlen einfließen, und dies verschleiert dann insbesondere das Phänomen der pathologischen Mengen: Nicht die Existenz gewisser langer Wohlordnungen ist es, die pathologische Mengen im Schlepptau nach sich zieht, sondern erst die Existenz von Wohlordnungen auf beliebigen Mengen, wie etwa ℝ, erzeugt diejenigen Mengen, die so ganz anders sind als alles, was man sonst kennt.
Wir führen deswegen und aus sachlich-ästhetischen Gründen die Ordinalzahlen bis ω1 mit einer auswahlfreien Methode ein, die zudem in der Mengenlehre eine unabhängige Bedeutung hat. Unser Objekt ω1 ist, wie oben erwähnt, nicht das übliche ω1, aber es ist alles andere als willkürlich.
Definition (abzählbare Ordinalzahlen und ω1 nach der „Hartogsmethode“)
Sei ℋ = { 〈 N, < 〉 | 〈 N, < 〉 ist eine Wohlordnung und N ⊆ ℕ }.
Dann ist „gleichlang“ eine Äquivalenzrelation auf ℋ und wir setzen
ω1 = ℋ/≡ .
Jedes α ∈ ω1 heißt eine abzählbare Ordinalzahl. Ein α ∈ ω1 heißt zudem eine (abzählbare) transfinite Zahl, falls die Elemente von α unendlich sind.
ω1 selbst heißt die erste überabzählbare Ordinalzahl.
Auf der Menge ω1 können wir sehr einfach eine Ordnung definieren:
Definition (die natürliche Ordnung auf den abzählbaren Ordinalzahlen, W(α))
Für α, β ∈ ω1 setzen wir:
α < β falls jedes Element von α ist kürzer als jedes Element von β.
Diese Relation < heißt die natürliche Ordnung auf ω1.
Für α ∈ ω1 setzen wir:
W(α) = (ω1)α = { β ∈ ω1 | β < α }.
Wir schreiben weiter auch α < ω1 für α ∈ ω1.
Es gilt nun der folgende Satz:
Satz (über ω1 = ℋ/≡ )
〈 ω1, < 〉 ist eine überabzählbare Wohlordnung.
Für alle α ∈ ω1 gilt:
(+) 〈 W(α), < 〉 ≡ 〈 N, < 〉 für alle 〈 N, < 〉 ∈ α.
Insbesondere ist W(α) abzählbar für alle α ∈ ω1.
Wir schreiben Elemente von ω1 im Folgenden oft kurz als N/≡ statt 〈 N, < 〉/≡ . Dies dient lediglich der Vereinfachung der Notation.
Beweis
〈 ω1, < 〉 ist eine lineare Ordnung:
Dies folgt sofort aus dem Vergleichbarkeitssatz.
〈 ω1, < 〉 ist eine Wohlordnung:
Sei A ⊆ ω1 nichtleer, und sei N/≡ ∈ A beliebig. Wir setzen
M = { x ∈ N | Nx/≡ ∈ A }.
Ist M = ∅, so ist N/≡ das kleinste Element von A in ω1.
Andernfalls sei x das kleinste Element von M in N.
Dann ist Nx/≡ das kleinste Element von A in ω1.
Beweis von (+):
Sei α ∈ ω1 und sei 〈 N, < 〉 ∈ α (also α = N/≡ ). Dann gilt:
W(α) = (ω1)α = { M/≡ ∈ ω1 | M/≡ < N/≡ } = { Nx/≡ | x ∈ N } ≡ N,
wobei der letzte Ordnungsisomorphismus gegeben wird durch g(Nx/≡ ) = x für alle x ∈ N.
Der Zusatz gilt, da N abzählbar ist für alle α ∈ ω1 und 〈 N, < 〉 ∈ α.
ω1 ist überabzählbar:
Andernfalls ist 〈 ω1, < 〉 ≡ 〈 ℕ, <* 〉 für eine Wohlordnung <* auf ℕ (betrachte die induzierte Wohlordnung eines bijektiven g : ω1 → ℕ).
Dann ist α = 〈 ℕ, <* 〉/≡ ∈ ω1, nach (+) also
〈 W(α), < 〉 ≡ 〈 ℕ, <* 〉 ≡ 〈 ω1, < 〉,
also ist ω1 gleichlang zu einem Anfangsstück von sich selbst, Widerspruch.
Korollar (ordinale Minimalität von ω1)
〈 ω1, < 〉 ist eine kürzeste überabzählbare Wohlordnung:
Ist 〈 W, < 〉 eine überabzählbare Wohlordnung, so ist 〈 ω1, < 〉 ≡ 〈 W, < 〉 oder 〈 ω1, < 〉 ≺ 〈 W, < 〉.
Beweis
Ist 〈 W, < 〉 ≺ 〈 ω1, < 〉, so existiert ein α ∈ ω1 mit
〈 W, < 〉 ≡ 〈 (ω1)α, < 〉 = 〈 W(α), < 〉,
und dann ist insbesondere |W| = |W(α)|, also W abzählbar.
Ziehen wir den Wohlordnungssatz hinzu, so erhalten wir den folgenden für die Theorie der Kardinalzahlen fundamentalen Satz:
Korollar (kardinale Minimalität von ω1)
Sei M eine überabzählbare Menge. Dann ist |ω1| ≤ |M|.
Beweis
Sei < eine Wohlordnung von M nach dem Wohlordnungssatz.
Nach dem Korollar ist 〈 ω1, < 〉 ≡ 〈 M, < 〉 oder 〈 ω1, < 〉 ≺ 〈 M, < 〉.
In beiden Fällen ist dann insbesondere |ω1| ≤ |M|.
So wie wir alle n ∈ ℕ und ℕ selbst als Kardinalzahlen betrachtet haben, können wir nun auch ω1 als Kardinalzahl auffassen (indem wir ω1 als Zeichen für alle mit der Menge ω1 gleichmächtigen Mengen einführen, vgl. Kapitel 2 in Abschnitt 1).
Die Ordinalzahlen sind durch < wohlgeordnet, und es ist gefahrlos, die ersten Ordinalzahlen mit den natürlichen Zahlen zu identifizieren, wobei wir dann streng genommen Repräsentanten von Äquivalenzklassen mit Äquivalenzklassen verwechseln. Weiter schreiben wir ω für die kleinste unendliche Ordinalzahl. Nach unserer Definition gilt dann ω = 〈 ℕ, < 〉/≡ mit der üblichen Ordnung auf ℕ, und wir können ω mit ℕ identifizieren, wenn wir möchten.
Allgemein sei dem Leser geraten, sich unter einer abzählbaren Ordinalzahl die „Länge“ oder den „Ordnungstyp“ einer aus natürlichen Zahlen bestehenden Wohlordnung vorzustellen, und nicht eine komplexe Äquivalenzklasse von gleichlangen Wohlordnungen auf Teilmengen von ℕ (vgl. etwa die Konstruktion von ℝ über Äquivalenzklassen von Fundamentalfolgen in ℚ). Diese Anschauung will die hier vorgestellte Konstruktion gerade vermitteln:
Die endlichen Ordinalzahlen sind die natürlichen Zahlen. Die abzählbar unendlichen Ordinalzahlen sind alle Zahlen (im Sinne von „Typen“, „Längen“), die man erhält, wenn man die natürlichen Zahlen anders anordnet, aber ihre Wohlordnungseigenschaft beibehält. Weiter ist ω1 die kleinste Zahl, die größer als alle abzählbaren Zahlen ist, d. h. ω1 ist das Supremum aller abzählbaren Zahlen.
So kann man etwa ℕ neu wohlordnen, indem man zuerst alle geraden Zahlen und dann alle ungeraden Zahlen aufzählt. Man erhält so eine Ordinalzahl, die man als ω + ω bezeichnen würde. Formal ist ω + ω die Äquivalenzklasse modulo „gleichlang“ der Wohlordnung 〈 ℕ, <* 〉 mit <* = { (n, m) ∈ ℕ2 | n ist gerade und m ist ungerade oder n und m haben gleiche Parität und es gilt n < m in ℕ }.
Die Ordinalzahlreihe bis einschließlich ω1 verläuft dann schematisch etwa so:
0, 1, 2, 3, …, ω, ω + 1, …, ω + ω, ω + ω + 1, …, α, α + 1, …, …, …, ω1.
Die dreimal wiederholten Pünktchen in α, α + 1, …, …, …, ω1 bezeichnen in der Tat einen weiten Weg:
Übung
Sei A ⊆ ω1 abzählbar. Dann ist sup(A) < ω1 (bzgl. der Ordnung 〈 ω1, < 〉).
ω1 kann also nicht in abzählbar vielen Schritten „von unten“ erreicht werden. Umgekehrt gilt:
Übung
Sei λ < ω1 ein Limeselement. Dann gibt es eine Folge 〈 αn | n ∈ ℕ 〉 in ω1 mit:
(i) | αn < αn + 1 < ω1 für alle n ∈ ℕ, |
(ii) | λ = supn ∈ ℕ αn. |
[ Sei g : ℕ → W(λ) bijektiv. Setze βn = max({ g(k) | k ≤ n }) für n ∈ ℕ.
Ausdünnung von 〈 βn | n ∈ ℕ 〉 liefert eine Folge wie gewünscht. ]
Wir diskutieren noch kurz, wie man weitere Ordinalzahlen konstruieren kann. Der nächste Schritt wäre die Konstruktion von 〈 ω2, < 〉, einer kürzesten Wohlordnung mit der Eigenschaft |ω1| < |ω2|. Wir setzen hierzu ω2 = ℋ(ω1)/≡ , wobei jetzt ℋ(ω1) = { 〈 A, < 〉 | 〈 A, < 〉 ist eine Wohlordnung und A ⊆ ω1 }. Ansonsten bleibt alles gleich. ω2 können wir wieder als das Supremum der Zahlen (Längen, Typen) verstehen, die wir durch eine wohlgeordnete Umordnung von ω1 erhalten. Iteriert man die Idee, so sind die Indizes der Reihe ω1, ω2, ω3, … wieder wohlgeordnet. Eine Definition, die alle Ordinalzahlen auf einen Schlag einfängt, erscheint nun wünschenswert. Als kanonische Definition entpuppte sich (vgl. [ von Neumann 1923 ]): x heißt eine von-Neumann-Zermelo-Ordinalzahl, falls gilt:
(i) | x ist transitiv, d. h. für alle y ∈ x ist y ⊆ x, |
(ii) | 〈 x, ∈ 〉 ist eine Wohlordnung (mit 〈 x, ∈ 〉 = 〈 x, { (a, b) ∈ x2 | a ∈ b } 〉). |
Die Elementrelation übernimmt also für alle Ordinalzahlen uniform die Aufgabe der Wohlordnung. Unter dieser Definition gilt dann α < β genau dann, wenn α ∈ β, und wir erhalten W(α) = { β | β < α } = { β | β ∈ α } = α. Alles in allem ergibt sich ein sehr geschmeidiger Kalkül. Diese Definition zu motivieren und zu entwickeln ist etwas aufwendiger als die hier vorgestellte und für unsere Zwecke vielleicht sogar besser geeignete Hartogsmethode. Die Hartogsmethode bleibt auch unter der allgemeinen Definition nach von Neumann und Zermelo wichtig als eine Methode zur Konstruktion langer Wohlordnungen, die das Auswahlaxiom nicht heranzieht. Die Vorstellung einer abzählbaren transfiniten Zahl als einer wohlgeordneten Umordnung von ℕ fördert darüber hinaus das Verständnis des Begriffs.
Nachfolgerordinalzahlen und Limesordinalzahlen
Definition (Nachfolgerordinalzahlen und Limesordinalzahlen)
Die Nachfolgerelemente der Wohlordnung 〈 ω1, < 〉 heißen Nachfolgerordinalzahlen, die Limeselemente heißen Limesordinalzahlen oder kurz Limiten.
Die Unterscheidung in Nachfolger- und Limeselemente ist Wohlordnungen so eigentümlich, dass die Induktion und Rekursion über eine Wohlordnung sich in den meisten Fällen dieser Unterscheidung anpasst. Für ω1 lautet eine Form der Induktion etwa:
Sei A ⊆ ω1, und es gelte:
(i) | 0 ∈ A. (Induktionsanfang) |
(ii) | Für alle α < ω1 gilt: Ist α ∈ A, so ist auch α + 1 ∈ A. (Induktionsschritt) |
(iii) | Für alle Limiten λ gilt: Ist W(λ) ⊆ A, so ist auch λ ∈ A. (Limesschritt) |
Dann gilt A = ω1.
Eine analoge dreiteilige Form gilt für die Rekursion. Speziell für Rekursionen über ω1 definiert man in zahllosen Fällen:
| (i) | G(0), | |
| (ii) | G(α + 1) mit Rückgriff auf G(α) | für alle α < ω1, |
| (iii) | G(λ) mit Rückgriff auf G|W(λ) | für alle Limiten λ < ω1. |
Ein Beispiel für eine solche dreiteilige Rekursion wollen wir nun genauer betrachten, und es ist in der Tat mehr als nur irgendein Beispiel. Es ist der Amboss, auf dem die Ordinalzahlen geschmiedet wurden, und zusammen mit der Entdeckung der Überabzählbarkeit von ℝ brachte es die moderne Mathematik ins Rollen.