2. Ordinalzahlen
Der Begriff der Wohlordnung bildet zusammen mit dem Begriff der Mächtigkeit das Herz der Cantorschen Mengenlehre. Ist „Mächtigkeit“ elementarer, so stellt sich in der durchgeführten Theorie der Wohlordnungsbegriff als der feinere und stärkere heraus. Deswegen geht in der axiomatischen Mengenlehre die Untersuchung von Wohlordnungen und Ordinalzahlen der Untersuchung von Mächtigkeiten und Kardinalzahlen voran.
Wohlordnungen
Definition (Wohlordnung, WO)
Eine lineare Ordnung 〈 M, < 〉 heißt eine Wohlordnung, falls jede nichtleere Teilmenge von M ein <-kleinstes Element besitzt. Wir setzen:
WO = { 〈 M, < 〉 | 〈 M, < 〉 ist eine Wohlordnung }.
Wir werden gleich sehen, dass die Klasse WO aller Wohlordnungen eine echte Klasse ist. Diese Reichhaltigkeit der Wohlordnungen ist bereits in einer schwachen Teiltheorie von ZF beweisbar.
Oft schreiben wir auch einfach M statt 〈 M, < 〉, um die Notation zu vereinfachen. Eine von M abhängige Ordnungsrelation ist dann stillschweigend mit dabei. Teilmengen von M ererben die Ordnung von M, soweit nichts anderes gesagt wird: Ist M eine Wohlordnung und N ⊆ M, so ist N wohlgeordnet durch die Relation < ∩ N2. Statt < ∩ N2 schreiben wir auch <|N. Wichtige Teilordnungen sind die Anfangsstücke von Wohlordnungen: Für alle x ∈ M heißt
Mx = { y ∈ M | y < x }
das durch x gegebene Anfangsstück von M. Die Struktur 〈 ∅, ∅ 〉 ist eine Wohlordnung und ein Anfangsstück jeder nichtleeren Wohlordnung. Für jedes x ist weiter 〈 { x }, ∅ 〉 eine Wohlordnung.
Seien M und N Wohlordnungen. Ein f : M → N heißt ordnungstreu, falls für alle x, y ∈ M mit x < y gilt, dass f (x) < f (y). Automatisch folgt dann für alle x, y ∈ M aufgrund der Linearität der Ordnung: Ist f (x) < f (y), so ist x < y.
Ist ein ordnungstreues f : M → N zudem bijektiv, so heißt f ein Ordnungsisomorphismus. Zwei Wohlordnungen M und N heißen gleichlang, in Zeichen M ≡ N, falls ein Ordnungsisomorphismus f : M → N existiert. M heißt kürzer als N, in Zeichen M ⊲ N, falls ein y ∈ N existiert mit M ≡ Nx.
Wir stellen die wichtigsten Resultate über Wohlordnungen zusammen. Die Beweise der „Einführung in die Mengenlehre“ können übernommen werden. Wir geben aber die wesentlichen Argumente in kanpper Form an.
Satz (grundlegende Resultate über Wohlordnungen)
Seien M und N Wohlordnungen.
(a) | Ist f : M → M ordnungstreu, so gilt x ≤ f (x) für alle x ∈ M. |
(b) | Sind f, g : M → N Ordnungsisomorphismen, so gilt f = g. |
(c) | Ist x ∈ M, so ist Mx nicht isomorph zu M. Damit ist ⊲ irreflexiv. |
(d) | Ist N ⊆ M, so ist N mit der ererbten Ordnung nicht länger als M. |
Beweis
Für (a) beobachten wir: Gibt es ein x mit f (x) < x, so gibt es ein kleinstes x* mit f (x*) < x*. Dann gilt f (f (x*)) < f (x*) nach Ordnungstreue, im Widerspruch zur Minimalität von x*. Die anderen Aussagen können mit Hilfe von (a) und der Wohlordnungseigenschaft bewiesen werden.
Satz (Vergleichbarkeitssatz für Wohlordnungen)
Je zwei Wohlordnungen M und N sind in ihrer Länge vergleichbar: Es gilt entweder M ⊲ N oder M ≡ N oder N ⊲ M.
Beweis
Wir setzen f = { (x, y) ∈ M × N | Mx ≡ Ny }. Dann gilt:
(i) | f : dom(f) → rng(f) ist ein Ordnungsisomorphismus. |
(ii) | dom(f) ist gleich M oder ein Anfangsstück von M. |
(iii) | rng(f) ist N oder ein Anfangsstück von N. |
(iv) | dom(f) = M oder rng(f) = N. |
Damit bezeugt f oder f −1, dass M ≡ N oder M ⊲ N oder N ⊲ M.
Wegen der Irreflexivität von ⊲ schließen sich die drei Fälle aus.
Wohlordnungen erlauben induktives Beweisen und rekursives Definieren:
Satz (Induktionssatz für Wohlordnungen)
Sei M ∈ WO. Sei φ(x) eine Eigenschaft, sodass für alle x ∈ M gilt:
(+) Gilt φ(y) für alle y < x, so gilt φ(x).
Dann gilt φ(x) für alle x ∈ M.
Beweis
Andernfalls existiert ein kleinstes x ∈ M mit ¬ φ(x). Dann gilt aber φ(y) für alle y < x, also gilt φ(x) nach (+), Widerspruch.
Logische Äquivalenz von Induktion und Wohlordnungseigenschaft
Aus logischer Sicht ist der Induktionssatz einfach die Kontraposition der Wohlordnungseigenschaft. Denn die Existenz eines kleinsten Gegenbeispiels für eine Eigenschaft φ(x) können wir so formulieren:
(+) ∃x ¬ φ(x) → ∃x. ¬ φ(x) ∧ ∀y < x φ(y).
Kontraposition (d. h. der Übergang von ψ → χ zu ¬ χ → ¬ ψ) und Anwendung der Verneinungsregeln liefert die gleichwertige Aussage:
(++) (∀x. ∀y < x φ(y) → φ(x)) → ∀x φ(x).
Die Aussage (++) ist aber gerade der Induktionssatz für die Eigenschaft φ. Wir verwenden hier durchweg die klassische Logik, die uns das Streichen einer doppelten Negation erlaubt.
Für das rekursive Definieren gilt:
Satz (Rekursionssatz für Wohlordnungen)
Sei M eine Wohlordnung, und sei G : V → V eine funktionale Klasse. Dann existiert genau eine funktionale Klasse F : M → V mit
F(x) = G(F|Mx) für alle x ∈ M.
Wir werden die Rekursion unten in Klassenform für die Ordinalzahlen beweisen, und verzichten deswegen auf einen Beweis an dieser Stelle, um Wiederholungen zu vermeiden.
Zum Beweis des obigen Rekursionssatzes muss i. A. das Ersetzungsschema verwendet werden. Dies ist nicht notwendig, wenn wir eine Menge U angeben können derart, dass F(x) ∈ U für alle x ∈ M gilt. Vgl. hierzu den Beweis des Rekursionssatzes unten.
Die Konstruktion von Wohlordnungen
Es gibt zwei elementare Konstruktionsmöglichkeiten für Wohlordnungen: Die Enderweiterung um ein Element und die Amalgamierung einer beliebigen Menge von Wohlordnungen.
Enderweiterungen
Ist 〈 M, < 〉 eine Wohlordnung und ist y eine Menge mit y ∉ M, so ist die Enderweiterung N von M um y, in Zeichen N = M + { y }, definiert durch
N = M ∪ { y },
<N = <M ∪ { (x, y) | x ∈ M }.
Das Element y ist das größte Element der Wohlordnung N und es gilt Ny = M. Die Konstruktion zeigt, dass es in WO keine maximalen Elemente bzgl. ⊲ gibt.
Für jede Menge N können wir uniform eine Menge y mit y ∉ N definieren: Unter dem Fundierungsaxiom können wir y = N setzen. Ohne Rückgriff auf das Fundierungsaxiom ist die Menge y = { z ∈ x | z ∉ z } geeignet.
Amalgamierungen
Sei Γ eine Kette von Wohlordnungen, d. h. für je zwei verschiedene Elemente M, N von Γ gilt, dass M ein Anfangsstück von N oder N ein Anfangsstück von M ist. Dann ist die Vereinigung N = ⋃ Γ eine Wohlordnung. Jedes M ∈ Γ ist gleich N oder ein Anfangsstück von N. Ist umgekehrt x ∈ N, so ist Nx ∈ Γ oder es existiert ein M ∈ Γ mit Nx ⊲ M. Die Länge von M ist also das Supremum der Längen von M.
Allgemeiner können wir eine beliebige Menge von Wohlordnungen wie folgt zu einer neuen Wohlordnung verschmelzen:
Definition (Amalgamierung von Wohlordnungen, 𝒜−(Γ) und 𝒜(Γ))
Sei Γ eine Menge von Wohlordnungen. Dann sind die Amalgamierungen 𝒜−(Γ) = 〈 W−, < 〉 und 𝒜(Γ) = 〈 W, < 〉 definiert durch:
W− = { Mx | M ∈ Γ, x ∈ M }/≡ ,
W = (Γ ∪ { Mx | M ∈ Γ, x ∈ M })/≡ ,
M/≡ < N/≡ , falls M ⊲ N für alle M/≡ , N/≡ in W− bzw. W.
Die Relationen < sind wohldefiniert auf W− und W. Leicht zu sehen sind die folgenden Eigenschaften der beiden Amalgamierungen:
Satz (über die Amalgamierung)
Sei Γ eine Menge von Wohlordnungen, und seien W− = 𝒜−(Γ), W = 𝒜(Γ).
Dann sind W− und W Wohlordnungen. Weiter ist die Länge von W das strikte Supremum der Längen der Wohlordnungen in Γ, d. h. es gilt:
(i) | Für alle M ∈ Γ ist M ⊲ W. |
(ii) | Ist W′ eine Wohlordnung wie in (i), so ist W ⊲ W′ oder W ≡ W′. |
Analog ist die Länge von W− das Supremum der Längen in Γ.
Hat also Γ kein ⊲-größtes Element, so sind W− und W gleichlang. Hat Γ ein ⊲-größtes Element M, so ist W− gleichlang zu M und W ist gleichlang zu jeder Enderweiterung von M um ein Element. Schließlich gilt: Ist Γ eine Kette von Wohlordnungen, so sind W− und ⋃ Γ gleichlang.
Ist Γ abgeschlossen unter Anfangsstücken, d. h. ist Mx ∈ Γ für alle M ∈ Γ und alle x ∈ M, so ist 𝒜+(Γ) = Γ/≡ .
Die Amalgamierung liefert:
Satz (Reichhaltigkeit der Wohlordnungen)
WO ist eine echte Klasse.
Beweis
Annahme, WO ist eine Menge. Sei dann W die Amalgamierung von WO. Dann gilt M ⊲ W für alle M ∈ WO. Wegen W ∈ WO also W ⊲ W, Widerspruch.
Zum Beweis dieses Satzes genügt eine schwache Axiomatik. Wir brauchen weder (AC), (Ers) noch (Fun).
Die Hartogs-Wohlordnung
Ein wichtiger Spezialfall der Amalgamierung ist die Konstruktion von langen Wohlordnungen nach Hartogs:
Definition (Hartogs-Wohlordnung)
Sei M eine Menge, und sei Γ = { 〈 N, < 〉 ∈ WO | N ⊆ M }. Dann heißt 𝒜(Γ) die Hartogs-Wohlordnung von M.
Da Γ abgeschlossen unter Anfangsstücken ist, gilt 𝒜(Γ) = Γ/≡ . Die wichtigsten Eigenschaften dieser Konstruktion sind:
Satz (über die Hartogs-Wohlordnung)
Sei M eine Menge, und sei W die Hartogs-Wohlordnung von M. Dann gilt:
(i) | Für alle N/≡ ∈ W sind 〈 N, < 〉 und WN/≡ gleichlang. Insbesondere ist |WN/≡ | = |N| ≤ |M|. |
(ii) | non(|W| ≤ |M|). |
Beweis
zu (i):
Für alle N/≡ ∈ W ist WN/≡ = { N′/≡ ∈ W | N′/≡ <W N/≡ }, und die Funktion f : N → WN/≡ mit
f (x) = Nx/≡ für alle x ∈ N
ist ein Ordnungsisomorphismus.
zu (ii):
Annahme, es gibt ein injektives g : W → M. Sei 〈 N, < 〉 die durch g induzierte Wohlordnung auf N = rng(g). Dann sind W und N gleichlang, und es gilt N/≡ ∈ W. Nach (i) sind also W und das Anfangsstück WN/≡ von W gleichlang, Widerspruch.
Wir bemerken noch, dass die Hartogs-Wohlordnung W von M für hinreichend große n eine Teilmenge von ℘n(M) ist, und damit gilt also im Gegensatz zu (ii) die Ungleichung |W| ≤ |℘n(M)|. Verwendet man in der Konstruktion von W nur die Wohlordnungs-Relationen < ⊆ M × M ⊆ ℘2(M) anstelle der geordneten Paare 〈 N, < 〉, so kann man hier W ⊆ ℘4(M) erreichen. Denn dann ist Γ ⊆ ℘3(M), und damit ist W = Γ/≡ ⊆ ℘4(M).
Rekursionen entlang der Hartogs-Wohlordnung
Die Hartogs-Wohlordnung ist nützlich, um zu zeigen, dass eine bestimmte rekursive Konstruktion zum Halten kommt oder ihr angestrebtes Ziel erreicht. Wir geben hierfür zwei Beispiele.
Die Rekursionen entlang der Hartogs- oder allgemein einer beliebigen Wohlordnung können natürlich auch entlang der Klasse der Ordinalzahlen durchgeführt werden. Aber die Entwicklung der Ordinalzahlen ist zum Beweis der folgenden Sätze nicht notwendig. Zudem benötigt die Ordinalzahltheorie das Ersetzungsschema, das wir bei den folgenden Beispielen nicht verwenden müssen.
Der Wohlordnungssatz
Wir zeigen als Erstes den Wohlordnungssatz durch „rekursives Abtragen“. Hierzu setzen wir das Auswahlaxiom ein, das bislang nicht verwendet wurde.
Satz (Wohlordnungssatz)
Jede Menge M lässt sich wohlordnen.
Beweis
Sei 〈 W, <W 〉 die Hartogs-Wohlordnung von M. Wir definieren durch Rekursion entlang a ∈ W mit Hilfe von (AC) solange möglich:
f (a) = „ein x ∈ M − { f (b) | b <W a }“ falls { f (b) | b <W a } ≠ M.
Dann existiert ein erstes nicht definiertes f (a*), denn andernfalls wäre f : W → M injektiv. Nach Konstruktion ist dann f : Wa* → M bijektiv und induziert damit eine Wohlordnung auf M.
Dieser Beweis ist in ZFC ohne Fundierungsaxiom und ohne Ersetzungsschema ausführbar. Für alle x ∈ M ist f (x) ∈ M, das für Rekursionen i. A. notwendige Ersetzungsschema muss nicht verwendet werden. Dagegen ist die Verwendung von (AC) unentbehrlich, der Wohlordnungssatz ist über ZF sogar äquivalent zum Auswahlaxiom.
Wir diskutieren die Anwendungen und Äquivalenzen des Auswahlaxioms noch genauer in einem eigenen Kapitel. Für die Entwicklung der Wohlordnungstheorie einschließlich der Ordinalzahltheorie und für die durch die von Neumann-Zermelo-Hierarchie motivierte Untersuchung des Fundierungsaxioms (s. u.) wird der Wohlordnungssatz nicht gebraucht. Innerhalb der Theorie der Wohlordnungen ist die Wohlordenbarkeit die einzige Stelle, für die im Allgemeinen das Auswahlaxiom verwendet werden muss.
Fixpunktsätze
Als ein weiteres Beispiel für eine Rekursion entlang der Hartogs-Wohlordnung beweisen wir den folgenden Fixpunktsatz:
Satz (Fixpunktsatz von Bourbaki)
Sei 〈 P, ≤ 〉 eine partielle Ordnung, in der jede linear geordnete Teilmenge ein Supremum besitzt. Weiter sei f : P → P expansiv auf P, d. h. für alle x ∈ P ist x ≤ f (x). Schließlich sei y ∈ P beliebig. Dann besitzt f einen Fixpunkt oberhalb von y, d. h. es gibt ein z ∈ P mit:
y ≤ z und f (z) = z.
Beweis
Sei 〈 W, <W 〉 die Hartogs-Wohlordnung von P. Wir definieren eine Folge 〈 xa | a ∈ W 〉 durch Rekursion entlang der Wohlordnung <W wie folgt:
| x0W | = y | für das Anfangselement 0W von W |
| xa + 1 | = f (xa) | für alle Nachfolgerelemente a + 1 von W |
| xb | = supa < b xa | für alle Limeselemente b von W |
Dann gibt es ein <W-kleinstes a* mit xa* + 1 = xa*, da andernfalls 〈 xa | a ∈ W 〉 injektiv wäre. Nach Konstruktion gilt xa* ≥ y und f (xa*) = xa*. Damit ist a* ein Fixpunkt von f oberhalb von y.
Der Beweis ist in ZF − (Ers) durchführbar. Das Argument zeigt auch, dass der Satz richtig bleibt, wenn „jede linear geordnete Teilmenge besitzt ein Supremum“ durch „jede wohlgeordnete Teilmenge besitzt ein Supremum“ ersetzt wird. Diese Voraussetzung genügt, um den Limesschritt der obigen Rekursion durchführen zu können.
Der Fixpunktsatz kann Maximalprinzipien wie das Zornsche Lemma ersetzen, falls das Auswahlaxiom nicht gebraucht wird, und falls auf den Einsatz der Theorie der Wohlordnungen verzichtet werden soll.
Korollar (Fixpunktsatz von Knaster-Tarski)
Sei 〈 P, ≤ 〉 eine partielle Ordnung, in der jede linear geordnete Teilmenge ein Supremum besitzt. Weiter sei f : P → P monoton auf P, d. h. für alle x, y ∈ P mit x ≤ y gilt f (x) ≤ f (y). Schließlich sei y ∈ P mit y ≤ f (y). Dann besitzt f einen Fixpunkt oberhalb von y.
Beweis
Die Menge P′ = { x ∈ P | y ≤ x, x ≤ f (x) } mit der von P ererbten Ordnung erfüllt die Voraussetzungen des Fixpunktsatzes von Bourbaki.
Die leere Menge ist eine linear geordnete Teilmenge von P. Da ihr Supremum existiert, hat P ein kleinstes Element 0P. Sicher gilt 0P ≤ f (0P), und damit hat jede monotone Funktion auf P mindestens einen Fixpunkt.
Die wichtigsten Beispiele für partielle Ordnungen, die die Kettenbedingung der beiden Fixpunktsätze erfüllen, sind die Strukturen der Form 〈 ℘(M), ⊆ 〉, mit einer beliebigen Menge M und der Inklusion ⊆.
Die Fixpunktsätze haben, ähnlich wie die Maximalprinzipien, viele Anwendungen. Ein Beweis des Satzes von Cantor-Bernstein mit Hilfe des Fixpunktsatzes von Knaster-Tarski ist uns in der „Einführung“ (1.4) schon begegnet. Ganz allgemein kann man die Theorie der Wohlordnungen etablieren, indem man zuerst den Fixpunktsatz von Bourbaki beweist. Wir verweisen hierzu den Leser auf [ Rautenberg 2008 ].
Ordinalzahlen
In der „Einführung“ hatten wir nach einer ausführlichen Betrachtung des Wohlordnungsbegriffs und den informalen Cantorschen und Hausdorffschen Ordinalzahlen die moderne Definition einer Ordinalzahl nach von Neumann und Zermelo bereits kennen gelernt (siehe dort 2. 6). Hier werden wir naturgemäß ausschließlich mit der modernen Definition arbeiten. Formal einwandfrei definierte Ordinalzahlen sind unerlässlich.
Wir geben eine Motivation der Ordinalzahlen nach von Neumann und Zermelo aus heutiger Sicht. Hierzu definieren abstrakt:
Definition (Ordinalzahldefinition)
Eine funktionale Klasse F : WO → V heißt eine Ordinalzahldefinition, falls für alle M, N ∈ WO gilt:
(+) F(M) = F(N) gdw M und N sind gleichlang.
Die Elemente des Wertebereichs von F heißen F-Ordinalzahlen. Eine Ordinalzahldefinition G heißt repräsentierend, falls für alle M ∈ WO gilt:
(++) G(M) ist eine zu M gleichlange Wohlordnung.
Gleichwertig zu (++) ist, wie man sich leicht klarmacht, die Bedingung:
(++)′ G(M) ∈ WO und G(G(M)) = G(M).
Wir suchen eine kanonische repräsentierende Ordinalzahldefinition. Die erste Beobachtung ist, dass wir eine repräsentierende Ordinalzahldefinition G aus einer beliebigen Ordinalzahldefinition F gewinnen können. Wir schreiben hierzu die F-Ordinalzahlen gemäß F mit kleinen griechischen Buchstaben und definieren eine relationale Klasse < auf den F-Ordinalzahlen durch
α < β, falls M kürzer als N ist,
wobei M, N beliebig sind mit F(M) = α und F(N) = β. Dies ist wohldefiniert.
Wir setzen nun:
G(M) = { α | α < F(M) } für alle M ∈ WO,
und wohlordnen die Menge G(M) durch <. Es ist leicht zu zeigen, dass G eine repräsentierende Ordinalzahldefinition ist.
Von einer kanonischen Ordinalzahldefinition F wird man erwarten, dass dieser Übergang von F zu G nichts Neues mehr liefert, dass also bereits F = G gilt. Unter dieser Voraussetzung ist α = { β | β < α } für alle Ordinalzahlen α, und weiter gelten die folgenden Aussagen:
(1) Jedes α ist transitiv.
(2) Die ∈ -Relation ist die <-Ordnung, und also eine Wohlordnung auf α.
Die Eigenschaften (1) und (2) genügen nun bereits für eine Definition:
Definition (Ordinalzahl, On, <)
Ein x heißt eine Ordinalzahl, falls x transitiv und durch ∈ wohlgeordnet ist. Wir setzen:
On = { α | α ist eine Ordinalzahl }
α < β, falls α ∈ β für alle α, β ∈ On.
Die folgenden Eigenschaften sind in der Theorie ZF ohne Fundierungsaxiom und Ersetzungsschema beweisbar (Übung):
Satz (elementare Eigenschaften der Ordinalzahlen)
Für alle α, β ∈ On gilt:
(i) | α ⊆ On und α = { γ ∈ On | γ < α }. |
(ii) | α ∉ α. |
(iii) | Ist β ∈ α, so ist αβ = „das durch β gegebene Anfangsstück von α“ = β. |
(iv) | Ist β ⊂ α, so ist β ∈ α. |
(v) | Ist α ≡ β, so ist α = β. Ist α ⊲ β, so ist α ∈ β. |
(vi) | Es gilt α < β oder α = β oder β < α. |
(vii) | ω ⊆ On, ω ∈ On. |
(viii) | α ∪ { α } ∈ On. |
(ix) | Ist x eine Menge von Ordinalzahlen, so ist ⋃ x ∈ On. |
(x) | Ist x eine transitive Menge von Ordinalzahlen, so ist x ∈ On. |
(xi) | Ist A ⊆ On eine nichtleere Klasse, so hat A ein kleinstes Element. |
Zu (ii): Wäre α ∈ α, so gilt β ∈ β für ein β ∈ α − nämlich für β = α. Dann ist aber ∈ nicht irreflexiv auf α, im Widerspruch zur Voraussetzung, dass ∈ eine lineare Ordnung auf α ist.
Korollar
On ist eine echte Klasse.
Beweis
Andernfalls sei α = ⋃ On. Dann ist α ∈ On und weiter α ∪ { α } ∈ On, also α ∈ ⋃ On = α. Also gilt α ∈ α, Widerspruch.
Eine verwandte Argumentation ist: Wäre On eine Menge, so wäre nach obigen Eigenschaften On transitiv und durch ∈ wohlgeordnet. Also wäre On selbst eine Ordinalzahl, d. h. On ∈ On, Widerspruch.
Insgesamt ist die <-Relation eine relationale Klasse auf On, die die Ordinalzahlen linear ordnet. Weiter gilt die Wohlordnungseigenschaft für On, d. h. jede nichtleere Teilklasse besitzt ein <-kleinstes Element.
Wir definieren:
Definition (Nachfolger- und Limesordinalzahl)
(a) | Für alle α ∈ On heißt α + 1 = α ∪ { α } der Nachfolger von α. |
(b) | Ein β ∈ On heißt eine Nachfolgerordinalzahl, falls es ein α ∈ On gibt mit β = α + 1. |
(c) | Ein λ ∈ On heißt eine Limesordinalzahl, falls λ ≠ 0 und λ kein Nachfolger ist. |
Wie üblich sind die Begriffe Minimum, Supremum und striktes Supremum für die lineare Ordnung < auf On definiert. Die Minima und Suprema können wir durch einfache mengentheoretische Operationen ermitteln, wie der folgende einfach zu beweisende Satz zeigt:
Satz (Supremum, striktes Supremum, Minimum von Ordinalzahlen)
Für alle α ∈ On, x ⊆ On und jede nichtleere Klasse A ⊆ On gilt:
(a) | α + 1 ist die kleinste Ordinalzahl, die größer als α ist, |
(b) | ⋃ x ist das Supremum von x, |
(c) | ⋃ { α + 1 | α ∈ x } ist das strikte Supremum von x, |
(d) | ⋂ A ist das Minimum von A. |
Wir schreiben sup(x), strsup(x) für das Supremum bzw. strikte Supremum von x und min(A) für das Minimum von A.
Der Repräsentationssatz
Mit Hilfe des Ersetzungsschemas können wir zeigen:
Satz (Repräsentations- und Eindeutigkeitssatz)
Für alle M ∈ WO existiert genau ein α ∈ On mit M ≡ α.
Beweis
Es genügt, für alle N ∈ WO zu zeigen:
| (+) | Für alle x ∈ N existiert genau ein α ∈ On mit Nx ≡ α. |
Dies zeigen wir durch Induktion nach x ∈ N. Für alle y < x können wir nach Induktionsvoraussetzung definieren:
F(y) = „das eindeutige α ∈ On mit Ny ≡ α“.
Mit Hilfe von (Ers) ist M = { F(y) | y < x } eine Menge. Wir setzen nun
γ = strsup(M).
Dann ist Nx ≡ γ. Die Eindeutigkeit ist klar.
Damit können wir definieren:
Definition (Ordnungstyp einer Wohlordnung, o. t.)
Wir definieren eine funktionale Klasse o. t.: WO → On durch:
o. t.(M) = „das eindeutige α ∈ On mit M ≡ α“ für alle M ∈ WO.
Dann ist o. t. : WO → On eine repräsentierende Ordinalzahldefinition.
Charakterisierungen
Es gibt eine Vielzahl von Charakterisierungen der Ordinalzahlen, und wir beenden diesen Zwischenabschnitt mit einigen äquivalenten Formulierungen.
Übung
Die folgenden Aussagen sind äquivalent für alle x:
(i) | x ist eine Ordinalzahl. |
(ii) | x ist transitiv und wird durch ∈ linear geordnet (mit (Fun)). |
(iii) | x ist transitiv und wird durch ⊂ wohlgeordnet. |
(iv) | x ist transitiv und wird durch ⊂ linear geordnet (mit (Fun)). |
(v) | x ist durch ∈ wohlgeordnet und für alle y ∈ x gilt y = { z ∈ x | z ∈ x } d. h. y ist das durch y gegebene Anfangsstück von x. |
(vi) | x ist transitiv, alle Elemente von x sind transitiv, und jede nichtleere Teilmenge von x besitzt ein ∈ -minimales Element. |
(vii) | x ist transitiv, alle Elemente von x sind transitiv (mit (Fun)). |
(viii) | x ist transitiv und für alle y ⊂ x gilt: Ist y transitiv, so ist y ∈ x. |
Ordinale Induktion und Rekursion
Die Klasseninduktion für Ordinalzahlen ergibt sich wieder direkt aus der Eigenschaft, dass nichtleere Klassen von Ordinalzahlen ein kleinstes Element besitzen:
Satz (Induktionssatz für On)
Sei φ(α) eine Eigenschaft, sodass für alle α ∈ On gilt:
(+) Gilt φ(β) für alle β < α, so gilt φ(α).
Dann gilt φ(α) für alle α ∈ On.
Anwendung des Induktionssatzes
In der Praxis verwenden wir oft eine dreiteilige Form, bei der wir anstelle von (+) zeigen:
Induktionsanfang
Es gilt φ(0).
Nachfolgerschritt von α nach α + 1
Für alle Ordninalzahlen α gilt:
φ(α) impliziert φ(α + 1).
Limesschritt λ
Für alle Limesordinalzahlen λ gilt :
φ(α) für alle α < λ impliziert φ(λ).
Haben wir dies bewiesen, so gilt φ(α) für alle α ∈ On.
Rekursion
Wir zeigen nun den Rekursionssatz für On (und reichen damit auch den Beweis des Rekursionssatzes für Wohlordnungen nach).
Satz (Rekursionssatz für On)
Sei G : V → V eine funktionale Klasse. Dann existiert eine eindeutige funktionale Klasse F : On → V mit:
(#) F(α) = G(F|α) für alle α ∈ On.
Beweis
Sei φG(α, x) die folgende Formel:
„α ∈ On und es gibt eine Folge f = 〈 xβ | β < α 〉 mit:
(i) für alle β < α ist xβ = G(f|β), (ii) x = G(f)“.
Wir zeigen:
| (+) | F = { (α, x) | φG(α, x) } ist eine funktionale Klasse und es gilt (#). |
Zum Beweis von (+) nennen wir eine Folge 〈 xβ | β < α 〉 wie in (i) eine α-Approximation der Rekursion mit G, und zeigen durch Induktion über α ∈ On:
(++) Es gibt genau eine α-Approximation fα = 〈 xβ | β < α 〉.
Beweis von (++)
Zur Eindeutigkeit:
Sind 〈 xβ | β < α 〉 und 〈 yβ | β < α 〉 α-Approximationen, so zeigt eine einfache Induktion über β, dass xα = xβ für alle β < α gilt.
Zur Existenz:
f0 = ∅ ist die eindeutige 0-Approximation. Ist fα die eindeutige α-Approximation, so ist fα + 1 = fα ∪ { (α, G(fα)) } die eindeutige α + 1-Approximation. Im Limesschritt λ wird nun entscheidend das Ersetzungsschema verwendet. Wir setzen:
fλ = ⋃α < λ fα,
wobei fα die eindeutige α-Approximation ist für alle α < λ.
Formal ist also fλ = ⋃ H″a, wobei H die funktionale Klasse ist, die jedem α < λ die eindeutige α-Approximation zuordnet, und jedem anderen x die leere Menge.
Aus (++) folgt, dass F = { (α, x) | φG(α, x) } eine funktionale Klasse ist. Eine einfache Induktion nach α ∈ On zeigt, dass (#) gilt.
Ist F′ eine weitere funktionale Klasse mit (#), so zeigt eine abschließende Induktion nach α ∈ On, dass F(α) = F′(α) für alle α ∈ On gilt.
Der Rekursionssatz liefert uns zu jeder funktionalen Klasse G eine zweite funktionale Klasse F, die die Rekursionsgleichung F(α) = G(F|α) erfüllt. Klassen sind durch Formeln definiert, und der Beweis zeigt uns ja auch, wie eine F definierende Formel in eine G definierende Formel umgewandelt werden kann: Die Formel φG(x, α) können wir konkret auf dem Papier aufschreiben, wenn wir die G definierende Formel ψ(x) kennen. Der Beweis des Rekursionssatzes zeigt, dass die aus ξ(x) gewonnene Formel φG(x, α) die gewünschten Eigenschaften hat.
Die von Neumann-Hierachie
Es ist instruktiv, sich die effektive Umwandlung von Formeln an einem Beispiel klar zu machen. Wir betrachten hierzu die kumulative von Neumann-Hierarchie 〈 Vα | α ∈ On 〉:
Definition (Vα-Hierarchie, V*)
Wir definieren durch Rekursion über α ∈ On:
V0 = ∅
Vα + 1 = ℘(Vα) für alle α ∈ On
Vλ = ⋃α < λ Vα für Limiten λ
Weiter setzen wir V* = ⋃α ∈ On Vα.
Die Vα-Mengen bilden eine transitive und kumulative Hierarchie: Alle Vα sind transitiv und es gilt Vα ⊆ Vβ für alle α ≤ β.
Auflösung der Rekursion als Epsilon-Formel
Für die Vα-Rekursion können wir als funktionale Klasse G wählen:
Ist F die Lösung der Rekursionsgleichung „F(α) = G(F|α) für alle α ∈ On“, so gilt F(0) = ∅, F(α + 1) = ℘(F(α)) für alle α ∈ On und F(λ) = ⋃α < λ F(α) für alle Limiten λ. Wie üblich schreiben wir Vα statt F(α).
Formeln wie „x = Vα“, „x ∈ Vα“ usw. können wir nun frei verwenden, ohne dabei die ∈ -Sprache der Mengenlehre zu verlassen. Gleiches gilt für „x ∈ V*“, denn dies ist die Formel „es gibt ein α ∈ On mit x ∈ Vα“.
Die Formel „x = Vω“ ist zum Beispiel äquivalent zur folgenden Formel φ(x) mit ω als Parameter:
„es gibt eine Funktion f mit:
dom(f) = ω, f (0) = ∅, f(n + 1) = ℘(f (n)) für alle n ∈ ω, x = ⋃ rng(f)“.
Die Formel φ(x) kann nun mit einigem Aufwand als ∈ -Formel ausgeschrieben werden.
Hat man diese Möglichkeit der Auflösung einer Rekursion einmal verinnerlicht, wird man gerne zu Ausdrücken wie „x = Vω“ und den zugehörigen oft informal − d. h. ohne Erwähnung der funktionalen Klasse G − präsentierten Rekursionen zurückkehren wollen. Alles bleibt wie gehabt, aber wir haben die Rekursion im axiomatischen Rahmen streng gerechtfertigt. Insgesamt ist dies ein Triumph der Ausdruckskraft der ∈ -Sprache unter den ZFC-Axiomen. Der Beweis zeigt, dass wir mit dem Ersetzungsschema ein starkes Axiomenschema brauchen, um die Rekursion formal abzusichern. Mit anderen Worten: Das Ersetzungsschema, das in der ursprünglichen Axiomatik von Zermelo ja noch fehlte, findet man unweigerlich, wenn man die von Cantor eingeführte transfinite Rekursion nicht nur intuitiv, sondern als beweisbaren Satz begreifen möchte.
Die Rolle des Fundierungsaxioms
Zur Definition der Ordinalzahlen, der von Neumann-Zermelo-Hierarchie und der Klasse V* = ⋃α ∈ OnVα wurde das Fundierungsaxiom nicht verwendet. Mit Hilfe des Fundierungsaxioms zeigen wir nun, dass die Vα-Hierarchie das Universum V ganz ausschöpft: Es gilt V = V*, d. h. für alle x existiert ein α mit x ∈ Vα. Hierzu brauchen wir eine für sich interessante Hilfskonstruktion.
Satz (Existenz des transitiven Abschlusses)
Für alle x existiert ein ⊆-kleinstes y mit: x ⊆ y, y ist transitiv.
Beweis
Wir definieren rekursiv für n < ω:
x0 = x
xn + 1 = ⋃ xn für alle n ∈ ω.
Dann ist y = ⋃n ∈ ω xn wie gewünscht.
Definition (transitiver Abschluss)
Für alle x setzen wir:
t. c.(x) = „die ⊆-kleinste transitive Menge y mit x ⊆ y“.
Die Bezeichnung „t. c.“ steht hier für „transitive closure“.
Mit Hilfe des transitiven Abschlusses können wir folgende Klassenversion des Fundierungsaxioms beweisen:
Satz (Klassenversion des Fundierungsaxioms)
Sei A eine nichtleere Klasse. Dann besitzt A ein ∈ -minimales Element, d. h. es gibt ein x ∈ A mit x ∩ A = ∅.
Beweis
Sei x ∈ A beliebig. Ist x ∩ A = ∅, so ist x ∈ -minimal. Andernfalls sei y = t. c.(x) ∩ A. Nach (Fun) besitzt y ein ∈ -minimales Element z.
Dann gilt z ∈ A und z ∩ A = ∅, also ist z ein ∈ -minimales Element von A.
Der Umweg über den transitiven Abschluss ist in der Tat notwendig:
Übung
Geben Sie eine Klasse A, ein x ∈ A und ein ∈ -minimales Element y von x ∩ A an derart, dass y nicht ∈ -minimal in A ist.
Nun können wir ohne Mühe zeigen:
Satz (Hierarchiesatz)
Es gilt V = V*, d. h. für alle x existiert ein α ∈ On mit x ∈ Vα.
Beweis
Sei A = V − V*. Annahme, A ≠ ∅. Sei dann x ∈ A ∈ -minimal in A.
Dann gilt aber x ⊆ V*. Für alle y ∈ x sei also
F(y) = „das kleinste α ∈ On mit y ∈ Vα“.
Sei α* = supy ∈ x F(y) (nach (Ers)). Dann gilt x ⊆ Vα*, also ist x ∈ Vα* + 1.
Damit ist x ∈ V*, Widerspruch.
Die Aussage „V = V*“ ist äquivalent zum Fundierungsaxiom über den restlichen Axiomen:
Übung
In ZF − (Fun) + „V = V*“ gilt das Fundierungsaxiom.
Damit haben wir im Rahmen unserer Axiomatik ein geordnetes Bild des Universums entwickelt: Das Universum V „entsteht“ aus der leeren Menge durch iterierte Anwendung der Potenzmengenbildung und Vereinigung entlang der Ordinalzahlen. Die Klasse V* = ⋃α ∈ On Vα können wir ohne Fundierungsaxiom definieren, aber erst mit diesem Axiom können wir V = V* zeigen und damit ein geordnetes Bild des Universums entwerfen. Es ist oft gesagt worden, dass die Gleichung „V = V*“ die intendierte Semantik der axiomatischen Mengenlehre darstellt. Es ist bemerkenswert, dass ein Axiomensystem existiert, dessen Mitglieder nicht über Wohlordnungen und Ordinalzahlen sprechen, das aber eine ausschöpfende transfinite Klassenhierarchie in sich trägt. Das Fundierungsaxiom spielt hier eine Schlüsselrolle, und es ist deswegen ein allgemein akzeptiertes Axiom der Mengenlehre.
Wir verweisen den Leser in diesem Zusammenhang auch auf [ Scott 1974 ] für eine gleichwertige Axiomatisierung der Mengenlehre, die die Intuition „V = V*“ direkter beschreibt.
Ein Prinzip, das dem Fundierungsaxiom widerspricht, diskutieren wir kurz am Ende des Kapitels über wohlfundierte Relationen. Dieses Prinzip, das sog. Antifundierungsaxiom, lässt sich aber letztendlich auch wieder innerhalb von ZFC durch geeignete Modellkonstruktionen analysieren, und sprengt in diesem Sinne die Interpretationskraft von ZFC nicht.
Der Beweis der Gleichung „V = V*“ verwendet an keiner Stelle das Auswahlaxiom. Die Vα-Hierarchie schöpft also das Universum aus, egal, ob wir die Existenz von abstrakten Auswahlmengen fordern oder nicht. Im entscheidenden Nachfolgerschritt von Vα nach Vα + 1 sammeln wir alle Teilmengen von Vα, die das Universum zu bieten hat. Darin ist keine Aussage enthalten, wie viele oder welche Teilmengen im Universum existieren. Die Idee, in einer Hierarchiekonstruktion statt „allen Teilmengen“ nur all diejenigen Teilmengen aufzunehmen, deren Existenz von den Axiomen explizit gefordert wird, führt zu Gödels konstruktiblem Universum L, das wir im zweiten Abschnitt besprechen werden. Dass „V = L“ gilt, kann man als eine Verstärkung von „V = V*“ und damit als eine Verstärkung des ordnenden Fundierungsaxioms ansehen. Hier gehen dann allerdings die Meinungen, ob diese Verstärkung den Rang eines Axioms erhalten soll oder nicht, weit auseinander.
Man wird das regulative Fundierungsaxiom nicht als einen Kandidaten für einen hypothetischen Widerspruch der Axiomatik ansehen. Aber einen Beweis braucht diese Anschauung allemal, denn die Axiome von ZFC könnten ja z. B. versteckt die Existenz einer Menge x mit x ∈ x fordern. Wir werden später als ersten relativen Konsistenzbeweis zeigen: Ist ZFC ohne (Fun) widerspruchsfrei, so ist auch ZFC widerspruchsfrei. Hier wird die Klasse V* noch einmal eine wichtige Rolle spielen.
Der Hierarchiesatz erlaubt folgende Identifikation von echten Klassen:
Satz (Charakterisierung von echten Klassen)
Sei A = { x | φ(x) } eine Klasse. Dann sind äquivalent:
(i) | A ist eine echte Klasse. |
(ii) | A ist unbeschränkt in der Vα-Hierarchie, d. h. für alle α ∈ On gibt es ein x ∈ A mit x ∉ Vα. |
Beweis
A ist Menge gdw es gibt ein α ∈ On mit A ∈ Vα gdw es gibt ein α ∈ On mit A ⊆ Vα gdw A ist beschränkt in der Vα-Hierarchie.
Übung
In ZF − (Fun) gilt: Ist A ⊆ V* unbeschränkt, so ist A eine echte Klasse.
Zur weiteren Erläuterung des Fundierungsaxioms betrachten wir schließlich noch unendliche absteigende ∈ -Ketten:
Übung
In ZFC − (Fun) sind äquivalent:
(i) | (Fun). |
(ii) | Es gibt kein f : ω → V mit f(n + 1) ∈ f (n) für alle n ∈ ω. |
[ Im Beweis von (ii) ↷ (i) wird das Auswahlaxiom gebraucht. ]
Die Rangfunktion
Definition (Rangfunktion, rang(x))
Für alle x ∈ V* setzen wir:
rang(x) = „das kleinste α ∈ On mit x ⊆ Vα“.
In ZFC ist die Rangfunktion auf ganz V definiert, und wir wollen dies immer annehmen, wenn wir nicht explizit das Fundierungsaxiom betrachten.
Die Rangfunktion ist ein Maß für die Komplexität einer Menge. Wir erschließen diese Funktion durch eine Reihe von Übungen.
Übung
Für alle α ∈ On und alle x, y gilt:
(i) | rang(α) = rang(Vα) = α |
(ii) | x ⊆ y impliziert rang(x) ≤ rang(y) |
(iii) | x ∈ y impliziert rang(x) < rang(y) |
(iv) | t. c.(x) ⊆ Vrang(x) und damit also rang(t. c.(x)) = rang(x) |
(v) | rang(x) = strsupy ∈ x rang(y) (= supy ∈ x rang(y) + 1). |
Die letzte Eigenschaft charakterisiert die Rangfunktion:
Übung
Sei F : V → On eine funktionale Klasse mit F(x) = strsupy ∈ x F(y) für alle x.
Dann ist F(x) = rang(x) für alle x.
Übung
Für alle x gilt rang″t. c.(x) = rang(x).
Für jedes x hat also t. c.(x) ⊆ Vrang(x) keine Lücken in der Vα-Hierarchie bis hinauf zu rang(x). Diese Eigenschaft charakterisiert die Rangfunktion:
Übung
Sei F : V → On, und es gelte F″t. c.(x) = F(x) für alle x.
Dann gilt F(x) = rang(x) für alle x.
Übung
Sei x eine transitive Menge. Wir definieren rekursiv für alle α ∈ On:
A0 = ∅, Aα + 1 = ℘(Aα) ∩ x, Aλ = ⋃α < λ Aα.
Dann gilt:
| (a) | Aα = Vα ∩ x | für alle α ∈ On |
| (b) | Aα = x | für alle α ≥ rang(x) |
| (c) | Aα + 1 − Aα ≠ ∅ | für alle α < rang(x) |
Speziell lässt sich der Rang einer Menge y aus ihrem transitiven Abschluss x = t. c.(y) errechnen: Der Rang von y ist gleich dem Rang von x, und dieser ist das kleinste α mit Aα = x. Anders formuliert: Für die Komplexität einer Menge x spielen nur die Mengen in t. c.(x) eine Rolle.
Das Fundierungsaxiom ist schließlich äquivalent zur Existenz von Komplexitätsbewertungen, die die ∈ -Relation respektieren:
Übung
Äquivalent zu (Fun) über ZF ist die Aussage:
Für alle x gibt es ein f : x → On, sodass für alle y, z ∈ x gilt:
y ∈ z impliziert f (y) < f (z).
Das Zurückschneiden von Klassen
Das Fundierungsaxiom erlaubt uns ein uniformes Zurückschneiden von nichtleeren Klassen zu nichtleeren Mengen. Diese Beobachtung geht auf Alfred Tarski zurück und wurde von Dana Scott 1955 zur „Definition durch Abstraktion“ verwendet, die insbesondere eine Kardinalzahldefinition in ZF liefert. Wir definieren:
Definition (φcut, Acut)
Für eine Formel φ(x) sei φcut(x) die folgende Formel:
„φ(x) ∧ ∀y. φ(y) → rang(x) ≤ rang(y)“
Ist A = { x | φ(x) }, so sei Acut = { x | φcut(x) }.
Ist A eine nichtleere Klasse, so ist Acut eine nichtleere Menge, denn es gilt Acut ⊆ Vα + 1 für α = min({ α ∈ On | es gibt ein x ∈ A mit rang(x) = α }, und Acut enthält alle rangminimalen Elemente von A (und damit mindestens ein Element von A). Genauer gilt Acut = (Vα + 1 − Vα) ∩ A, wobei α minimal ist mit Vα + 1 ∩ A ≠ ∅.
Beim Arbeiten mit Äquivalenzrelation auf echten Klassen sind die Äquivalenzrelationen oft selbst echte Klassen, und wir können dann nicht frei mit ihnen operieren. Die Schnitt-Methode liefert eine Möglichkeit, die Äquivalenzklassen zu Mengen zurückzuschneiden, ohne ihre charakteristische Information zu verlieren. Die so gestutzten Äquivalenzklassen können so als abstrakte (Rechen-) Zeichen verwendet werden:
Satz („Zeichengeneration“ für Äquivalenzrelationen)
Sei A eine Klasse, und sei ∼ ⊆ A2 eine Äquivalenzrelation auf A, d. h. ∼ ist eine reflexive, symmetrische und transitive relationale Klasse. Dann existiert eine funktionale Klasse F : A → V mit der Eigenschaft:
(#) Für alle x, y ∈ A gilt: F(x) = F(y) gdw x ∼ y.
Beweis
Für alle x ∈ A sei F(x) = { z ∈ A | x ∼ z }cut. Dann ist F wie gewünscht:
F(x) ∼ F(y) impliziert x ∼ y : Seien x, y ∈ A mit F(x) = F(y). Sei z ∈ F(x) beliebig. Dann gilt x ∼ z und y ∼ z, also x ∼ z.
x ∼ y impliziert F(x) = F(y) : Seien x, y ∈ A mit x ∼ y. Dann ist
F(x) = { z ∈ A | x ∼ z }cut = { z ∈ A | y ∼ z }cut = F(y).
Ein wichtiger Spezialfall ist die Äquivalenzrelation der Gleichmächtigkeit auf ganz V. Die Methode liefert dann:
Definition (Kardinalzahldefinition in ZF, cardZF(x))
Für alle x ∈ V setzen wir:
cardZF(x) = { y | |x| = |y| }cut.
Die Menge cardZF heißt die ZF-Mächtigkeit oder ZF-Kardinalität von x.
Für alle x, y gilt unter dieser Definition wie gewünscht:
(#) cardZF(x) = cardZF(y) gdw „es gibt eine Bijektion f : x → y“.
Damit haben wir eine formale Definition der Mächtigkeit oder Kardinalität einer Menge in der Theorie ZF gegeben. Sie ist ganz im Sinne der Hausdorffschen Zeichenzuordnung, bei der jeder Menge x ein prinzipiell beliebiges Zeichen zugeordnet wird derart, dass Mengen derselben Mächtigkeit und nur solche dasselbe Zeichen erhalten. Im Gegensatz zu Hausdorff haben wir nun die Zeichen auch wirklich definiert und nehmen sie nicht mehr selbstverständlich oder unproblematisch an. Das x zugeordnete Kardinalitäts-Zeichen ist die − insgesamt recht verwickelt definierte − Menge cardZF(x).
Die Verwendung des Fundierungsaxioms ist hier wesentlich: Levy hat gezeigt, dass es in der Theorie T = ZF − (Fun) keine Kardinalzahldefinition gibt, d. h. man kann in dieser Theorie keine funktionale Klasse cardT : V → V definieren, die für alle x, y die Äquivalenz (#) erfüllt.
Die Kardinalzahldefinition in ZF ist nicht repräsentierend, d. h. es gilt i. A. nicht, dass |cardZF(x)| = |x|. Im nächsten Kapitel werden wir eine repräsentierende Kardinalzahldefinition geben, die das Auswahlaxiom verwendet (nicht aber das Fundierungsaxiom).
Übung
Für eine relationale Klasse R sind dom(R) und rng(R) wie für Mengenrelationen definiert, d. h. dom(R) = { x | es gibt ein y mit (x, y) ∈ R } und rng(R) = { y | es gibt ein x mit (x, y) ∈ R }.
Sei nun E ⊆ V2 eine relationale Klasse. Dann gibt es relationale Klassen L und R mit den Eigenschaften:
(i) | Für alle x ist { y | y L x } eine Menge und es gilt rng(L) = rng(E). |
(ii) | Für alle x ist { y | x R y } eine Menge und es gilt dom(R) = dom(E). |
Das Kollektionsschema
Eine weitere Anwendung des Zurückschneidens von echten Klassen ist das folgende Kollektionsschema, das eine Alternative zum Ersetzungsschema darstellt. Wir werden es im nächsten Abschnitt gewinnbringend verwenden.
Kollektionsschema (Kol)
Für jede Formel φ(u, v, p1, …, pn) gilt:
∀x, p1, …, pn ∃y ∀u ∈ x. ∃v φ(u, v, p1, …, pn) → ∃v ∈ y φ(u, v, p1, …, pn).
Das Kollektionsschema liefert uns also für jede Menge x eine Menge y, die für alle u ∈ x einen Zeugen für die Eigenschaft φ(u, v) als Element enthält, falls es überhaupt irgendeinen solchen Zeugen gibt. Alle derartigen Zeugen bilden i. A. eine echte Klasse C = { v | es gibt ein u ∈ x mit φ(u, v) }, aber durch das Kollektionsschema können wir die Klasse C so zu einer Menge y beschränken, dass sich für jedes u ∈ x mindestens ein Zeuge in y befindet, wenn es überhaupt einen zu u gehörigen Zeugen gibt.
Selbst unter (AC) gibt es keinen unmittelbaren Beweis für diese Zeugenbeschränkung. Wir können nicht einfach setzen:
f (u) = „ein v mit φ(u, v)“ für alle u ∈ v, y = rng(f),
denn das Auswahlaxiom erlaubt uns nur aus Mengen zu wählen, und die von u abhängigen Klassen { v | φ(u, v) } sind im Allgemeinen echt.
Satz
Das Kollektionsschema ist in ZF beweisbar.
Beweis
Sei φ(u, v) eine Formel wie im Kollektionsschema (wir unterdrücken die Parameter). Sei x eine beliebige Menge. Wir setzen:
y = ⋃u ∈ x { v | φ(u, v) }cut.
Die Menge y existiert nach Ersetzungsschema, denn es gilt y = ⋃ H″x für die funktionale Klasse H : V → V mit H(u) = { v | φ(u, v) }cut für alle u. Weiter ist y wie gewünscht, denn ist { v | φ(u, v) } ≠ ∅, so ist auch { v | φ(u, v) }cut ≠ ∅.
Umgekehrt gilt:
Übung
In ZF − (Ers) + (Kol) gilt das Ersetzungsschema.
[ Der Beweis verwendet eine schwache Form der Aussonderung. Anders als das Ersetzungsschema impliziert das Kollektionsschema das Aussonderungsschema nicht. ]
Wir werden im Kapitel über wohlfundierte Relationen noch einmal auf das Fundierungsaxiom zurückkommen, und insbesondere eine Induktion und Rekursion über die Relation ∈ diskutieren und beweisen.
Ordinalzahlarithmetik
Die Operationen der Addition, Multiplikation und Exponentiation von Ordinalzahlen lassen sich sowohl rekursiv als auch direkt definieren. Wir stellen die Definitionen und wichtigsten Resultate zusammen.
Definition (Ordinalzahlarithmetik)
Wir definieren rekursiv für α, β ∈ On und Limiten λ:
α + 0 = α, α + (β + 1) = (α + β) + 1, α + λ = supβ < λ α + β,
α · 0 = 0, α · (β + 1) = (α · β) + α, α · λ = supβ < λ α · β,
α0 = 1, αβ + 1 = αβ · α, αλ = supβ < λ αβ.
Die Addition und Multiplikation ist nicht kommutativ. Es gilt das Distributivgesetz α(β + γ) = αβ + αγ, dagegen ist i. A. (α + β)γ ≠ αγ + βγ. Für die Exponentiation gilt αβ + γ = αβ + αγ und (αβ)γ = αβγ, dagegen ist i. A. (αβ)γ ≠ αγ βγ.
Alle drei Operationen lassen sich auch ohne die Verwendung von Rekursion einführen: Die Addition lässt sich über die Summe zweier Wohlordnungen definieren, die Multiplikation über die Produktbildung, und die Exponentiation über die natürliche Exponentiation zweier Wohlordnungen nach Hausdorff und Hessenberg:
Definition (direkte Ordinalzahlarithmetik)
Für α, β ∈ On seien:
S = α × { 0 } ∪ β × { 1 },
P = α × β,
E = { f : β → α | f (γ) ≠ 0 für höchstens endlich viele γ < β }.
Wir definieren <S, <P, <E auf S, P, E durch:
| (γ, i) <S (δ, j), | falls i < j oder i = j und γ < δ, |
| (γ1, δ1) <P (γ2, δ2), | falls δ1 < δ2 oder δ1 = δ2 und γ1 < γ2, |
| f <E g, | falls f ≠ g und f (δ) < g(δ) für δ = max({ η | f (η) ≠ g(η) }). |
Es gilt
o. t.(〈 S, <S 〉) = α + β, o. t.(〈 P, <P 〉) = α · β, o. t.(〈 E, <E 〉) = αβ,
wie man unschwer durch Induktion nach β bei fest gehaltenem α zeigt.
Die direkten Definitionen liefern unmittelbar:
Satz (Invarianz der Kardinalität der Ordinalzahlarithmetik)
Seien α, β, γ, δ ∈ On mit |α| = |γ| und |β| = |δ|. Dann gilt:
|α + β| = |γ + δ|, |α · β| = |γ · δ|, |αβ| = |γδ|.
Viele Ordinalzahlen sind abgeschlossen unter arithmetischen Operationen:
Satz (additiv abgeschlossene Ordinalzahlen)
Für alle λ ≥ ω sind äquivalent:
(i) | λ ist additiv abgeschlossen (d. h. α + β < λ für alle α, β < λ). |
(ii) | λ = ωα für ein α ≥ 1. |
(iii) | α + λ = λ für alle α < λ. |
Satz (multiplikativ abgeschlossene Ordinalzahlen)
Für alle λ ≥ ω sind äquivalent:
(i) | λ ist multiplikativ abgeschlossen (d. h. α · β < λ für alle α, β < λ). |
(ii) | λ = ω(ωβ) für ein β ∈ On. |
(iii) | β · λ = λ für alle 1 ≤ β < λ. |
Die Beweise dieser Aussagen sind eine gute Übung.
Satz (exponentiell abgeschlossene Ordinalzahlen)
Für alle λ ≥ ω sind äquivalent:
(i) | λ ist exponentiell abgeschlossen (d. h. αβ < λ für alle α, β < λ). |
(ii) | λ = γλ für alle 2 ≤ γ < λ. |
(iii) | λ = γλ für ein 2 ≤ γ < λ. |
Beweis
(i) ↷ (ii): Für alle 2 ≤ γ < λ gilt λ ≤ γλ = supβ < λ γβ ≤(i) λ.
(ii) ↷ (iii): Ist trivial.
(iii) ↷ (i): Sei 2 ≤ γ < λ mit λ = γλ. Dann ist λ additiv abgeschlossen, da
α + α ≤ 2α + 2α = 2α + 1 ≤ γα + 1 < γλ = γ für alle α < λ.
Weiter ist λ multiplikativ abgeschlossen, denn für alle α < λ ist
α · α ≤ 2α · 2α = 2α + α ≤ γα + α < αλ = λ.
Seien nun α, β < λ. Dann ist
αβ ≤ (γα)β = γα · β ≤ γλ = λ.
Definition (ε-Zahl)
Eine Ordinalzahl α > ω heißt eine Epsilon-Zahl, falls α = ωα.
Die exponentiell abgeschlossenen unendlichen Ordinalzahlen sind also nach obigem Satz genau ω und die ε-Zahlen. Für jede Ordinalzahl β0 ≥ ω ist
α = supn ∈ ω βn mit βn + 1 = ωβn für alle n ∈ ω
die kleinste ε-Zahl, die größer oder gleich β ist. Die erste ε-Zahl ε0 = ωωω… werden wir unten noch genauer betrachten.
Die drei arithmetischen Operationen erlauben die folgenden vielfach nützlichen Darstellungen von Ordinalzahlen:
Satz (allgemeine Normaldarstellung)
Sei η ∈ On, η ≥ 2. Dann lässt sich jedes γ ∈ On eindeutig schreiben als:
(#) γ = ηα1 ν1 + … + ηαk νk,
mit k ∈ ω, α1 > α2 > … > ακ ≥ 0, 0 < νi < η.
Zum Beweis wählt man α1 maximal, sodass ηα1 ≤ γ. Nun wählt man ν1 maximal mit ηα1 ν1 ≤ γ. Analog seien nun α2 und ν2 maximal, sodass ηα1 ν1 + ηα2 ν2 ≤ α. Iteration dieses Verfahrens liefert die Darstellung (#). Die Eindeutigkeit ist klar.
Definition (Cantorsche Normalform)
Für alle η ≥ 2 und alle γ ∈ On heißt die Darstellung (#) von η die Cantorsche Normalform von β zur Basis η oder kurz die η-Normalform. Die Zahl k heißt die Länge der Darstellung. Die Zahlen αi und νi heißen die Exponenten bzw. Koeffizienten der Darstellung.
Übung
Zwei Zahlen γ und δ in Normaldarstellung (zu einer gemeinsamen Basis η) können ihrer Größe nach verglichen werden, indem man ihre Exponenten und Koeffizienten in der offensichtlichen Weise von links nach rechts auswertet.
Lange abzählbare Wohlordnungen
Eine Wohlordnung auf ω des Typs ωω
Wir konstruieren eine einfache Wohlordnung <* auf M = ω − { 0, 1 }, die den Ordnungstyp ωω besitzt. Dann ist f : ω → ωω mit f (n) = o. t.({ m | m <* n + 2 }) für alle n ∈ ω eine Bijektion.
Zur Definition von <* schreiben wir die Elemente von M in ihrer Primfaktorzerlegung, wobei wir Vielfachheiten ausschreiben und die Faktoren wie üblich der Größe nach anordnen. Z. B. schreiben wir 12 = 2 · 2 · 3. Wir ordnen nun die so dargestellten Zahlen wie folgt: Hat n weniger Faktoren als m, so sei n <* m. Haben n und m gleichviele Faktoren, so entscheidet die Größe des ersten unterschiedlichen Faktors. So ist 3 <* 2 · 2 und 2 · 2 · 5 <* 2 · 3 · 3. Die Ordnung <* beginnt mit der Reihe der Primzahlen 2, 3, 5, …, gefolgt von 4, 6, 10, …
Übung
(i) | Für alle n ≥ 1 gilt o. t.({ m | m <* 2n + 1 }) = ωn. |
(ii) | Es gilt o. t.(〈 M, <* 〉) = ωω. |
Der Leser vergleiche die Ordnung <* mit der exponentiellen Ordnung <E auf E = { f ∈ ωω | f (n) ≠ 0 für höchstens endlich viele n }, die wir als Ordnung auf N = ω − { 0 } auffassen können, wenn wir ein f ∈ E mit Πn ∈ ω pnf (n) ∈ N identifizieren, wobei 〈 pn | n ∈ ω 〉 die monotone Aufzählung aller Primzahlen ist, also p0 = 2, p1 = 3, usw. (Hier ist wie üblich Πn ∈ ω 0 = 1.) Auch diese Ordnung hat, wie wir wissen, den Typ ωω.
Eine Wohlordnung auf ω des Typs ε0
Sei ε0 die erste ε-Zahl, also ε0 = supn ∈ ω xn, wobei x0 = ω und xn + 1 = ωxn für alle n ∈ ω. Ist α < ε0 und α = ωα1 n1 + ... + ωαk nk die Cantorsche Normaldarstellung von α zur Basis ω, so ist α1 < α. Diese Eigenschaft ermöglicht uns, α < ε1 durch eine natürliche Zahl n zu kodieren. Hierzu sei wieder 〈 pn | n ∈ ω 〉 die monotone Aufzählung aller Primzahlen.
Eine rekursive Kodierung aller Ordinalzahlen unterhalb von ε0 durch natürliche Zahlen erhalten wir wie folgt:
Definition (die Funktion b : ε0 → ω)
Wir definieren b : ε0 → ω rekursiv für α < ε0 durch:
b(0) = 0,
b(α) = pb(α1)n1 · pb(α2)n2 · … · pb(αk)nk − 1 für alle α > 0, wobei
α = ωα1 n1 + … + ωαk nk die ω-Normalform von α ist.
Umgekehrt definieren wir:
Definition (die Funktion c : ω → ε0)
Wir definieren c : ω → ε0 rekursiv für n < ω durch:
| c(0) = | 0 | |
| c(n) = | „die nach abfallenden Exponenten c(i) geordnete ordinale | |
| Summe aller ωc(i) ei, i ≤ k“, | für alle n ≥ 1, wobei: | |
| n + 1 = p0e0 · p1e1 · ... · pkek, mit ei ≥ 0 für alle i < k und ek ≠ 0 |
Es gilt c(n) = ωc(0) e0 # ωc(1) e1 # ... # ωc(k) ek für die Hessenberg-Summe # (s. u.).
Es ist instruktiv, die ersten Werte c(0), c(1), c(2), … zu berechnen. Es gilt:
Übung
Es gilt c ∘ b = id|ε0 und b ∘ c = id|ω.
Die Funktion b ist also eine bijektive Kodierung der Ordinalzahlen unterhalb von ε0 durch natürliche Zahlen, und c ist die zugehörige Dekodierung.
Paarungsfunktionen
Eine wichtige arithmetische Konstruktion ist die kanonische Wohlordnung von On × On und die zugehörige Paarungsfunktion:
Definition (die Ordnung ≺ und die Γ-Funktion)
Für α, β, γ, δ ∈ On setzen wir (α, β) ≺ (γ, δ), falls
(i) | max(α, β) < max(γ, δ), oder |
(ii) | max(α, β) = max(γ, δ), α < γ, oder |
(iii) | max(α, β) = max(γ, δ), α = γ, β < δ. |
Für α, β ∈ On seien:
W(α, β) = { (γ, δ) | (γ, δ) ≺ (α, β) }
Γ(α, β) = o. t.(〈 W(α, β), ≺ 〉)
Die funktionale Klasse Γ ist eine Bijektion von On × On nach On. Daneben ist auch Γ|α2 : α2 → α bijektiv für viele Ordinalzahlen α. Neben 0 und 1 sind dies genau die multiplikativ abgeschlossenen unendlichen Zahlen:
Satz (Bijektionen der Γ-Funktion)
Für alle Ordinalzahlen λ ≥ ω sind äquivalent:
(i) | Γ|λ2 → λ ist bijektiv. |
(ii) | Γ(0, λ) ≤ λ. |
(iii) | λ ist multiplikativ abgeschlossen. |
Beweis
Vorab halten wir fest: Es gilt Γ(0, α) = Γ″α2 für alle α. Mit g(α) = Γ(0, α) gilt
g(0) = 0, g(α + 1) = g(α) + α + α + 1, g(λ) = supα < λ g(α).
Weiter ist Γ(0, λ) ≤ λ gleichwertig zu Γ(0, λ) = λ.
Die Äquivalenz von (i) und (ii) ist klar.
zu (ii) ↷ (iii):
Offenbar ist λ ein Limes. Für alle α < λ ist α + α ≤ g(α + 1) ≤ g(λ) ≤ λ, also ist λ additiv abgeschlossen. Weiter ist λ auch multiplikativ abgeschlossen, denn für alle α < λ lässt sich α × α unter der multiplikativen Ordnung ordnungstreu in die Γ-Aufzählung von λ × λ einbetten (betrachte das Segment { (β, γ) | α ≤ β < α + α, γ < α } von λ × λ).
zu (iii) ↷ (ii):
Der Fall λ = ω ist klar. Sei also λ > ω. Sei α < λ. Dann gibt es ein additiv abgeschlossenes β mit α < β < λ. Dann ist g(α) ≤ β · β < λ, da sich die Γ-Ordnung auf α × α ordnungstreu in die multiplikative Ordnung auf β × β einbetten lässt (die Γ-Ordnung auf dem Produkt α × α besteht aus α-vielen Summanden der Länge kleinergleich α + α + 1 < β). Also ist g(λ) = supα < λ g(α) ≤ λ.
Die Hessenberg-Summe und die Paarungssumme &
Aus der Cantorschen Normaldarstellung zur Basis ω erhalten wir eine weitere Paarungsfunktion, die uns Paarungsbijektionen für alle additiv abgeschlossenen Ordinalzahlen liefert und in diesem Sinne der Γ-Funktion überlegen ist:
Definition (die Hessenberg-Summe # und die Paarungssumme &)
Wir definieren +H, & : On2 → On für alle γ, δ ∈ On durch:
| #(γ, δ) | = ωα1 · (n1 + m1) + ... + ωαk · (nk + mk) |
| &(γ, δ) | = ωα1 · π(n1, m1) + ... + ωαk · π(nk, mk) |
wobei π : ω2 → ω die Cantorsche Paarungsfunktion auf ω ist, und
γ = ωα1 n1 + ... + ωαk · nk, δ = ωα1 m1 + ... + ωαk · mk
die eindeutigen ω-Normaldarstellungen von γ und δ mit gemeinsamen Exponenten sind (hier ist mi = 0 oder ni = 0 möglich, nicht aber ni = mi = 0).
Die funktionale Klasse # heißt die Hessenberg-Summe.
Die funktionale Klasse & : On2 → On ist bijektiv und monoton in beiden Argumenten. Leicht zu sehen ist weiter:
Satz (Bijektionen der &-Funktion)
Für alle λ ≥ ω sind äquivalent:
(i) | λ ist additiv abgeschlossen. |
(ii) | &|λ2 : λ2 → λ ist bijektiv. |
Übung
Es gibt eine funktionale Klasse P : On → V mit: Für alle α ≥ ω ist P(α) eine Bijektion von α2 nach α.
Die Hessenberg-Summe ist keine Bijektion, aber dennoch nützlich und natürlich: Wir ordnen die Summanden zweier Zahlen in Normaldarstellung nach abfallenden Exponenten, und summieren dann mit der üblichen Addition auf.
Beispiele
ω2 # ω4 # ω3 # ω4 = ω4 · 2 + ω3 + ω2
ω2 + ω4 + ω3 + ω4 = ω4 · 2.
Die wichtigsten Eigenschaften und eine Charakterisierung der Hessenberg-Summe diskutieren wir in den beiden folgenden Übungen.
Übung
(i) | Die Hessenberg-Summe # ist kommutativ und assoziativ. |
(ii) | Für alle α, β ∈ On ist α + β ≤ α # β. |
(iii) | Für alle γ ∈ On ist { (α, β) | α # β = γ } endlich. |
(iv) | # ist streng monoton in der zweiten Kompoente, d. h. für alle α, β, γ mit β < γ ist α # β < α # γ. |
(v) | Ist F : On2 → On kommutativ und streng monoton, so gilt F(α, β) ≥ α # β für alle α, β. |
Übung
Für alle α0, …, αn ∈ On gilt:
α0 # … # αn = sup({ o. t.(⋃i ≤ n ai) | ai ⊆ On, o. t.(ai) = αi für alle i ≤ n }).
Endliche Mengen und Folgen von Ordinalzahlen
Wir wollen nun noch endliche Mengen { α1, …, αk } und endliche Folgen 〈 α1, …, αk 〉 von Ordinalzahlen in bijektiver Weise durch Ordinalzahlen kodieren. Hierzu setzen wir:
Definition (die Klassen < ω[ On ], < ωOn)
Wir setzen:
< ω[ On ] = { x ⊆ On | x ist endlich }
< ωOn = { f : n → On | n ∈ ω }
Eine endliche Menge von Ordinalzahlen können wir mit einer strikt aufsteigenden endlichen Folge von Ordinalzahlen identifizieren. Unter dieser Identifikation ist also < ω[ On ] eine Teilklasse von < ωOn. Umgekehrt ist eine endliche Folge von Ordinalzahlen eine endliche Teilmenge von On2, die wir durch Kodierung mit Hilfe von Γ oder & als eine endliche Menge von Ordinalzahlen auffassen können. Die Klassenversion des Satzes von Cantor-Bernstein liefert also eine Bijektion zwischen < ω[ On ] und < ωOn.
Wir geben nun noch einfache Bijektionen von < ω[ On ] nach On und von < ωOn nach On an.
Definition (die Funktion Γfin)
Für alle { α1, …, αk } ⊆ On mit α1 > α2 > … > αk setzen wir:
Γfin({ α1, …, αk }) = 2α1 + … + 2αk
Nach dem Satz über die Cantorsche Normalform zur Basis 2 ist die funktionale Klasse Γfin : < ω[ On ] → On bijektiv. Es gilt Γfin(0) = 0 und Γfin({ 0 }) = 1.
Die Klasse < ωOn aller endlichen Folgen von Ordinalzahlen können wir analog zu On2 behandeln:
Definition (die Ordnung ≺seq und die Γseq-Funktion)
Wir definieren eine Relation ≺seq auf On< ω durch:
| s ≺seq t, falls | max(s) < max(t) oder |
| max(s) = max(t) und |s| < |t| oder | |
| max(s) = max(t) und |s| = |t| und s(δ) < t(δ), | |
| wobei δ = δ(s, t) = „das kleinste n mit s(n) ≠ t(n)“ |
Für jedes s ∈ < ωOn seien:
Wseq(s) = { ( t ∈ < ωOn | t ≺seq s },
Γseq(s) = o. t.(〈 Wseq(s), ≺ 〉).
Die funktionale Klasse Γseq : < ωOn → On ist bijektiv.
Übung
Bestimmen Sie diejenigen α ∈ On, für die gilt:
(i) | Γfin|< ω[ α ] : < ω[ α ] → α ist bijektiv, |
(ii) | Γseq|< ωα : < ωα → α ist bijektiv, |
wobei < ω[ α ] = { x ⊆ α | x ist endlich } und < ωα = { f : n → α | n ∈ ω }.