Vorlesung über Mengenlehre

Martin Ziegler^{∗}^{†} Wintersemester 1992/1993, 2013/2014

Inhaltsverzeichnis

1 Die Axiome von Bernays-Gödel 3 2 Wohlordnungen 12 3 Ordinalzahlen 15 4 Ordinalzahlarithmetik 18 5 Die natürlichen Zahlen und die v. Neumann Hierarchie 22 6 Kardinalzahlen 25 7 Kardinalzahlexponentiation 29 8 Clubs und stationäre Mengen 33 9 Der Satz von Silver 37 10 Pfeilrelationen 39 11 Der Satz von König 42 12 Schwach kompakte Kardinalzahlen 44 13 Meßbare Kardinalzahlen 47 14 Transitive Modelle der Mengenlehre 51 15 V=L 58 16 Änderungen 68

∗Version 7bis (30. Januar 2014)

†v7-25-g25e56e2, Thu Jan 30 13:34:56 2014 +0100

2

1 Die Axiome von Bernays-Gödel

Die betrachteten Gegenstände unserer Theorie heißen Klassen, die wir mit Variablen A, B, …, X, Y, Z bezeichnen. Klassen können Elemente von einander sein. Wir schreiben

A ∈ B

für “A ist Element von B”.

Die naive Mengenlehre (im Sinne von [1]) hat zwei Axiome:

Axiom (Extensionalität) Zwei Klassen, die dieselben Elemente haben, sind gleich.

Axiom (Naives Komprehensionsaxiom) Zu jeder Eigenschaft von Klassen gibt es eine Klasse, deren Elemente genau die Klassen mit dieser Eigenschaft sind.

Wegen des Extensionalitätsaxioms ist diese Klasse eindeutig bestimmt.

Satz 1.1 (Russellsches Paradox) Die naive Mengenlehre ist widersprüchlich.

Beweis:

Sei R die Klasse aller Klassen, die sich selbst nicht als Element enthalten; für die also

A ∈ R ⟺ A ∉ A.

Dann hat man das unmögliche

R ∈ R ⟺ R ∉ R.
□

Der in der Bernays–Gödelschen Mengenlehre BG vorgeschlagene Ausweg besteht darin, “kleine” Klassen, Mengen, auszuzeichnen und als Elemente von Klassen \underline{nur Mengen} zuzulassen. Mengen bezeichnen wir mit kleinen Buchstaben a, b, … x, y, z. (Vergleiche dazu die Artikel von Paul Bernays A system of axiomatic set theory I-VII im Journal of Symbolic Logic, Bände 2,6,7,8,13 und 19.)

Das Komprehensionsaxiom von BG ist

Axiom (Komprehension) Zu jeder Eigenschaft von Mengen gibt es eine (wegen des Extensionalitätsaxioms eindeutig bestimmte) Klasse, deren Elemente genau die Mengen mit dieser Eigenschaft sind.

Wir schreiben

{x | E(x)}

für die Klasse aller Mengen x, die die Eigenschaft E haben.

Wir werden gleich sehen, daß Extensionalität und Komprehension keinen Widerspruch ergeben können. Der Grund ist aber leider, daß die beiden Axiome allein viel zu schwach sind, um unsere Vorstellung von der Welt der Mengen und Klassen zu formalisieren. BG besteht aus einer Reihe weiterer Axiome, die wir in diesem Kapitel vorstellen.

Damit die Mengenlehre eine Theorie im Sinne der Prädikatenlogik ist (und die Beweise im Prädikatenkalkül formalisierbar) müssen ihre Axiome elementare Aussagen sein: Die Sprache von BG hat ein Prädikat Men für “Menge sein” und ein Relationszeichen ϵ für die Elementbeziehung. Unsere Konvention, daß Klassen nur Mengen enthalten können, drückt sich dann durch

∀X∀Y X ϵ Y ⟶ Men(X)

aus. Das Extensionalitätsaxiom ist

∀X ∀Y (∀x(x ϵ X ⟷ x ϵ Y)) ⟶ X =^{.} Y.

Um das Komprehensionsaxiom elementar auszudrücken zu können, müssen wir uns darauf festlegen, nur elementare – also durch Formeln – ausdrückbare Eigenschaften von Mengen zuzulassen. BG fordert eine weitere Einschränkung: Wir betrachten im Komprehensionsaxiom nur beschränkte Formeln, in denen alle Quantoren nur über Mengen laufen – das heißt, nur in der Form ∀x (Men(x) ⟶ …) und ∃x (Men(x) ∧ …) vorkommen. Für jede beschränkte Formel ϕ(X_{0}, …, X_{n}) in der Sprache von BG haben wir dann ein elementares Komprehensionsaxiom

∀X_{1} … ∀X_{n} ∃Y ∀X_{0} (X_{0} ϵ Y ⟷ (Men(X_{0}) ∧ ϕ(X_{0}, …, X_{n}))) .

Das Komprehensionsaxiom ist also nicht ein einzelnes Axiom, sondern ein Axiomenschema. Läßt man beliebige Formeln zu, erhält man die Morse–Kelley–Mengenlehre.

Man überzeugt sich leicht, daß sich auch die übrigen Axiome von BG, die wir in diesem Kapitel angeben, elementar formulieren lassen.

Logischer Exkurs Wenn man in einer Theorie T für eine Formel ϕ

∀x_{1}, …, x_{n}∃!x_{0}ϕ(x_{0}, …, x_{n})

beweisen kann (∃! bedeutet “es gibt genau ein”), geht man häufig zu einer definitorischen Erweiterung T über. Man führt ein neues n–stelliges Funktionszeichen f_{ϕ} ein und erweitert T um das Axiom

∀x_{1} … ∀x_{n} ϕ(f_{ϕ}(x_{1}, …, x_{n}), x_{1} …, x_{n}).

Jede Formel der erweiterten Sprache ist in T_{ϕ} zu einer Formel der alten Sprache äquivalent. Außerdem ist T_{ϕ} eine konservative Erweiterung von T: Jede Aussage der alten Sprache, die sich in T_{ϕ} beweisen läßt, ist auch in T beweisbar. Wir machen im folgenden von diesem Prinzip stillschweigend extensiven Gebrauch. Die oben eingeführte Klassenklammer zum Beispiel,

{y | ψ(y, x_{1}, …, x_{n})} ,

ist ein durch die Formel

ϕ(X_{0}, …, X_{n}) = ∀Z (Z ϵ X_{0} ⟷ (Men(Z) ∧ ψ(Z, X_{1}, …, X_{n})))

definiertes neues Relationszeichen.

Aus unseren beiden Axiomen folgt die Existenz von zwei Klassen:

Notation V ist die Allklasse {x | x =^{.} x}. ∅ ist die leere Klasse {x | ¬x =^{.} x}.

Die Existenz von V hat zur Folge, daß jede Menge Element einer Klasse ist. Also ist eine Klasse A genau dann eine Menge, wenn sie Element einer Klasse ist. “Menge” ist daher als Grundbegriff eigentlich überflüssig. Statt “A ist Menge” schreiben wir auch “A ∈ V”.

Das Russellsche Paradox wird ein Lemma:

Lemma 1.2 Es gibt eine echte Klasse.

Beweis: Die Klasse R aller Mengen, die sich nicht selbst als Element enthalten, kann keine Menge sein. □

Notation Für Klassen A und B bedeutet

• A ⊂ B, A ist Teilklasse (oder wenn A eine Menge ist: Teilmenge) von B, daß alle Elemente von A auch Elemente von B sind.

• A ∪ B = {x | x ∈ A oder x ∈ B} die Vereinigung von A und B.

• A∩B = {x | x ∈ A und x ∈ B} der Durchschnitt. Zwei Klassen heißen disjunkt, wenn ihr Durchschnitt leer ist.

• A \ B = {x | x ∈ A und x ∉ B} die Differenz von A und B.

• Ā = {x | x ∉ A} das Komplement von A.

• ⋃ A = {x | ∃ y x ∈ y ∧ y ∈ A} die Vereinigung der Elemente von A.

• ⋂ A = {x | ∀ y y ∈ A → x ∈ y} der Durchschnitt der Elemente von A.

• 𝔓(A) = {x | x ⊂ A} die Potenzklasse von A.

Mengenlehre in der Schule beschäftigt sich mit Theoremen wie zum Beispiel

\overline{A ∪ B} = Ā ∩ B̄,

eine der sogenannte de Morganschen Regeln.

Das Aussonderungsaxiom drückt aus, daß Mengen kleine Klassen sind.

Axiom (Aussonderung)

a ∩ A ∈ V

Folgerung 1.3 1. V ∉ V

2. A ≠ ∅ ⟹ ⋂ A ∈ V

Beweis:

1. Die Russelsche Klasse ist eine Teilklasse von V.

2. Wenn a ∈ A, ist a ∩ ⋂ A = ⋂ A. □

Ein Modell der bisherigen Axiome ist

𝔐_{0} = (M_{0}, E_{0}),

wobei M_{0} nur ein Element m hat und E_{0} leer ist. Es ist dann V^{𝔐_{0}} = m die einzige Klasse. m ist keine Menge in 𝔐_{0}.

Axiom (Leere Menge)

∅ ∈ V

Ein Modell muß jetzt mindestens zwei Elemente haben: Eine Interpretation von V und eine von ∅. M_{1} enthalte zwei Elemente a und b, E_{1} sei die zweistellige Relation, die nur zwischen a und b besteht. Dann ist in der Tat 𝔐_{1} = (M_{1}, E_{1}) ein Modell der bisherigen Axiome.

Für zwei Mengen a und b sei {a, b} = {x | x =^{.} a ∨ x =^{.} b} die Paarklasse aus a und b. Allgemeiner bezeichnet für eine Folge a_{0}, …, a_{n−1} von Mengen {a_{0}, …, a_{n−1}} die Klasse, deren Elemente gerade die a_{i} sind.

Axiom (Paarmenge)

{a, b} ∈ V

Wir können jetzt die ersten vier natürlichen Zahlen definieren: 0 = ∅, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}. Wir sollten eigentlich zwischen den “naiven” natürlichen Zahlen, von denen wir zum Beispiel bei der Definition der Ausdrücke {a_{0}, …, a_{n−1}} Gebrauch gemacht haben und den ihnen zugeordneten Termen in unserem formalen System BG unterscheiden. Wir sollten für diese Terme besser ⌜0⌝, ⌜1⌝ usw. schreiben.

Wir können auf der Basis der bisherigen Axiome noch nicht beweisen, daß 3 eine Menge ist. Zum Beispiel ist das System M_{2} aller Mengen (im naiven Sinn), die sich aus der leeren Menge durch iteriertes Anwenden der Paarbildung gewinnen lassen (die Mengen, die erblich höchstens zwei Elemente haben) zusammen mit allen anderen Teilmengen von M_{2} als echten Klassen ein Modell unserer Axiome, in dem 3 eine echte Klasse ist.

Axiom (Vereinigungsmenge)

⋃ a ∈ V

Wir können schließen, daß die Vereinigung a ∪ b = ⋃{a, b} zweier Mengen wieder eine Menge ist. Außerdem wissen wir jetzt, daß alle {a_{0}, …, a_{n−1}} Mengen sind: das folgt aus {a_{0}, …, a_{n}} = {a_{0}, …, a_{n−1}} ∪ {a_{n}} per Induktion.

Wir definieren rekursiv für jedes n die Menge ⌜n⌝ durch

⌜n⌝ = {⌜0⌝, …, ⌜n − 1⌝}.

Man zeigt leicht durch Induktion, daß alle ⌜n⌝ verschieden sind. Im folgenden schreiben wir einfach n für ⌜n⌝. Aus dem Kontext ergibt sich, ob wir eine natürliche Zahl unserer mathematischen Umgangssprache oder einen Term der Mengenlehre meinen.

Wir definieren nach Kuratowski das geordnete Paar

< a, b >= {{a, b}, {a}}.

Lemma 1.4 < a, b >=< a′, b′ > genau dann, wenn a = a′ und b = b′.

Beweis:

Sei c =< a, b >=< a′, b′ >. Wenn c nur ein Element hat, ist {a, b} = {a} = {a′, b′} = {a′}. Daraus folgt a = b = a′ = b′. Wenn c zwei Elemente hat, haben {a, b} und {a′, b′} jeweils zwei Elemente. Es folgt {a, b} = {a′, b′} und {a} = {a′}. Daraus folgt die Behauptung. □

Allgemeiner definiert man für alle positiven natürlichen Zahlen n das n–Tupel der Mengen x_{1}, …, x_{n} rekursiv durch

< x_{1} >= x_{1}

und

< x_{0}, …, x_{n} >=<< x_{0}, …, x_{n−1} >, x_{n} > .

Aus 1.4 folgt, daß zwei n–Tupel genau dann gleich sind, wenn sie dieselben Komponenten haben.

Axiom (Potenzmenge)

𝔓(a) ∈ V

Das cartesische Produkt A × B zweier Klassen ist definiert als {x | ∃a ∈ A, b ∈ B x =< a, b >}. Allgemeiner definieren wir A_{0} × … × A_{n} rekursiv durch A_{0} × … × A_{n} = (A_{0} × … × A_{n−1}) × A_{n}. Die n–fache cartesische Potenz von A sei mit A^{n} bezeichnet.

Aus dem Potenzmengenaxiom folgt

Folgerung 1.5 a_{0} × … × a_{n} ∈ V

Beweis:

Wenn x ∈ a und y ∈ b, sind {x, y} und {x} Elemente von 𝔓(a ∪ b) und folglich < x, y > ein Element von 𝔓(𝔓(a ∪ b)). a × b ist damit eine Teilklasse der Menge 𝔓(𝔓(a ∪ b)) und daher selbst eine Menge. Die Behauptung folgt daraus durch Induktion. □

Eine Klasse

R ⊂ V × V

von Paaren heißt Relation. Zum Beispiel sind ∈= {< x, y >| x ∈ y},∋= {< x, y >| y ∈ x} und =, die Gleichheit {< x, x >| x ∈ V}, Relationen. Wie hier schreiben wir auch für andere Relationen häufig

aRb

für < a, b >∈ R. Wir definieren das Bild einer Klasse A unter R als

R[A] = {y | ∃x ∈ A xRy}.

Eine Relation F heißt Funktional, wenn

xF y_{1}&xF y_{2} ⟹ y_{1} = y_{2}

für alle y_{1}, y_{2}. Die Gleichheit ist zum Beispiel ein Funktional.

Axiom (Ersetzungsaxiom) Für alle Funktionale F ist F [a] ∈ V.

Für beliebige Relationen R und Q definieren wir

1. R ↾ A = R ∩ (A × V) ist die Einschränkung von R auf A. Die Identität von A ist id_{A} = (=↾ A).

2. D(R) = {x | ∃y xRy}, der Definitionsbereich von R.

3. Wb(R) = {y | ∃x xRy}, der Wertebereich von R.

Es ist also F [A] = Wb(F ↾ A).

4. Q ∘ R = {w | ∃x, y, z xRy ∧ yQz ∧ w =^{.}< x, z >}, die Verknüpfung von Q mit R.

5. R^{−1} = {w | ∃x, y xRy ∧ w =^{.}< y, x >}, die inverse Relation.

Wenn Q und R Funktionale sind, haben die eben definierten Begriffe die übliche Bedeutung. Die Notation

F : A ⟶ B,

F ist ein Funktional von A nach B , bedeutet, daß F ein Funktional mit Definitionsbereich A ist, dessen Wertebereich in B liegt. Für Elemente a von A bezeichnet dann F (a) das eindeutig bestimmte Element b von B mit aF b (sonst sei F (a) = ∅). Wenn F auf A^{n} definiert ist, schreiben wir F (a_{1}, …, a_{n}) statt F (< a_{1}, …, a_{n} >). {F (a_{1} …, a_{n}) | E(a_{1}, …, a_{n})} ist die Klasse aller F (a_{1} …, a_{n}), mit a_{i} ∈ A und E(a_{1} …, a_{n}). Ein Funktional, das eine Menge ist, heißt Funktion.

Ein F : I ⟶ B nennt man auch eine mit Elementen von I indizierte Familie von Elementen von B und man schreibt F_{i} für F (i). Die Gleichung F = (F_{i} | i ∈ I) erläutert den Gebrauch von Ausdrücken der Form (… | …).

Das folgende Lemma macht noch keinen Gebrauch vom Ersetzungsaxiom.

Lemma 1.6

1. Wenn die Relationen q und r Mengen sind und a eine Menge ist, sind auch r ↾ a, D(r), Wb(r), q ∘ r, r^{−1} und id_{a} Mengen.

2. Wenn D(R) und Wb(R) Mengen sind, ist auch die Relation R eine Menge.

Beweis:

1. r ↾ a ist eine Teilklasse von r , also selbst eine Menge. Wenn < x, y >∈ r, ist {x, y} ∈ ⋃ r und daher x und y Elemente von ⋃ ⋃ r. D(r) und Wb(r) sind also Teilklassen von ⋃ ⋃ r. q ∘ r ist in D(r) × Wb(q), einer Menge nach Lemma 1.5, enthalten und also selbst eine Menge. r^{−1} ist Teilklasse von Wb(r) × D(r) und id_{a} Teilklasse von a × a.

2. R ist Teilklasse von D(R) × Wb(R). □

Folgerung 1.7 Wenn der Definitionsbereich eines Funktionals F eine Menge ist, ist F eine Funktion.

Beweis:

Wenn D(F) eine Menge ist, ist nach dem Ersetzungsaxiom Wb(F) = F [D(F)] eine Menge, also nach dem letzten Lemma auch F. □

Ein Funktional F : a ⟶ B ist also immer eine Funktion. Es macht daher Sinn die Klasse ^{a}B aller Funktionen von a nach B zu bilden. Weil ^{a}B ⊂ 𝔓(a × B), ist ^{a}B eine Menge, wenn B eine Menge ist.

Bis auf das Extensionalitätsaxiom kann man alle bisherigen Axiome als Spezialfälle des naiven Komprehensionsaxioms auffassen. Das gilt nicht für die letzten drei Axiome von BG: Das Fundierungsaxiom, das Unendlichkeitsaxiom und das Auswahlaxiom.

Axiom (Fundierungsaxiom) Jede nicht-leere Klasse A hat ein Element, das von A disjunkt ist.

Aus dem Fundierungsaxiom folgt, daß die Russelsche Klasse gleich der Klasse V aller Mengen ist: Wenn sich a selbst als Element enthielte, wären A = {a} und das einzige Element von A nicht disjunkt. Allgemeiner kann es für kein n eine Folge

x_{0} ∋ x_{1} ∋ … ∋ x_{n}

mit x_{0} = x_{n} geben. Die Menge A = {x_{0}, … x_{n−1}} würde sonst dem Fundierungsaxiom widersprechen. Das Fundierungsaxiom sagt, daß sich das Mengenuniversum V schrittweise so konstruieren läßt: Man startet mit der leeren Menge, dann nimmt man immer wieder alle Mengen hinzu, deren Elemente man schon konstruiert hat. Der nächste Satz, das Prinzip der ∈-Induktion, ist eine Präzisierung dieser Vorstellung.

Folgerung 1.8 V ist die einzige Klasse A, die alle Mengen enthält, deren Elemente zu A gehören.

Beweis:

Wenn B ≠ V, ist A = V \ B nicht leer. Das Fundierungsaxiom liefert ein x ∈ A, daß zu A disjunkt ist. Dann gehören die Elemente von x zu B, x selbst aber nicht. □

Übung 1.1 Sei 𝔓_{ω}(ℕ) die Menge aller endlichen Mengen von natürlichen Zahlen und x ↦ ⌈x⌉ eine Bijektion zwischen 𝔓_{ω}(ℕ) und ℕ, der Menge der natürlichen Zahlen. Zum Beispiel sei ⌈⌉ gegeben durch

⌈{n_{1}, … n_{k}}⌉ = ∑_{i} 2^{n_{i}}.

Die echten Klassen des Modells 𝔐 seien die unendlichen Teilmengen von ℕ und die Mengen von 𝔐 die Elemente von ℕ. Die Elementbeziehung E sei zwischen Mengen und echten Klassen die natürliche und zwischen Mengen und Mengen definiert durch

xE⌈{n_{1}, … n_{k}}⌉ ⟺ x ∈ {n_{1}, … n_{k}}.

Dann ist 𝔐 ein Modell aller bisherigen Axiome mit möglicher Ausnahme des Fundierungsaxioms. Das Fundierungsaxiom gilt, wenn n_{i} < ⌈{n_{1}, … n_{k}}⌉.

Wir werden später sehen, daß man aus jedem Modell von BG ohne Fundierung ein Modell von BG machen kann, indem man sich auf die fundierten Mengen beschränkt (siehe Übung 5.3). Die Beschränkung auf fundierte Mengen bedeutet keine wesentliche Einschränkung, weil man (ohne das Fundierungsaxiom) zeigen kann (siehe 2.5), daß jede Menge in Bijektion mit einer fundierten Menge steht.

Eine Klasse, die die leere Menge enthält und unter der Nachfolgeroperation

x ↦ x ∪ {x}

abgeschlossen ist, muß alle natürlichen Zahlen ⌜n⌝ (n = 0, 1, …) enthalten. Das Unendlichkeitsaxiom soll ausdrücken, daß die (noch zu definierende) Klasse der natürlichen Zahlen eine Menge ist:

Axiom (Unendlichkeitsaxiom) Es gibt eine Menge, die die leere Menge enthält und unter der Nachfolgeroperation abgeschlossen ist.

Sei A eine Klasse von nicht-leeren Mengen. Eine Auswahlfunktion von A ist ein Funktional F : A ⟶ V, mit

F (x) ∈ x

für alle x ∈ A.

Axiom (Auswahlaxiom) Jede Menge von nicht-leeren Mengen hat eine Auswahlfunktion.

Auf das Auswahlaxiom beziehen wir uns häufig mit AC, “Axiom of choice”. Wenn die übrigen Axiome von BG widerspruchsfrei sind, kann man das Auswahlaxiom weder widerlegen noch beweisen: Das Auswahlaxiom ist unabhängig von den übrigen Axiomen.

Das System BG hat durch Verwendung von Klassen den Vorteil formaler Einfachheit. Der Modellbegriff ist allerdings etwas kompliziert, weil man immer zwischen Klassen und Mengen unterscheiden muß. Das (äquivalente) System ZFC — Zermelo–Fränkel mit Auswahlaxiom — spricht nur von Mengen. Das Komprehensionsaxiom fällt weg, dafür werden die in den übrigen Axiomen vorkommenden Klassen durch Formeln ersetzt. Auf diese Weise werden das Aussonderungsaxiom, das Ersetzungsaxiom und das Fundierungsaxiom zu Axiomenschemata.

Die Axiome von ZFC: Die ϕ = ϕ(x_{0}, …, x_{n}) laufen über beliebige Formeln (in denen keine Klassenvariablen vorkommen.)

Axiom (Extensionalität)

∀x∀y((∀z z ϵ x ↔ z ϵ y) ⟶ x =^{.} y)

Axiom (Aussonderung)

∀x_{1}, …, x_{n}∀x∃y(∀x_{0} x_{0} ϵ y ⟷ (x_{0} ϵ x ∧ ϕ))

Axiom (Leere Menge)

∃x∀y ¬y ϵ x

Axiom (Paarmenge)

∀x_{1}, x_{2}∃x∀y (y ϵ x ⟷ (y =^{.} x_{1} ∨ y =^{.} x_{2}))

Axiom (Vereinigungsmenge)

∀x∃y∀z (z ϵ y ⟷ ∃w (z ϵ w ∧ w ϵ x))

Axiom (Potenzmenge)

∀x∃y∀z (z ϵ y ⟷ ∀w (w ϵ z → w ϵ x))

Axiom (Ersetzungsaxiom)

∀x_{2} … x_{n}∀x((∀x_{1}∃!x_{0} ϕ) ⟶ ∃y∀x_{0}(x_{0} ϵ y ↔ ∃x_{1}(x_{1} ϵ x ∧ ϕ)))

Axiom (Fundierungsaxiom)

∀x_{1} … x_{n}(∃x_{0} ϕ ⟶ ∃x_{0}(ϕ ∧ ∀y(y ϵ x_{0} → ¬ϕ(y, x_{1} …, x_{n}))))

Axiom (Unendlichkeitsaxiom)

∃x(∃y(y ϵ x ∧ ∀z¬z ϵ y) ∧ ∀y(y ϵ x → ∃z(z ϵ x ∧ ∀w(w ϵ z ↔ (w ϵ y ∨ w =^{.} y)))))

Das Auswahlaxiom formulieren wir etwas anders (aber äquivalent) als in BG, weil sonst die Formel zu unhandlich würde. Es sagt hier, daß eine Menge x von nicht–leeren, paarweise disjunkten Mengen eine Transversale besitzt: eine Menge, die mit jedem Element von x genau ein Element gemeinsam hat.

Axiom (Auswahlaxiom)

∀x((∀y(y ϵ x → ∃z z ϵ y))∧(∀y∀z(y ϵ x∧z ϵ x → ¬∃w(w ϵ y∧w ϵ z))) ⟶ ∃y∀z(z ϵ x → ∃!w(w ϵ z∧w ϵ y)))

C steht für choice, das Auswahlaxiom. ZF bezeichnet das Axiomensystem ohne das Auswahlaxiom. Fränkel hat dem Zermeloschen Axiomensystem das Ersetzungsaxiom hinzugefügt. Z ist unser Axiomensystem ohne Auswahlaxiom und Ersetzungsaxiom.

Satz 1.9 BG ist eine konservative Erweiterung von ZFC.

Was wir meinen ist: in BG und ZFC sind die gleichen nur mit Mengenvariablen formulierbaren Aussagen beweisbar.

Daß man alle Axiome von ZFC in BG beweisen kann, ist klar. Wenn eine Mengen–Aussage ϕ nicht aus ZFC folgt, gibt es ein Modell 𝔐 = (M, E), in dem ϕ falsch ist. Sei K das System aller in 𝔐 definierbaren Teilmengen von M, die nicht die Ausdehnung eines Elementes a von M sind (d.h. von der Form {m ∈ M | mEa}). Dann ist (M ∪ K, E∪ ∈↾ (M × K)) ein Modell von BG, in dem die Mengen die Elemente von M sind. Einzig der Nachweis des Komprehensionsaxioms verlangt eine kleine Überlegung: Wenn man in der zu komprehendierenden Formel die Klassenparameter durch ihre definierenden Formeln ersetzt, erhält man einen äquivalenten Ausdruck, der keine Klassen mehr enthält und also ein Element von M oder von K definiert. Jetzt hat man ein Modell von BG, in dem ϕ falsch ist. □

Wir werden später sehen, daß man das Komprehensionsaxiomenschema von BG durch endlich viele Spezialfälle ersetzen kann, daß aber dagegen ZFC nicht endlich axiomatisierbar ist.

Die Axiomatisierung von ZFC stammt von E. Zermelo ([17]) – bis auf das Ersetzungsaxiom, das von Fränkel ([5]) hinzugefügt wurde. Man verwendet darum die Bezeichnung Z für ZFC ohne Ersetzungsaxiom und Auswahlaxiom und ZC für Z mit Auswahlaxiom.

2 Wohlordnungen

Eine Wohlordnung ist ein Paar ū =< u, r >, wobei r eine lineare Ordnung auf u ist, die fundiert ist. Das heißt, daß jede nicht–leere Teilmenge von u ein (bzgl. r) minimales Element hat. Eine wohlgeordnete Klasse ist gegeben durch eine Klasse U und eine fundierte lineare Ordnung R auf U, die vorgängerklein ist. Das heißt, daß für alle a ∈ U die Klasse U_{(a)} = {b ∈ U | bRa} der Vorgänger von a eine Menge ist.

Eine nichtleere wohlgeordnete Klasse U hat ein kleinstes Element. Wenn a ∈ U nicht größtes Element von U ist, gibt es ein kleinstes Element, das größer ist als a, den Nachfolger von a. Ein Element von U, das nicht kleinstes Element von U und kein Nachfolger ist, ist Limeselement.

Wenn die Teilmenge v nicht kofinal in U ist, gibt es in U eine kleinste echte obere Schranke b von v. b heißt echtes Supremum sup^{∗} v von v. Es gilt immer a = sup^{∗} U_{(a)}. Dabei heißt V kofinal in U, wenn es für alle a ∈ U ein b ∈ V gibt, das größer–gleich a ist.

Ein Anfangsstück einer Wohlordnung ist eine Teilklasse, die mit jedem Element auch jedes kleinere enthält. Wie jede Teilklasse einer Wohlordnung sind auch Anfangsstücke mit der induzierten Ordnung wieder Wohlordnungen. Wenn das Anfangsstück V von U kofinal ist, ist V = U. Sonst ist V ein Anfangsstück der Form U_{(a)}.

Übung 2.1

1. Die leere Menge (mit der leeren Ordnung) ist eine Wohlordnung.

2. Jede Wohlordnung ū läßt sich um ein Element verlängern: Wähle ein Element a, das nicht zu u gehört (z.B. u). v̄ =< v, s >, wobei v = u ∪ {a} und s = r ∪ (u × {a}), ist dann wieder eine Wohlordnung. u ist ein Anfangsstück von v.

3. Sei (ū_{i} | i ∈ I), ū_{i} =< u_{i}, r_{i} >, eine Familie von Wohlordnungen, die Anfangsstücke voneinander sind, d.h. daß für alle i, j aus I ū_{i} ein Anfangsstück von ū_{j} oder ū_{j} ein Anfangsstück von ū_{i} ist. Dann ist die Vereinigung der u_{i} mit der Vereinigung der r_{i} eine wohlgeordnete Klasse. Die ū_{i} sind Anfangsstücke dieser Wohlordnung.

Definition Auf den Klassen U und V seien die Relationen R und S gegeben. Ein Isomorphismus zwischen U und V ist eine Bijektion F : U ⟶ V, die R in S überführt. Das heißt, daß

R(a, b) ⇔ S(F (a), F (b))

für alle a, b ∈ U. Wenn ein Isomorphismus existiert, heißen U und V isomorph. Für Wohlordnungen schreiben wir ū ≅ v̄.

Lemma 2.1 U und V seien zwei wohlgeordnete Klassen und F und G zwei Isomorphismen von U mit Anfangsstücken von V. Dann ist F = G.

Beweis:

Weil F [U] ein Anfangsstück von V ist, ist F [U_{(a)})] = V_{(F (a))} für alle a ∈ U. Daraus folgt die Rekursionsgleichung

F (a) = sup^{∗}F [U_{(a)})],

die angibt, wie sich der Funktionswert F (a) aus den Werten F (b) für b ∈ U_{(a)} bestimmt. Weil G die gleiche Rekursionsgleichung erfüllt, müssen G und F auf der Wohlordnung U übereinstimmen. En detail: Sei a ein Element mit F (a) ≠ G(a). Aus der Rekursionsgleichung für F und G folgt dann F [U_{(a)}] ≠ G[U_{(a)}]. Es gibt also ein b mit bRa und F (b) ≠ G(b). Die Klasse der Elemente a, auf denen F und G nicht übereinstimmen hat kein kleinstes Element und ist darum leer. □

Definition Eine Wohlordnung ū heißt kürzer als die Wohlordnung v̄, wenn ū zu einem echten Anfangsstück von v̄ isomorph ist. Wir schreiben ū ≺ v̄. Die Definition erweitert sich sinngemäß auf wohlgeordnete Klassen.

Es ist klar, daß ≺ transitiv ist. Aus dem Lemma folgt die Irreflexivität:

Folgerung 2.2 Keine Wohlordnung ist kürzer als sie selbst.

Beweis:

id_{u} ist ein Isomorphismus von ū auf ein Anfangsstück. □

Satz 2.3 Je zwei wohlgeordnete Klassen U und V sind vergleichbar: Es ist entweder U kürzer als V oder V ist kürzer als U oder beide Wohlordnungen sind isomorph.

Beweis:

Sei U durch R und V durch S wohlgeordnet. Setze F = {< a, b >∈ U × V | U_{(a)} ≅ V_{(b)}}^{1}. Wegen 2.1 ist durch aF b ay eindeutig durch b und b eindeutig durch a bestimmt. F ist also eine Bijektion zwischen U_{0} = D(F) und V_{0} = Wb(F). Wenn f ein Isomorphismus zwischen U_{(a)} und V_{(b)} ist und a′Ra, dann ist f ↾ U_{(a′)} ein Isomorphismus zwischen U_{(a′)} und V_{(f(a′))}. Es ist also a′F b′ für ein b′Sb. Daraus folgt, daß U_{0} und V_{0} Anfangsstücke sind und F ein Isomorphismus zwischen U_{0} und V_{0}. Wir sind fertig, wenn wir zeigen können, daß U_{0} = U oder V_{0} = V. Sonst gäbe es aber a ∈ U und b ∈ V mit U_{0} = U_{(a)} und V_{0} = V_{(b)}. Das hieße aber, daß aF b und a ∈ U_{0}, was nicht geht. □

Folgerung 2.4 Es gibt bis auf Isomorphie höchstens eine wohlgeordnete Klasse. Alle Wohlordnungen sind kürzer als eine solche Klasse.

Beweis:

Alle echten Anfangsstücke einer wohlgeordneten Klasse sind Mengen. □

Aus dem Auswahlaxiom folgt:

Satz 2.5 (Wohlordnungssatz) Jede Menge läßt sich wohlordnen.

Dieser Satz, von Cantor noch für evident gehalten, wurde von Zermelo ([16]) bewiesen.

Beweis:

Sei a eine Menge. Wähle mit Hilfe des Auswahlaxioms eine Funktion f : 𝔓(a) \ {a} → V mit f(x) ∈ a \ x. Wir nennen eine Wohlordnung < u, r > gut, wenn u ⊂ a und

(∗) x = f(u_{(x)}) für alle x ∈ u.

Hilfssatz Wenn ū und v̄ gut sind, ist ū ein Anfangsstück von v̄ (mit der induzierten Ordnung) oder umgekehrt.

Beweis: Sei zum Beispiel g : u ⟶ v ein Isomorphismus auf ein Anfangsstück. Dann erfüllt g die Rekursionsgleichung g(a) = sup^{∗} g[u_{(a)}] = f(g[u_{(a)}]). Die Identität auf u erfüllt dieselbe Gleichung. Also ist f = id_{u}.

1U_{(a)} ist eine Menge. Darum läßt sich U_{(a)} ≅ V_{(b)} mit einer Formel ausdrücken, in der nur Mengenquantoren vorkommen.

Nach der Übung 2.1.3 ist die Vereinigung ū aller guten Wohlordnungen wieder eine gute Wohlordnung. Wäre u eine echte Teilmenge von a, könnte man ū wie in der Übung 2.1.2 um das neue Element f(u) zu einer guten Wohlordnung v̄ verlängern. v müßte dann aber Teilmenge von u sein, was nicht geht. Also ist u = a. □

Umgekehrt folgt das Auswahlaxiom aus dem Wohlordnungssatz: Sei a eine Menge von nicht–leeren Mengen. Wähle eine Wohlordnung < von ⋃ a. Dann ist f(x) = min(x) eine Auswahlfunktion von a. Eine anderes zum Auswahlaxiom äquivalentes Prinzip ist Zorns Lemma ([18]).

Satz 2.6 (Zorns Lemma) Sei (a, <) eine partielle Ordnung. Wenn jede totalgeordnete Teilmenge von a eine obere Schranke hat, gibt es ein maximales Element.

Beweis:

Wenn a kein maximales Element hätte, hätte jede totalgeordnete Menge (eine “Kette”) u eine echte obere Schranke. Wir können annehmen, daß diese oberen Schranken durch eine Auswahlfunktion als f(u) gegeben sind. Wir nennen eine wohlgeordnete Kette u gut, wenn x = f(u_{(x)}) für alle x ∈ u. Wie im Beweis des Wohlordnungssatzes zeigt man, daß alle guten Ketten Anfangsstücke voneinander sind. Die Vereinigung aller guten Ketten ist wieder eine gute Kette u, die keine Erweiterung mehr zuläßt. u ∪ {f(u)} ist aber eine solche Erweiterung. Widerspruch. □

Das Auswahlaxiom folgt aus dem Zornschen Lemma auf folgende Weise: Sei a eine Menge von nicht–leeren Mengen. Die Menge p aller Auswahlfunktionen von Teilmengen von a wird durch ⊊ partiell geordnet. Die Vereinigung einer Kette von Auswahlfunktionen aus p ist wieder eine Auswahlfunktion. Ein maximales Element von p muß aber eine auf ganz a definierte Auswahlfunktion sein, weil man jede auf einer echten Teilmenge definierte Auswahlfunktion noch fortsetzen kann.

3 Ordinalzahlen

Cantor hat Ordinalzahlen als die Ordnungstypen von wohlgeordneten Mengen definiert. Eine Ordinalzahl hat also die Form

{ū | ū ≅ v̄}

für eine Wohlordnung v̄. Das Problem dieser Definition ist, daß Ordinalzahlen – bis auf den Ordnungstyp der leeren Menge – keine Mengen sind; man kann also keine Klassen von Ordinalzahlen bilden. Die unten angegebene Definition stammt von Zermelo und J.v.Neumann.

Satz 3.1 Es gibt eine wohlgeordnete echte Klasse (On, <).

Jede Wohlordnung ist dann nach 2.3 zu einem eindeutig bestimmten echten Anfangsstück On_{α} von On isomorph. Zum Beweis von 3.1 definieren wir daher On als die Klasse aller Ordinalzahlen im folgenden Sinn:

Definition Eine Ordinalzahl ist eine Menge α mit einer Wohlordnung <, so daß für alle β ∈ α

β = α_{(β)}.

Wir erinnern uns, daß α_{(β)} = {γ ∈ α | γ < β} (siehe Kapitel 2). Zum Beispiel sind 0,1,2,… Ordinalzahlen. Die Gleichung β = α_{(β)} ist gleichbedeutend mit der gleichzeitigen Gültigkeit von

β ∩ α = α_{(β)}

und

β ⊂ α.

Die erste Gleichung bedeutet, daß auf α die Ordnung < mit der ∈–Relation übereinstimmt. Die Inklusion sagt, daß α eine transitive Menge ist; das heißt, daß

x ∈ y ∈ α ⟹ x ∈ α.

Die Ordinalzahlen sind also die transitiven Mengen α, die durch ∈↾ α wohlgeordnet werden. Wir bemerken noch, daß offensichtlich die Elemente einer Ordinalzahl – also ihre echten Anfangsstücke – wieder Ordinalzahlen sind.

Wir ordnen On durch

β < α ⟺ β ≺ α .

Es ist nach Kapitel 2 klar, daß ≺ transitiv und irreflexiv ist. Wir müssen noch zeigen, daß < konnex ist, das heißt, daß α < β, α = β oder β < α für alle α, β ∈ On. Wegen 2.3 folgt das aus dem nächsten Lemma.

Lemma 3.2 Ordinalzahlen sind durch ihren Isomorphietyp eindeutig bestimmt.

Beweis:

Sei f : α → β der Isomorphismus. Dann gilt für alle x ∈ α

f(x) = β_{(f(x))} = f[α_{(x)}] = f[x].

Das ist eine Rekursionsgleichung für f, die auch von id_{α} erfüllt wird. Also ist f = id_{α}. □

Wir können sofort folgern, daß die Relation < auf On fundiert und vorgängerklein ist, denn die Ordinalzahlen, die kleiner sind als α entsprechen gerade den echten Anfangsstücken von α und sind also durch ≺ wie diese Anfangsstücke durch echte Inklusion wohlgeordnet. Weiter läßt sich aus dem Lemma folgern:

Folgerung 3.3 Für Ordinalzahlen α und β gilt

α < β ⟺ α ∈ β

und

α ≤ β ⟺ α ⊂ β.

Beweis:

α < β bedeutet, daß α zu einem echten Anfangsstück β_{(x)} = x von β isomorph ist, daß also α = x. Die zweite Behauptung folgt sofort aus der ersten. □

Wäre On eine Menge, so wäre On eine Ordinalzahl, also Element von sich selbst, was wegen des Fundierungsaxioms nicht geht. Man braucht aber hier das Fundierungsaxiom nicht: On ≺ On geht nicht nach (der Klassenversion von ) 2.2. Damit ist Satz 3.1 bewiesen. □

Folgerung 3.4 Jede Wohlordnung ist zu (genau) einer Ordinalzahl, ihrem Ordnungstyp, isomorph.

Beweis:

Sei ū eine Wohlordnung. Nach 2.3 ist ū mit On vergleichbar. Weil On keine Menge ist, ist ū zu einem echten Anfangsstück von On, also zu einer Ordinalzahl isomorph. □

Den Ordnungstyp einer Wohlordnung ū bezeichnen wir mit otp(ū). Für Mengen a von Ordinalzahlen schreiben wir einfach otp(a) für den Ordnungstyp von a mit seiner natürlichen Ordnung.

Sei A eine Teilklasse von On. Wenn A eine echte Klasse ist, gibt es einen eindeutig bestimmten Isomorphismus F zwischen On und A. Wenn A eine Menge ist, finden wir einen eindeutig (siehe 2.1) bestimmten Isomorphismus F zwischen einer Ordinalzahl, nämlich dem Ordnungstyp von A, und A. Wir nennen F die Aufzählungsfunktion von A. Es ergibt sich so eine ein-eindeutige Beziehung zwischen auf Ordinalzahlen oder auf On definierten streng monotonen Funktionen nach On und Teilklassen von On.

Satz 3.5 Sei α eine Menge. Dann sind äquivalent:

1. α ist Ordinalzahl.

2. α ist transitiv und ∈ konnex auf α.

3. α ist erblich transitiv, das heißt α und alle seine Elemente sind transitiv.

Beweis:

Daß Ordinalzahlen transitiv und konnex sind, wissen wir schon. Ordinalzahlen sind erblich transitiv, weil ihre Elemente wieder Ordinalzahlen sind. 2 ⇒ 1 : Das Fundierungsaxiom hat zur Folge, daß ∈ irreflexiv und fundiert auf α ist. Es bleibt zu zeigen, daß ∈↾ α transitiv ist. Seien also x, y und z Elemente von α und x ∈ y ∈ z. Das Fundierungsaxiom schließt x = z und z ∈ x aus, also bleibt nur noch x ∈ z übrig. 3 ⇒ 1 : Wir zeigen durch ∈–Induktion, daß alle erblich transitiven x Ordinalzahlen sind. Sei also x erblich transitiv. Sei y ein Element von x. Dann ist y transitiv. Weil y eine Teilmenge von x ist, sind auch die Elemente von y transitiv. Die Induktionsvoraussetzung ergibt, daß y eine Ordinalzahl ist. x ist also eine Menge von Ordinalzahlen und daher konnex. 2 ⇒ 1 ergibt, daß x Ordinalzahl ist. □

Lemma 3.6 1. Wenn α eine Ordinalzahl ist, ist α ∪ {α} der Nachfolger α + 1 von α, das heißt, die kleinste

Ordinalzahl, die größer ist als α.

2. Wenn (α_{i})_{i∈I} eine Familie von Ordinalzahlen ist, so ist ⋃_{i∈I} α_{i} das Supremum der α_{i}, das heißt, die kleinste Ordinalzahl, die größer-gleich allen α_{i} ist.

Beweis:

1: α ∪ {α} ist offensichtlich erblich transitiv, also eine Ordinalzahl. Zwischen α und α ∪ {α} gibt es keine echte Teilmenge mehr, also auch keine Ordinalzahl. 2: Die Vereinigung ist erblich transitiv –also eine Ordinalzahl– und die kleinste gemeinsame Obermenge aller α_{i}. Damit folgt die Behauptung aus 3.3. □

Wir haben im Beweis Gebrauch vom Fundierungsaxiom gemacht. In Wahrheit wird das Fundierungsaxiom nicht gebraucht.

Eine Limeszahl ist eine Ordinalzahl > 0, die keine Nachfolgerzahl ist. Die Klasse ω aller Ordinalzahlen, die kleiner sind als alle Limeszahlen, ist ein Anfangsstück von On. Wenn es keine Limeszahlen gibt (Wir zeigen gleich, daß das dem Unendlichkeitsaxiom widerspricht.), ist ω = On. Sonst ist ω eine Ordinalzahl, die kleinste Limeszahl.

Lemma 3.7 ω ∈ V

Beweis:

Das Lemma folgt aus dem Unendlichkeitsaxiom: Sei a eine Menge mit der im Unendlichkeitsaxiom geforderten Eigenschaft. Wir müssen zeigen, daß es mindestens eine Limeszahl gibt. Sei α die kleinste Ordinalzahl, die größer ist als alle Ordinalzahlen, die in a enthalten sind. Dann ist α eine Limeszahl. Denn wenn γ < α, ist γ ≤ β für eine Ordinalzahl β aus a. Dann ist auch β + 1 aus a und wir haben γ + 1 ≤ β + 1 < α. α ist nicht Null, weil 0 ∈ a. □

Umgekehrt impliziert das Lemma das Unendlichkeitsaxiom. Denn ω hat die Eigenschaft der Menge a, deren Existenz im Unendlichkeitsaxiom gefordert wird :

0 ∈ ω und x ∈ ω ⟹ x ∪ {x} ∈ ω.

4 Ordinalzahlarithmetik

Die arithmetischen Operationen auf On werden rekursiv definiert. Die Möglichkeit dafür liefert der folgende Satz.

Satz 4.1 (Rekursionssatz) Sei G : V ⟶ V ein Funktional. Dann gibt es ein eindeutig bestimmtes Funktional F : On ⟶ V, das für alle α ∈ On die Rekursionsgleichung F (α) = G(F ↾ α) erfüllt.

Beweis:

Eindeutigkeit: Sei F′ ein zweites Funktional, das die Rekursionsgleichung erfüllt. Wir zeigen, daß F (α) = F′(α) durch Induktion über α: Wenn die Behauptung schon für alle β < α gilt, ist F ↾ α = F′ ↾ α, also ist F (α) = G(F ↾ α) = G(F′ ↾ α) = F′(α). Existenz: Wir zeigen durch Induktion, daß es für alle α ein f : α + 1 ⟶ V gibt, das für alle β < α + 1 die Rekursionsgleichung erfüllt. Nehmen wir also an, daß es für alle α′ < α ein solches f : α′ +1 ⟶ V gibt. Weil ein solches f = f_{α′} jeweils eindeutig bestimmt ist, sind die f_{α′} Anfangsstücke voneinander. Die Vereinigung der f_{α′} ist also ein f′ : α ⟶ V, das wieder die Rekursionsgleichung erfüllt. Die Funktion f = f′ ∪ {< α, G(f′) >} ist dann auf α + 1 definiert und erfüllt die Rekursionsgleichung für alle β < α + 1. Schließlich setzen wir

F = ⋃ {f | für ein α ist f eine auf α + 1 definierte Funktion, die die Rekursionsgleichung erfüllt}

□

Aus dem Rekursionssatz folgt sofort die Möglichkeit, rekursiv Funktionen f auf Ordinalzahlen α durch eine Gleichung f(β) = G(f ↾ β) zu definieren, wobei G ein Funktional _{⋃β<α}^{β}V ⟶ V ist.

Häufig wird eine Rekursionsgleichung in der folgenden Form angegeben:

f(0)  = a
f(α + 1) = g(α, f(α))
f(λ)  = ⋃_{β<λ} f(β), wenn λ Limeszahl.

Wir nennen die dritte Bedingung die Stetigkeit von F

Folgerung 4.2 Für jedes Funktional G : V × V ⟶ V gibt es ein eindeutig bestimmtes Funktional F : V×On ⟶ V, das die Rekursionsgleichung F (x, α) = G(x, F_{x} ↾ α) erfüllt, wobei F_{x}(β) = F (x, β).

Beweis:

Für jedes x und jedes α gibt es genau eine Funktion f : α + 1 ⟶ V, die die Rekursionsgleichung f(β) = G(x, f ↾ β) (β ≤ α) erfüllt. Wir setzen F (x, α) = f(α). □

Wir können jetzt die Addition, Multiplikation und Exponentiation für Ordinalzahlen definieren.

Definition

Addition  α + 0  = α
α + (β + 1) = (α + β) + 1
α + λ  = sup_{β<λ}(α + β)  λ Limeszahl
Multiplikation α · 0  = 0
α · (β + 1) = (α · β) + α
α · λ  = sup_{β<λ}(α · β)  λ Limeszahl
Exponentiation α^{0}  = 1
α^{(β+1)}  = (α^{β}) · α
α^{λ}  = sup_{β<λ}(α^{β})  λ Limeszahl

Es ist klar, daß hier die bekannten Rechenoperationen auf den natürlichen Zahlen fortgesetzt werden, daß also 2 + 3 = 5, 2 · 3 = 6 und 2^{3} = 8 usw. Übrigens ist α + 1 doppelt definiert, einmal als Nachfolger von α und dann als Ergebnis der Addition. Wenn wir die Nachfolgeroperation hier einmal mit S bezeichnen, ist aber α + 1 = α + S(0) = S(α + 0) = S(α).

Addition und Multiplikation sind nicht mehr kommutativ. Es ist zum Beispiel 1+ω = ω < ω+1 und 2·ω = ω < ω+ω = ω·2. Damit sind auch zwei andere Rechengesetze falsch: Es ist (1+1)·ω < 1·ω+1·ω und (ω · 2)^{2} = ω^{2} · 2 < ω^{2} · 4 = ω^{2} · 2^{2}. Sonst gelten die üblichen Rechenregeln.

Lemma 4.3

0. α · 1 = α; α^{1} = α; 0 + α = α; 0 · α = 0; 1 · α = α; 0^{α} = 0, (α > 0); 1^{α} = 1

\begin{aligned}1. & (α + β) + γ & = & α + (β + γ) \\ 2. & α · (β + γ) & = & α · β + α · γ \\ 3. & (α · β) · γ & = & α · (β · γ) \\ 4. & α^{β+γ} & = & α^{β} · α^{γ} \\ 5. & (α^{β})^{γ} & = & α^{β·γ} \end{aligned}

Beweis:

0. Das ist einfach zu beweisen. Für die letzten vier Gleichungen braucht man Induktion.

Wir beweisen 1. bis 5. durch Induktion nach γ. Für γ = 0 ist alles klar. Alle zehn Seiten der fünf Gleichungen sind stetig in γ. Es bleibt also nur noch der Nachfolgerfall zu zeigen.

1. (α + β) + (γ + 1) = ((α + β) + γ) + 1 = (α + (β + γ)) + 1 = α + ((β + γ) + 1) = α + (β + (γ + 1))

2. α · (β + (γ + 1)) = α · ((β + γ) + 1) = α · (β + γ) + α = α · β + α · γ + α = α · β + α · (γ + 1)

3. (α · β) · (γ + 1) = (α · β) · γ + α · β = α · (β · γ) + α · β = α · (β · γ + β) = α · (β · (γ + 1))

4. α^{β+(γ+1)} = α^{(β+γ)+1} = α^{β+γ} · α = α^{β} · α^{γ} · α = α^{β} · α^{γ+1}

5. (α^{β})^{γ+1} = (α^{β})^{γ} · α^{β} = α^{β·γ} · α^{β} = α^{β·γ+β} = α^{β·(γ+1)} □

Lemma 4.4

1. Sei f : α ⟶ On streng monoton. Dann ist β ≤ f(β) für alle β < α.

2. Addition, Multiplikation und Exponentiation sind schwach monoton im ersten Argument und streng monoton im zweiten mit den folgenden Ausnahmen: α · β ist nur streng monoton in β, wenn α > 0. α^{β} ist nur streng monoton in β, wenn α > 1 und wenn α = 0 auch nicht schwach monoton.

Beweis:

1. Induktion über β.

2. Eine stetige Funktion f ist streng monoton, wenn f(β) < f(β + 1) für alle β. Es ist aber α + β < α + (β + 1), also + streng monoton in β. Daraus folgt — wenn α > 0 — α · β < α · β + α = α · (β + 1): · ist streng monoton in β. Damit hat man für α > 1, daß α^{β} < α^{β} · α = α^{β+1} und α^{β} ist streng monoton in β. □

Das folgende Lemma klärt die Bedeutung der arithmetischen Operationen.

Lemma 4.5

1. Jede Ordinalzahl größer–gleich α läßt sich in eindeutiger Weise schreiben als α + β.

2. Wenn α > 0, läßt sich jede Ordinalzahl eindeutig in der Form α · β + γ mit γ < α schreiben.

3. Wenn α > 1, läßt sich jede positive Ordinalzahl eindeutig in der Form α^{β} · γ + δ schreiben, wobei 0 < γ < α und δ < α^{β}.

Beweis:

Wir geben uns ein μ vor.

1. Sei μ ≥ α. Weil α+(μ+1) > μ ist {β′ | α+β′ ≤ μ} beschränkt. Sei β das Supremum dieser Menge. Weil + stetig im zweiten Argument ist, ist α + β ≤ μ. Wäre α + β < μ, wäre α + (β + 1) ≤ μ. Die Eindeutigkeit folgt, weil + streng monoton im zweiten Argument ist.

2. Setze β = sup{β′ | α·β′ ≤ μ}. Das Supremum existiert, weil nach dem letzten Lemma α·(μ+1) > μ. Wegen der Stetigkeit von · ist α · β ≤ μ. Schreibe

μ = α · β + γ.

Aus dieser Gleichung folgt

α · (β + 1) = α · β + α > μ ⟺ γ < α.

Wenn β wie oben gewählt ist, ist also γ < α. Umgekehrt folgt, wenn γ < α, daß β das obige Supremum ist, und wir haben die Eindeutigkeit.

3. Weil α^{μ+1} > μ, existiert β = sup{β′ | α^{β′} ≤ μ}. Stetigkeitsgründe ergeben α^{β} ≤ μ. Wir wenden 2. an und erhalten

μ = α^{β} · γ + δ mit δ < α^{β}.

Hieraus folgt durch leichte Rechnung

α^{β+1} > μ ⟺ γ < α.

Wenn β das obige Supremum ist, ist also γ < α. Umgekehrt schließt man aus dieser Ungleichung, daß β wie eben konstruiert sein muß. β, γ und δ sind also eindeutig bestimmt. □

Folgerung 4.6 Sei α und β zwei Ordinalzahlen. Dann gilt

1. Sei < auf w = (α × {0}) ∪ (β × {1}), der disjunkten Vereinigung von α und β, definiert durch

< x, i > < < y, j >⇔ \{ \begin{matrix}x < y und i = j = 0 & oder \\ x < y und i = j = 1 & oder \\ i = 0 und j = 1. \end{matrix}

Dann ist α + β der Ordnungstyp von < w, < >.

2. Die lexikographische Ordnung < sei auf w = α × β definiert durch

< x, y > < < x′, y′ >⇔ \{ \begin{matrix}y < y′ & oder \\ x < x′ und y = y.′ \end{matrix}

Dann ist α · β der Ordnungstyp von < w, < >.

3. Sei α > 1. Betracht die Menge w aller Funktionen von β nach α, die für fast alle – das heißt für alle bis auf endlich viele – Argumente den Wert 0 annehmen. Die lexikographische Ordnung < auf w sei definiert durch: f < g genau dann, wenn es ein x < β gibt, sodaß f(x) < g(x) und f(y) = g(y) für alle y > x. Dann ist α^{β} der Ordnungstyp von < w, < >.

Beweis:

1. Ein Isomorphismus F : α + β ⟶ w ist gegeben durch

F (γ) = \{ \begin{matrix}< γ, 0 >, & wenn γ < α \\ < δ, 1 >, & wenn γ = α + δ \end{matrix}

2. Ein Isomorphismus F : α · β ⟶ w ist gegeben durch

F (γ) =< ϵ, δ > , wenn γ = α · δ + ϵ und ϵ < α.

3. Sei f ∈ w und β_{0} < … < β_{n−1} ∈ β die Elemente von β, für die f(β_{i}) = α_{i} > 0. Setze

G(f) = α^{β_{n−1}} · α_{n−1} + ⋯ + α^{β_{0}} · α_{0}.

G ist der gesuchte Isomorphismus. Die Surjektivität zeigt man durch Induktion: Sei γ < α^{β}. Wir können annehmen, daß γ positiv ist. Aus 4.5 folgt, daß γ = α^{δ} · ϵ + μ für δ < β, 0 < ϵ < α und μ < α^{δ}. Nach Induktionsvoraussetzung ist μ = α^{β_{n−1}} · α_{n−1} + ⋯ + α^{β_{0}} · α_{0}. Wir setzen β_{n} = δ > β_{n−1}, α_{n} = ϵ und erhalten γ = α^{β_{n}} · α_{n} + ⋯ + α^{β_{0}} · α_{0}. □

Der Beweis zeigt, daß man jede Ordinalzahl eindeutig in der Cantorschen Normalform schreiben kann:

ω^{β_{n−1}} · k_{n−1} + ⋯ + ω^{β_{0}} · k_{0},

wobei β_{0} < … < β_{n−1} und 0 < k_{i} < ω.

Übung 4.1 (Rekursionssatz für fundierte Klassen) Sei R eine fundierte Relation auf U. Das heißt

1. R ist vorgängerklein: Für alle a ∈ U ist U_{(a)} = {b ∈ U | bRa} eine Menge.

2. Jede nicht–leere Teilklasse A von U enthält ein R–minimales Element a. D.h. ein a mit A∩U_{(a)} = ∅.

Dann gibt es für jedes auf Vdefinierte Funktional G genau ein Funktional F : U ⟶ V mit F (a) = G(F ↾ U_{(a)}) für alle a ∈ U.^{2}

Übung 4.2 Sei R eine zweistellige Relation R auf der Klasse A. Man zeige: R ist genau dann fundiert, wenn es ein Funktional r : A ⟶ On mit

aRb ⟹ r(a) < r(b)

gibt. Wenn R fundiert ist, kann man r außerdem so wählen, daß r(b) = sup {r(a) + 1 | aRb}. r ist dadurch eindeutig bestimmt und heißt der Fundierungsrang. ∈ ist fundiert auf V. Der entsprechende Fundierungsrang von x heißt der Rang rang(x) von x.

2Zeige durch „Induktion“, daß es für alle a ∈ U eine eindeutig bestimmte Funktion f : u → V gibt mit folgenden Eigenschaften: 1. u is die kleinste Teilmenge von U, die a enthält und vorgängerabgeschlossen ist, 2. f erfüllt die Rekursionsgleichung.

5 Die natürlichen Zahlen und die v. Neumann Hierarchie

Sei ω die kleinste Limeszahl aus Kapitel 3. Die Elemente von ω heißen natürliche Zahlen.

Lemma 5.1 Eine Ordinalzahl ist eine natürliche Zahl genau dann, wenn sie durch ∈^{−1} wohlgeordnet wird.

Beweis:

Sei n ∈ On. Wenn n ∉ ω, ist ω eine Teilmenge von n ohne Maximum. Wenn umgekehrt n eine nichtleere Teilmenge a hat, die kein Maximum hat, ist sup a ≤ n eine Limeszahl, also n ∉ ω. □

Im nächsten Satz zeigen wir, daß das System der natürlichen Zahlen durch die sogenannten Peanoaxiome charakterisiert wird. Sei dazu s die Nachfolgerfunktion von ω. Wir betrachten die Struktur 𝔑 =< ω, 0, s >.

Satz 5.2 𝔑 ist durch folgende Eigenschaften bis auf Isomorphie eindeutig bestimmt:

1. s ist injektiv.

2. 0 ist nicht im Bild von s.

3. ω hat keine echte Teilmenge A, die 0 enthält und unter s abgeschlossen ist.

Beweis:

𝔑 hat offenbar die angegebenen Eigenschaften. Die dritte Eigenschaft folgt aus der Fundiertheit von ω: Das Komplement einer echten Teilmenge A hat ein Minimum a. Wenn a = 0 ist, enthält A nicht die 0. Sonst ist a eine Nachfolgerordinalzahl und A ist nicht unter s abgeschlossen. Sei umgekehrt 𝔐 =< M, O, S > eine Struktur mit den drei Eigenschaften. Wir wollen einen Isomorphismus f zwischen 𝔑 und 𝔐 angeben. Also eine Bijektion f : ω ⟶ M, die ein Homomorphismus ist, das heißt f(0) = O und f(s(n)) = S(f(n)) für alle n ∈ ω erfüllt. Einen (eindeutig bestimmten) Homomorphismus f von 𝔑 nach 𝔐 liefert der Rekursionssatz. Das Bild von f enthält O und ist unter S abgeschlossen, ist also nach 3. gleich M. Zu zeigen bleibt, daß f injektiv ist. Betrachte

A = {m ∈ ω | f(m) ≠ f(n) für alle n > m}.

Jedes n > 0 hat die Form s(n′). Dann ist wegen 2. f(0) ≠ S(f(n′)) = f(n). A enthält also 0. Sei weiter m ∈ A und s(m) < n. Dann schreibt sich n als s(n′) für ein n′ > m und wir haben f(m) ≠ f(n′). Aus 1. ergibt sich f(s(m)) ≠ f(n). Damit ist s(m) ∈ A gezeigt und es folgt A = ω: f ist injektiv. □

Man zeigt leicht, daß ω unter den drei Ordinalzahloperationen abgeschlossen ist.

Satz 5.3 Auf den natürlichen Zahlen sind die Ordinalzahloperationen und die Anordnung durch die folgenden Rekursionen eindeutig bestimmt:

x + 0 = x , x + s(y) = s(x + y)
x · 0 = 0 , x · s(y) = x · y + x
x^{0} = 1 , x^{s(y)} = x^{y} · x
x ≮ 0  , x < s(y) ⇔ x = y oder x < y
□

Übung 5.1

1. + und · sind kommutativ auf ω.

2. Für alle l, m, n ∈ ω ist (n · m)^{l} = n^{l} · m^{l}.

Eine unendliche Folge ist eine auf ω definierte Funktion a : ω ⟶ V, deren Elemente wir als a_{i} = a(i) schreiben. Endliche Folgen sind auf natürlichen Zahlen definiert. Wir können jetzt das Fundierungsaxiom so ausdrücken:

Satz 5.4 Es gibt keine unendlich absteigende ∈–Kette. Das heißt, keine unendliche Folge (a_{i} | i ∈ ω) mit a_{i+1} ∈ a_{i} für alle i.

Beweis:

Sonst würde die Menge {a_{i} | i ∈ ω} dem Fundierungsaxiom widersprechen. □

Wir werden gleich sehen, daß 5.4 zum Fundierungsaxiom äquivalent ist.

Definition Die transitive Hülle th(a) von a ist die kleinste transitive Menge, die a als Teilmenge enthält.

Die transitive Hülle existiert als Durchschnitt aller transitiven Mengen, wenn es überhaupt eine transitive Menge gibt, die a enthält. Das folgt aber aus dem Unendlichkeitsaxiom:

Lemma 5.5 Jede Menge a ist in einer transitiven Menge enthalten.

Beweis:

Definiere f : ω ⟶ V rekursiv durch f(0) = a und f(n + 1) = ⋃ f(n). Dann ist b = ⋃_{i∈ω} f(i) transitiv. Denn, wenn x ∈ y ∈ f(n), ist x ∈ f(n + 1). Man sieht leicht, daß b = th(a) □

Wir können nun zeigen, daß das Fundierungsaxiom aus 5.4 folgt. (Natürlich muß man sich überzeugen, daß im Beweis das Fundierungsaxiom nirgendwo benutzt wird.) Sei A eine nicht–leere Klasse ohne ∈–minimales Element und c ein Element von A. Dann hat auch a = A ∩ th(c) kein ∈–minimales Element. Das Auswahlaxiom liefert uns eine Funktion f : a ⟶ a mit f(x) ∈ x für alle x ∈ a. Definiere die unendliche Folge b rekursiv durch: b_{0} = ein beliebiges Element von a, b_{i+1} = f(b_{i}). b widerspricht 5.4.

Übung 5.2 Zeige, daß sich th : V ⟶ V rekursiv durch

th(x) = x ∪ ⋃_{y∈x} th(y)

definieren läßt. (Eine solche Definition ist natürlich nur sinnvoll, wenn das Fundierungsaxiom gilt.)

Übung 5.3 Das Fundierungsaxiom sei hier nicht vorausgesetzt. Man zeige

1. Für eine Menge a sind äquivalent

(a) Es gibt keine unendliche ∈–Kette, die bei a beginnt.

(b) th(a) ist fundiert. D.h. jede nicht–leere Teilmenge von th(a) hat ein ∈–minimales Element.

2. Die Klasse aller Mengen, deren transitive Hülle fundiert ist, ist ein Modell von ZFC inklusive Fundierung.

Das System aller Mengen, deren transitive Hülle fundiert ist, läßt sich mit der von Neumann Hierarchie ausschöpfen.

Definition (von Neumann Hierarchie)

V_{0}  = ∅
V_{α+1} = 𝔓(V_{α})
V_{λ}  = ⋃_{α<λ} V_{α}, λ Limeszahl

Lemma 5.6 1. Alle V_{α} sind transitiv.

2. α < β ⇒ V_{α} ⊂ V_{β} Beweis:

1. Durch Induktion: V_{0} ist transitiv. Wenn x transitiv ist, ist auch 𝔓(x) transitiv. Also ist mit V_{α} auch V_{α+1} transitiv. Eine Vereinigung von transitiven Mengen ist transitiv. Also ist für Limeszahlen λ V_{λ} transitiv, wenn für alle α < λ die V_{α} transitiv sind.

2. Aus 1. folgt, daß V_{α} ⊂ V_{α+1}. Daraus folgt die Behauptung leicht durch Induktion. □ Aus dem Fundierungsaxiom folgt nun:

Satz 5.7 V = ⋃_{α∈On} V_{α} Beweis: Wir zeigen durch ∈–Induktion, daß jedes x in einem V_{α} liegt: Angenommen alle Elemente von x liegen in einem der V_{α}. Für jedes y ∈ x sei α(y) minimal mit y ∈ V_{α(y)}. Wenn β = sup_{y∈x} α(y), liegen alle Elemente von x in V_{β}. (Das folgt aus dem letzten Lemma.) Dann ist x ∈ V_{β+1}. □ Übung 5.4 Der Rang von x ist das kleinste α mit x ∈ V_{α+1}. Übung 5.5 Hier setzen wir das Fundierungsaxiom nicht voraus.

1. Die Elemente von ⋃_{α∈On} V_{α} sind genau die Mengen, deren transitive Hülle fundiert ist.

2. Satz 5.7 impliziert das Fundierungsaxiom.

6 Kardinalzahlen

Definition Zwei Mengen x und y heißen gleichmächtig, wenn es eine Bijektion zwischen x und y gibt. In Zeichen x ∼ y.

Man zeigt leicht, daß ∼ eine Äquivalenzrelation ist.

Nach dem Wohlordnungssatz ist jede Menge zu einer Ordinalzahl gleichmächtig. Wir nennen die kleinste Ordinalzahl, die zu x gleichmächtig ist, die Mächtigkeit oder auch die Kardinalität |x| von x. Die Ordinalzahlen, die Mächtigkeiten sind, heißen Kardinalzahlen.

Lemma 6.1 Es ist immer |α| ≤ α. Gleichheit gilt genau dann, wenn α Kardinalzahl ist.

Beweis: klar

Lemma 6.2

1. x ∼ y genau dann, wenn |x| = |y|.

2. Es sind äquivalent

(a) |x| ≤ |y|

(b) Es gibt eine injektive Abbildung f : x ⟶ y.

(c) x ist leer oder es gibt eine surjektive Abbildung. f : y ⟶ x.

Beweis:

1. ist klar

2. (a)⇒(b) Seien f : x ⟶ |x| und g : y ⟶ |y| Bijektionen. Wenn |x| ≤ |y|, ist |x| eine Teilmenge von |y|. Dann ist i = g^{−1} ∘ f eine injektive Abbildung von x nach y.

(b)⇒(a) Sei i : x ⟶ y injektiv und g wie eben. Dann ist g ∘ i eine Bijektion zwischen x und einer Teilmenge a von |y|. Sei h : α ⟶ a die Aufzählungsfunktion von a. Nach Lemma 4.4 ist β ≤ h(β) < |y| für alle β < α. Es folgt |x| ≤ α ≤ |y|.

(b)⇒ (c) Sei i : x ⟶ y injektiv. Wenn x nichtleer ist, wähle ein a ∈ x. Definiere s : y ⟶ x durch

s(z) = \{ \begin{matrix}i^{−1}(z) & wenn z ∈ i[x] \\ a & sonst \end{matrix}

(c)⇒(b) Wenn x leer ist, ist ∅ eine injektive Abbildung von x nach y. Wenn s : y ⟶ x eine Surjektion ist, wählen wir mit Hilfe des Auswahlaxioms für jedes z ∈ x ein i(z) aus {i ∈ y | s(i) = z}. i : x ⟶ y ist injektiv. □

Folgerung 6.3 (Satz von Bernstein) Wenn es eine Injektion f : x ⟶ y und eine Injektion g : y ⟶ x gibt, gibt es eine Bijektion h zwischen x und y.

Verfolgt man den Beweis der Folgerung zurück, sieht man, daß vom Auswahlaxiom Gebrauch gemacht wurde: Man braucht den Wohlordnungssatz. Man kann aber auch einen konstruktiven Beweis angeben. Sei a ∈ x. Dann unterscheiden wir zwei Fälle.

1. Wenn es ein n < ω und ein b ∈ y gibt mit

g ∘ \underbrace{(f ∘ g) ∘ (f ∘ g) ∘ ⋯ ∘ (f ∘ g)}_{n}(b) = a

und b ∉ f[x], setze h(a) = g^{−1}(a).

2. Sonst setze h(a) = f(a).

Wie man leicht sieht, ist h die gesuchte Bijektion.

Lemma 6.4 Alle natürlichen Zahlen und ω selbst sind Kardinalzahlen.

Beweis:

Wir zeigen durch Induktion über m ∈ ω, daß m ≁ n für alle natürlichen Zahlen n > m. Für m = 0 ist die Behauptung klar. Wenn 0 < m < n, schreiben wir m = m′ + 1 und n = n′ + 1. Dann ist m′ < n′. Wenn es eine Bijektion f : m ⟶ n geben würde, würde durch

g(z) = \{ \begin{matrix}f(m′), & wenn f(z) = n′ \\ f(z) & sonst \end{matrix}

eine Bijektion zwischen m′ und n′ definiert, was der Induktionsvoraussetzung widerspricht. Daß ω Kardinalzahl ist, folgt aus |n| < |n + 1| ≤ |ω| (n < ω). □

Eine Menge heißt endlich, wenn ihre Mächtigkeit eine natürliche Zahl ist und abzählbar, wenn ihre Mächtigkeit ω ist.

Definition Eine Klasse A von Ordinalzahlen heißt abgeschlossen in On, wenn das Supremum jeder nichtleeren Teilmenge von A wieder zu A gehört. Gleichbedeutend ist:

sup(A ∩ λ) = λ ⟹ λ ∈ A

für jede Limeszahl λ. Eine Teilmenge a einer Ordinalzahl α heißt abgeschlossen in α, wenn sup(a∩λ) = λ ⟹ λ ∈ a für alle Limeszahlen λ ∈ α.

Satz 6.5 Die Klasse der Kardinalzahlen ist unbeschränkt und abgeschlossen in On.

Beweis:

Die Unbeschränktheit folgt aus dem Satz von Cantor:

Lemma 6.6 |𝔓(x)| > |x| für alle x.

Beweis:

Da 𝔓(x) nichtleer ist, müssen wir zeigen, daß keine Abbildung g : x ⟶ 𝔓(x) surjektiv ist: in der Tat ist

{z ∈ x | z ∉ g(z)} ∉ Wb(g).
□(Lemma)

Es bleibt zu zeigen, daß das Supremum λ einer Menge a von Kardinalzahlen wieder eine Kardinalzahl ist: Für alle β < λ gibt es ein κ ∈ a mit β < κ. Es ist also β < κ = |κ| ≤ |λ|. Also ist λ = |λ|. □

Die kleinste Kardinalzahl, die größer ist als κ nennt man den Nachfolger κ^{+} von κ. Kardinalzahlen ungleich 0, die keine Nachfolgerkardinalzahlen sind heißen Limeskardinalzahlen.

Eine Klasse von Ordinalzahlen ist gegeben durch ihre Aufzählungsfunktion. Es gilt Lemma 6.7 Eine unbeschränkte Klasse von Ordinalzahlen ist genau dann abgeschlossen, wenn ihre Aufzählungsfunktion stetig ist.

Stetige Aufzählungsfunktionen heißen Normalfunktionen.

Beweis:

Sei F die Aufzählungsfunktion von A. Die Abgeschlossenheit von A bedeutet, daß das Supremum eines nicht–leeren Anfangsstücks von A ohne größtes Element wieder zu A gehört. Solche Anfangsstücke sind aber gerade Mengen der Form F [μ] für eine Limeszahl μ. Das Supremum von F [μ] gehört genau dann zu A, wenn sup(F [μ]) = F (μ). □

Man zeigt leicht, daß das folgende gilt: Sei f : α → β schwach monoton, stetig und das Bild von f sei kofinal in β. Dann ist das Bild von f abgeschlossen in β.

Die Aufzählungsfunktion von Card, der Klasse der unendlichen Kardinalzahlen, nennen wir ℵ. Es ist ℵ_{0} = ω, ℵ_{1} ist die erste überabzählbare Kardinalzahl, ℵ_{α} die α–te unendliche Kardinalzahl. Man schreibt auch ω_{α} für ℵ_{α}. Es ist ℵ_{α}^{+}=ℵ_{α+1}. ℵ_{λ} ist genau dann Limeskardinalzahl, wenn λ = 0 oder Limesordinalzahl ist.

Wir bemerken hier, daß unendliche Kardinalzahlen Limesordinalzahlen sind: Unendliche Ordinalzahlen λ haben die Form ω+α. Es ist dann 1+λ = 1+ω+α = ω+α = λ und also |λ+1| = |1+λ| = |λ|.

Definition (Kardinalzahlarithmetik) κ und μ seien Kardinalzahlen. Wir definieren

1. κ +_{c} μ = |(κ × {0}) ∪ (μ × {1})|

2. κ ·_{c} μ = |κ × μ|

3. (κ^{μ})_{c} = |^{μ}κ|

Nach Lemma 6.6 ist κ^{+} ≤ 2^{κ}. Die Kontinuumshypothese CH besagt, daß ω^{+} = 2^{ω}. Die verallgemeinerte Kontinuumshypothese GCH (generalized continuum hypothesis) fordert κ^{+} = 2^{κ} für alle unendlichen κ.

Es ist klar, daß |(u × {0}) ∪ (v × {1})| = |u| +_{c} |v|, |u × v| = |u| ·_{c} |v| und |^{u}v| = (|v|^{|u|})_{c}. Die Ordinalzahloperationen sind natürlich nicht mit den Kardinalzahloperationen identisch. Man hat κ+_{c} μ = |κ + μ| und κ ·_{c} μ = |κ · μ|. Im allgemeinen ist aber (κ^{μ})_{c} größer als |κ^{μ}|.

Man zeigt leicht, daß in der Kardinalzahlarithmetik alle von den natürlichen Zahlen gewohnten Rechenregeln gelten. +_{c} und ·_{c} sind assoziativ und kommutativ; es gilt das Distributivgesetz. Für die Exponentiation gilt (κ^{μ+_{c}λ})_{c} = (κ^{λ})_{c} ·_{c} (κ^{μ})_{c}, (κ^{μ·_{c}λ})_{c} = (((κ^{λ})_{c}^{μ})_{c}, und (κ ·_{c} λ)^{μ} = (κ^{μ})_{c} ·_{c} (λ^{μ})_{c}. Das zeigt man leicht durch Angabe von Bijektionen. Zum Beispiel folgt die letzte Gleichung aus C (A × B) ∼ ^{C}A ×^{C}B. Die Bijektion ordnet hier jeder Funktion f : C ⟶ A × B das Paar < g, h > zu, wobei f(c) =< g(c), h(c) >.

Alle drei Kardinalzahloperationen sind schwach monoton in allen Argumenten, wie man leicht einsehen kann.

Für eine Familie (κ_{i})_{i∈I} definiert man die Summe ∑_{i∈I} κ_{i} und das Produkt ∏_{i∈I} κ_{i} als die Mächtigkeit von ⋃_{i∈I} (κ_{i} × {i}) bzw. von {f : I ⟶ ⋃_{i∈I} κ_{i} | f(i) ∈ κ_{i} für alle i} (diese Menge nennt man ebenfalls das Produkt der Mengen κ_{i}).

Lemma 6.8 Für natürliche Zahlen stimmen Ordinalzahloperationen und Kardinalzahloperationen überein.

Beweis:

Aus Lemma 4.6, Satz 5.3 und Lemma 6.4. □

Aus dem nächsten Satz folgt, daß Addition und Multiplikation für unendliche Kardinalzahlen trivial sind.

Satz 6.9 κ ·_{c} κ = κ für alle κ ∈ Card.

Beweis:

Der Beweis geht durch Induktion nach κ. Wir definieren eine Wohlordnung auf κ × κ:

< α, β > < < α′, β′ >⟺ \{ \begin{matrix}max\{α, β\} < max\{α′, β′\} & oder \\ max\{α, β\} = max\{α′, β′\} & und & β < β′ & oder \\ & & β = β′ & und & α < α.′ \end{matrix}

< wird vermöge der Einbettung < α, β >⟼< α, β, max{α, β} > von der lexikographischen Ordnung auf κ×κ×κ induziert, ist also eine Wohlordnung. Wir zeigen, daß alle echten Anfangsstücke von κ×κ eine kleinere Mächtigkeit als κ haben. Daraus folgt, daß alle Ordinalzahlen kleiner als der Ordnungstyp von κ × κ kleiner als κ sind. Weil andererseits die Mächtigkeit von κ × κ mindestens κ ist, folgt daß der Ordnungstyp gleich κ ist. Damit ist dann der Satz bewiesen.

Fixiere ein Paar p_{0} =< α_{0}, β_{0} >. Sei γ = max{α_{0}, β_{0}}+1. Dann liegen alle Paare, die kleiner als p_{0} sind in γ × γ. Das durch p_{0} bestimmte Anfangsstück hat also höchstens die Mächtigkeit κ_{0} = |γ| ·_{c} |γ|. Wenn γ endlich ist, ist auch κ_{0} endlich und kleiner als κ. Sonst wenden wir die Induktionsvoraussetzung an und erhalten κ_{0} = |γ| < κ. □

Folgerung 6.10 κ und μ seien Kardinalzahlen und κ unendlich. Dann ist

1. κ +_{c} μ = max{κ, μ}

2. κ ·_{c} μ = \{ \begin{matrix}0, & wenn μ = 0 \\ max\{κ, μ\} & sonst \end{matrix}

3. (2^{κ})_{c} = (κ^{κ})_{c}

Beweis:

Sei λ = max{κ, μ}.

1. λ ≤ κ +_{c} μ ≤ λ +_{c} λ = 2 ·_{c} λ ≤ λ ·_{c} λ = λ

2. Wenn μ > 0, ist λ ≤ κ ·_{c} μ ≤ λ ·_{c} λ = λ

3. (2^{κ})_{c} ≤ (κ^{κ})_{c} ≤ ((2^{κ})_{c}^{κ})_{c} = (2^{κ·_{c}κ})_{c} = (2^{κ})_{c} □

Folgerung 6.11 Wenn I unendlich ist und die κ_{i} größer als 0, ist

∑_{i∈I} κ_{i} = max{|I|, sup_{i∈I} κ_{i}}

Beweis:

Sei λ = ∑_{i∈I} κ_{i}. Weil κ_{i} ≤ λ für alle i, ist sup_{i∈I} κ_{i} ≤ λ. Weil die κ_{i} größer als 0 sind, ist |I| ≤ ∑_{i∈I} 1 ≤ λ. Andererseits ist λ ≤ ∑_{i∈I} (sup_{i∈I} κ_{i}) = |I| ·_{c} sup_{i∈I} κ_{i} = max{|I|, sup_{i∈I} κ_{i}}. □

Übung 6.1 |α^{β}| = max{|α|, |β|}, wenn α > 1, β > 0 und nicht beide Ordinalzahlen endlich sind.

7 Kardinalzahlexponentiation

Wir schreiben Exponentiation für Kardinalzahlen ab jetzt ohne den Index c. Außer in Übung 8.1 kommt Ordinalzahlexponentiation nicht mehr vor.

Definition Die Kofinalität cf (α) einer Ordinalzahl α ist die kleinste Mächtigkeit einer kofinalen Teilmenge von α.

Entsprechend läßt sich die Kofinalität beliebiger linearer Ordnungen definieren. Man beachte, daß cf (0) = 0 und cf (α + 1) = 1.

Lemma 7.1

1. cf (α) ≤ α

2. Wenn B kofinal in α ist, ist cf (α) = cf (B).

3. α hat eine abgeschlossene, kofinale Teilmenge vom Ordnungstyp cf (α).

4. cf (cf (α)) = cf (α)

Beweis:

1. ist trivial.

2. Wenn b kofinal in B ist, ist b auch kofinal in α. Also ist cf (α) ≤ cf (B). Wenn umgekehrt a kofinal in α ist, ist b = {min (B \ x) | x ∈ a} kofinal in B und |b| ≤ |a|. Also cf (B) ≤ cf (α).

3. Sei f : cf (α) ⟶ α eine Bijektion mit einer kofinalen Teilmenge. Definiere F : cf (α) ⟶ On durch F (x) = sup_{y<x} f(y). Weil kein x < cf (α) auf eine kofinale Teilmenge abgebildet werden kann, liegen die Werte von F in α. Das Bild a von F ist offensichtlich kofinal in α. Weil F schwach monoton ist, ist otp(a) ≤ cf (α). (g(x) = min{i < cf (α) | F (i) = x} definiert einen Isomorphismus zwischen a und einer Teilmenge von cf (α).) Wegen der Stetigkeit von F ist a abgeschlossen.

4. Sei a kofinal in α vom Ordnungstyp cf (α). Dann ist cf (cf (α)) = cf (a). Nach 2. ist cf (a) = cf (α). □

Es ist leicht zu sehen, daß 1,2 und 4 nicht nur für Ordinalzahlen α gelten, sondern für beliebige lineare Ordnungen. Wenn man Abgeschlossenheit nicht fordert, gilt auch 3.

Definition Eine unendliche Kardinalzahl κ heißt regulär, wenn cf (κ) = κ.

Kofinalitäten sind reguläre Kardinalzahlen nach Lemma 7.1 4. Unendliche Nachfolgerkardinalzahlen κ^{+} sind regulär. Wenn nämlich sup_{i∈I}(α_{i}) = κ^{+}, ist

⋃_{i∈I} α_{i} = κ^{+}.

Also ist nach Folgerung 6.11 max {|I|, sup_{i∈I} |α_{i}|} ≥ κ^{+}. Weil |α_{i}| ≤ κ für alle i, ist |I| = κ^{+}. Die kleinste reguläre Limeskardinalzahl ist ω. Für überabzählbare Limeszahlen λ ist cf (ℵ_{λ}) = cf (λ). Die Existenz überabzählbarer regulärer Limeskardinalzahlen, sogenannter schwach unerreichbarer Kardinalzahlen, läßt sich nicht beweisen (vgl.14.8, 15.9 und 15.10). Für eine schwach unerreichbare Kardinalzahl ℵ_{λ} ist ℵ_{λ} = cf (λ) ≤ λ ≤ ℵ_{λ}, also ℵ_{λ} = λ. Die Existenz solcher Kardinalzahlen κ ist leicht zu zeigen. Definiere κ_{0} = ω, κ_{i+1} = ℵ_{κ_{i}} und setze κ = sup_{i∈ω} κ_{i}. κ hat aber die Kofinalität ω und ist nicht regulär.

Definition Für unendliche κ definiere

1. κ ⌣^{μ} = sup_{λ<κ} λ^{μ}

2. μ ⌣^{κ} = sup_{λ<κ} μ^{λ}

Für unendliche Nachfolgerkardinalzahlen hat man {κ^{+} \atop ⌣} ^{μ} = κ^{μ}.

Wir wollen versuchen κ^{μ} zu berechnen. Wenn μ endlich ist, und κ unendlich, ist κ^{μ} = κ. Wir nehmen also im folgenden an, daß μ unendlich ist. Für kleine κ hat man 0^{μ} = 0, 1^{μ} = 1, und für alle κ zwischen 2 und μ ist κ^{μ} = 2^{μ}. Denn 2^{μ} ≤ κ^{μ} ≤ μ^{μ} = 2^{μ}.

Satz 7.2 Sei μ unendlich. Dann ist

1. κ^{μ} = (κ ⌣^{μ} )^{cf (μ)}

2. Für unendliches κ und μ < cf (κ) ist κ^{μ} = max {κ, κ ⌣^{μ}} .

3. Für unendliches κ und cf (κ) ≤ μ ist κ^{μ} = ( κ ⌣^{μ})^{cf (κ)} .

Beweis:

1. Sei μ = sup_{i<cf (μ)} α_{i}. Setzt man μ_{i} = |α_{i}|, so ist μ ≥ ∑_{i<cf (μ)} μ_{i} = max {cf (μ), sup_{i<cf (μ)} μ_{i}}. Wenn μ regulär ist, ist cf (μ) = μ; wenn μ singulär ist, ist μ Limeskardinalzahl und wir haben sup_{i<cf (μ)} μ_{i} = μ. Es folgt μ = ∑_{i<cf (μ)} μ_{i}. Also ist

κ^{μ} = κ^{∑_{i<cf (μ)} μ_{i}} = ∏_{i<cf (μ)} κ^{μ_{i}} ≤ ∏_{i<cf (μ)} κ ⌣^{μ} = (κ ⌣^{μ} )^{cf (μ)}.

Andererseits ist (κ ⌣^{μ} )^{cf (μ)} ≤ κ^{μ·_{c}cf (μ)} = κ^{μ}.

Allgemein gilt

κ ⌣^{μ} ≤ κ^{μ} ≤ ( κ ⌣^{μ})^{cf (κ)} .

Um die zweite Ungleichung einzusehen, schreiben wir κ = ∑_{i<cf (κ)} κ_{i}. Wenn die κ_{i} größer als 1

sind – wie wir annehmen können –, ist ∑_{i<cf (κ)} κ_{i} ≤ ∏_{i<cf (κ)} κ_{i}. Also ist κ^{μ} ≤ (∏_{i<cf (κ)} κ_{i})^{μ} =

∏_{i<cf (κ)} κ_{i}^{μ} ≤ ∏_{i<cf (κ)} κ ⌣^{μ} = ( κ ⌣^{μ})^{cf (κ)} .

2. Wenn μ < cf (κ), ist jede Funktion von μ nach κ beschränkt, also ^{μ}κ = ⋃_{α<κ} ^{μ}α und daher

κ^{μ} ≤ ∑_{α<κ} |α|^{μ} = max {κ, sup_{α<κ} |α|^{μ}} = max {κ, κ ⌣^{μ}} .

3. Wenn cf (κ) ≤ μ, ist ( κ ⌣^{μ})^{cf (κ)} ≤ (κ^{μ})^{cf (κ)} ≤ κ^{μ·_{c}μ} = κ^{μ} □

Aus dem Satz folgt, daß sich Potenzen berechnen lassen, wenn man nur die Funktion

κ^{cf(κ)}

kennt. Wenn κ und μ (μ unendlich) gegeben sind, unterscheidet man zur Berechnung von κ^{μ} fünf (sich nicht notwendig ausschließende) Fälle:

1. Wenn cf(μ) < μ, führt κ^{μ} = (κ ⌣^{μ} )^{cf (μ)} die Berechnung auf kleinere Exponenten zurück.

2. Wenn 2 ≤ κ ≤ cf (μ) = μ, ist κ^{μ} = μ^{cf (μ)}.

3. Wenn κ unendlich ist und μ < cf (κ), ist man durch κ^{μ} = max {κ, κ ⌣^{μ}} auf kleinere Basen (bei gleichem Exponenten) zurückgeführt.

4. Wenn κ unendlich und cf (κ) < μ, braucht man zur Berechnung von κ^{μ} = ( κ ⌣^{μ})^{cf (κ)} Exponentiation mit kleineren Basen (bei gleichem Exponenten) und eine Potenz mit kleinerem Exponenten.

5. Wenn κ unendlich und μ = cf (κ), ist κ^{μ} = κ^{cf (κ)}.

Als Beispiel berechnen wir ℵ_{ω}^{ℵ_{ω}}. Es ist ℵ_{ω}^{ℵ_{ω}} = (ℵ_{ω} ⌣^{ℵ_{ω}} )^{ℵ_{0}} = (sup_{n<ω} ((ℵ_{ω})^{ℵ_{n}}))^{ℵ_{0}} . Weiter ist (ℵ_{ω})^{ℵ_{n}} = ( {ℵ_{ω} \atop ⌣} ^{ℵ_{n}})^{ℵ_{0}} = (sup_{m<ω} (ℵ_{m}^{ℵ_{n}}))^{ℵ_{0}} . Jetzt müssen wir noch ℵ_{m}^{ℵ_{n}} für genügend große m berechnen. Wir haben ℵ_{m}^{ℵ_{n}} = max \{ℵ_{m}, {ℵ_{m} \atop ⌣} ^{ℵ_{n}}\} = … = max \{ℵ_{m}, 2^{ℵ_{n}}\} . Zusammen ergibt das (ℵ_{ω})^{ℵ_{n}} = (max (ℵ_{ω}, 2^{ℵ_{n}}))^{ℵ_{0}} = max (ℵ_{ω}^{ℵ_{0}}, 2^{ℵ_{n}}) . Schließlich ist ℵ_{ω}^{ℵ_{ω}} = max (ℵ_{ω}^{ℵ_{0}}, (sup_{n<ω} (2^{ℵ_{n}}))^{ℵ_{0}}) . Wenn die Folge der 2^{ℵ_{n}} konstant = 2^{ℵ_{n_{0}}} wird, ist (sup_{n<ω} (2^{ℵ_{n}}))^{ℵ_{0}} = 2^{ℵ_{n_{0}}} . Sonst ist cf (sup_{n<ω} (2^{ℵ_{n}})) = ℵ_{0}.

Über die Funktion κ^{cf(κ)} weiß man nur: Satz 7.3 Für unendliche κ ist κ^{cf(κ)} > κ. Beweis: Sei κ = sup_{i<cf (κ)} α_{i} und f eine Funktion von κ nach ^{cf(κ)}κ. Für jedes i < cf (κ) ist

|{f(j)(i) | j < α_{i}}| ≤ |α_{i}| < κ.

Also gibt es ein β = g(i) aus κ, das von allen f(j)(i) (j < α_{i}) verschieden ist. Die Funktion g ist dann verschieden von allen f(j). f kann also nicht surjektiv sein. □ Folgerung 7.4 Wenn μ unendlich und κ ≥ 2, ist cf (κ^{μ}) > μ Beweis: Sonst ist (κ^{μ})^{cf (κ^{μ})} ≤ (κ^{μ})^{μ} = κ^{μ}. Das widerspricht 7.3 □

Für reguläre κ ist κ^{cf (κ)} = 2^{κ}. Sonst gilt nur κ^{+} ≤ κ^{cf (κ)} ≤ κ^{κ} = 2^{κ}. Die verallgemeinerte Kontinuumshypothese impliziert also κ^{cf (κ)} = κ^{+} für alle κ.

Umgekehrt folgt aus κ^{cf (κ)} = κ^{+} für alle κ wieder GCH. Das ist klar für reguläre κ. Singuläre κ sind Suprema von regulären Kardinalzahlen. Wir haben also 2 ⌣^{κ} = κ und daher 2^{κ} = (2 ⌣^{κ})^{cf (κ)} = κ^{cf (κ)}. Übung 7.1 Aus GCH folgt für unendliche κ

κ^{μ} = \{ \begin{matrix}κ, & wenn & 0 < μ < cf (κ) \\ κ^{+}, & wenn & cf (κ) ≤ μ ≤ κ \\ μ^{+}, & wenn & κ ≤ μ \end{matrix}

Übung 7.2 (Satz von König) Wenn κ_{i} < μ_{i} für alle i, ist ∑_{i∈I} κ_{i} < ∏_{i∈I} μ_{i}. (cf [9])

Nach einem Satz von Easton [2] kann man auf regulären Kardinalzahlen die Funktion 2^{κ} beliebig vorschreiben (in einem zu präzisierenden Sinn), solange sie nur schwach monoton bleibt und cf (2^{κ}) > κ. Für singuläre Kardinalzahlen gibt es allerdings Zusammenhänge zwischen den verschiedenen Werten. Im Kapitel 9 zeigen wir, daß für singuläres κ von überabzählbarer Kofinalität 2^{κ} = κ^{+} gilt, wenn GCH unterhalb von κ richtig ist. Ein anderes Beispiel ist der nächste Satz.

Satz 7.5 (Heckler) Sei κ singulär und für genügend große μ < κ sei 2^{μ} konstant gleich 2^{μ_{0}}. Dann ist auch 2^{κ} = 2^{μ_{0}}.

Beweis:

2^{κ} = (2 ⌣^{κ})^{cf (κ)} = (2^{μ_{0}})^{μ_{0}} = 2^{μ_{0}}. □

8 Clubs und stationäre Mengen

Im folgenden sei eine unendliche Kardinalzahl κ mit überabzählbarer Kofinalität festgehalten.

Definition Eine unbeschränkte und abgeschlossene Teilmenge C von κ heißt club (closed unbounded).

Ein club in On ist eine unbeschränkte und abgeschlossene Klasse von Ordinalzahlen.

Jeder nichtleere Endabschnitt von κ ist ein club. Wenn A unbeschränkt in κ ist, ist die Menge A′ = {α < κ | α = sup(α ∩ A)} der Häufungspunkte von A ein club. Um die Unbeschränktheit einzusehen, beginnen wir mit einem β < κ. Weil A unbeschränkt ist, finden wir über β eine Folge α_{0} < α_{1} < ⋯ < α_{n} < ⋯ von Elementen von A. Weil die Kofinalität von κ überabzählbar ist, liegt das Supremum der α_{i} in κ und gehört zu A′. Wenn κ eine Limeskardinalzahl ist, ist die Menge der Kardinalzahlen unterhalb von κ ein club (cf 6.5).

Lemma 8.1 Der Durchschnitt zweier clubs ist wieder ein club.

Beweis:

Daß der Durchschnitt von (beliebig vielen) abgeschlossenen Mengen wieder abgeschlossen ist, ist klar. Seien C und D clubs und γ aus κ. Wir wählen nun eine aufsteigende Folge γ < α_{0} < β_{0} < α_{1} < β_{1} < ⋯ von Elementen α_{i} ∈ C und β_{i} ∈ D. Dann liegt sup_{i<ω} α_{i} = sup_{i<ω} β_{i} in C ∩ D. Der Durchschnitt ist also auch unbeschränkt. □

Lemma 8.2 Der Durchschnitt von weniger als cf (κ)–vielen clubs ist wieder ein club.

Beweis:

Sei μ eine Kardinalzahl kleiner als cf (κ) und (C_{α})_{α<μ} eine Familie von clubs. Wir zeigen durch Induktion über μ, daß der Durchschnitt D der C_{α} unbeschränkt ist. Für endliche μ folgt das aus 8.1. Sei also μ unendlich und γ < κ. Nach Induktionsannahme sind alle D_{α} = ⋂_{β<α} C_{β} unbeschränkt. Definiere rekursiv ein f : μ ⟶ κ durch

f(α) = min {ϵ ∈ D_{α} | ϵ größer als γ und alle Elemente von f[α]} .

Diese Definition ist sinnvoll, weil f[α] nicht kofinal in κ sein kann. Weil μ Limeszahl ist, ist δ = sup_{α<μ} f(α) für jedes β < μ gleich sup_{β<α<μ} f(α), also Supremum von Elementen aus C_{β}. δ liegt also in allen C_{β} und ist größer als γ. □

Übung 8.1 Für eine Teilmenge A von κ definiere A^{(α)} durch Rekursion über α: A^{(0)} = A, A^{(α+1)} = (A^{(α)})′ und A^{(λ)} = ⋂_{α<λ} A^{(α)} für Limeszahlen λ. Nach 8.2 sind für jeden club C alle C^{(α)} für α < cf (κ) wieder clubs. Zeige, daß κ^{(α)} = {ω^{α}β | β < κ} für alle α < κ.^{3}

Sei (A_{α})_{α<κ} eine Familie von Teilmengen von κ. Der Diagonaldurchschnitt der A_{α} ist

Δ_{α<κ}A_{α} = {α < κ | α ∈ ⋂_{β<α} A_{β}} .

Satz 8.3 Wenn κ regulär (und überabzählbar) ist, ist der Diagonaldurchschnitt von clubs wieder ein club.

3In ω^{α} verwenden wir Ordinalzahlexponentation.

Sei D der Diagonaldurchschnitt der clubs C_{α}.

D ist abgeschlossen: Sei α = sup(D ∩ α) < κ eine Limeszahl. Fixiere ein β < α. Dann ist α Supremum von Ordinalzahlen aus D, die zwischen β und α liegen. Diese Ordinalzahlen liegen aber alle in C_{β}. Also liegt auch α in C_{β}. Es folgt α ∈ D.

D ist unbeschränkt: Wegen 8.2 können wir eine monoton wachsende Funktion f : ω → κ mit beliebig vorgegebenen f(0) konstruieren, sodaß f(n + 1) ∈ ⋂_{β<f(n)} C_{β} für alle n. Das Supremum der f(n) gehört zu D.

Übung 8.2 Für Teilmengen A, B von κ sei A ≡ B, wenn A ∩ C = B ∩ C für einen club C. ≡ ist eine Äquivalenzrelation auf 𝔓(κ). In den Relationen A ∩ B ≡ E, A ∪ B ≡ E und κ \ A ≡ B kann man A, B, E durch äquivalente Mengen ersetzen. 𝔓(κ)/ ≡ wird dadurch zu einer Booleschen Algebra. Der Diagonaldurchschnitt D einer Familie (A_{α}) ist bis auf ≡ charakterisiert durch

1. (D/ ≡) ⊂ (A_{α}/ ≡) für alle α

2. Aus (E/ ≡) ⊂ (A_{α}/ ≡) für alle α folgt (E/ ≡) ⊂ (D/ ≡).

Der Diagonaldurchschnitt hängt also bis auf ≡ nur von der Menge {A_{α}/ ≡| α < κ} ab, er ist das Infimum der A_{α}/ ≡ in der Booleschen Algebra 𝔓(κ)/ ≡.

Definition Eine Teilmenge S von κ, die jeden club schneidet, heißt stationär.

S ist also stationär, wenn (S/ ≡) in 𝔓(κ)/ ≡ nicht das Nullelement ist. Wegen 8.1 ist jeder club stationär. Wenn μ eine reguläre Kardinalzahl ist, kleiner als cf (κ), ist {α < κ | cf (α) = μ} stationär. Sei nämlich C ein club. Nach Lemma 7.1.3 enthält C einen club D, der isomorph zu cf (κ) ist. Sei f : cf (κ) ⟶ D die Aufzählungsfunktion. Dann hat für jede Limeszahl λ < cf (κ) f(λ) die Kofinalität cf (λ). f(μ) ist also ein Element von D mit Kofinalität μ.

Die letzten drei Sätze lassen sich als Eigenschaften stationärer Mengen deuten. Lemma 8.1 besagt: Die Vereinigung zweier nicht–stationärer Mengen ist nicht stationär. Lemma 8.2 wird zu: Die Vereinigung von weniger als cf (κ) vielen nicht–stationären Mengen ist nicht stationär. Satz 8.3 liest sich jetzt als: Die Diagonalvereinigung {α < κ | α ∈ ⋃_{β<α} A_{β}} einer Familie (A_{α})_{α<κ} von nicht–stationären Mengen ist nicht stationär. Das sieht man so: sei für jedes α C_{α} ein zu A_{α} disjunkter club, dann ist die Diagonalvereinigung der A_{α} disjunkt zum club Δ_{α<κ}C_{α}. Eine andere Form dieser Aussage ist der Satz von Fodor (cf [4]):

Satz 8.4 (Fodor) Sei S eine stationäre Teilmenge der überabzählbaren regulären Kardinalzahl κ und f : S ⟶ κ eine regressive Funktion. Das heißt, daß f(α) < α für alle α ∈ S. Dann ist f auf einer stationären Teilmenge von S konstant.^{4}

Beweis:

S ist die Diagonalvereinigung der A_{α} = {β ∈ S | f(β) = α}. Weil S stationär ist, muß eine der Mengen A_{α} stationär sein. □

Auf nicht-stationären Mengen S, die 0 nicht enthalten, gibt es immer regressive Funktionen f, die keinen Wert kofinal oft annehmen: Wenn C ein club ist, der zu S disjunkt ist, setze f(s) = sup(s ∩ C).

4Wir meinen eine Teilmenge A von S, die in κ stationär ist. Übung: Definiere „A stationär in S “ und zeige, daß A genau dann in S stationär ist, wenn A in κ stationär ist.

Sei A eine Teilmenge von ω_{1}. Das “A–Spiel” spielen zwei Spieler I und II. I wählt eine Ordinalzahl α_{0} aus ω_{1}, II wählt eine größere Zahl α_{1}, dann wählt I α_{2} > α_{1}, und so weiter. Nach ω vielen Schritten hat I gewonnen, wenn sup_{i<ω} α_{i} ∈ A, sonst hat II gewonnen. Eine Gewinnstrategie für I ist eine Vorschrift, die in Abhängigkeit von den vorausgegangenen Zügen den nächsten Zug von I festlegt. Dabei soll I, wie auch II spielt, immer gewinnen. Eine Gewinnstrategie ist also eine Familie (f_{n})_{n<ω} von Funktionen f_{n} : ω_{1}^{n} ⟶ ω_{1}, sodaß für alle Folgen α_{0} < α_{1} < α_{2} … mit α_{2n} = f_{n}(α_{1}, α_{3}, …, α_{2n−1}) für alle n das Supremum der Folge in A liegt. Eine Gewinnstrategie für II wird analog definiert.

Satz 8.5 I bzw. II hat genau dann eine Gewinnstrategie, wenn A bzw. ω_{1} \ A einen club enthält.

Beweis:

Wir zeigen die Behauptung für I. (Der Beweis der Behauptung für II geht genauso.) Wenn A den club C enthält, wählt I einfach für α_{2n} ein Element aus C, das größer als α_{2n−1} ist. Das ist immer möglich, weil C unbeschränkt ist. Weil C abgeschlossen ist, liegt das Supremum der so gewählten α_{i} in C. Sei (f_{n}) eine Gewinnstrategie für I. Eine Ordinalzahl α < ω_{1} nennen wir abgeschlossen, wenn für alle n

α_{1}, …, α_{n} < α ⟹ f_{n}(α_{1}, …, α_{n}) < α.

Hilfssatz Die Menge C aller abgeschlossenen Ordinalzahlen ist ein club.

Beweis:

Daß C abgeschlossen ist, ist klar. Sei β_{0} eine beliebige Ordinalzahl aus ω_{1}. Definiere rekursiv β_{i+1} = max{β_{i}, sup ⋃ f_{n}[β_{i}^{n}]}. Dann ist sup_{i<ω} β_{i} ∈ C. □(Hilfssatz)

Sei D die Menge der Limesordinalzahlen aus ω_{1} und α ∈ C ∩ D. Wir lassen nun I nach seiner Strategie spielen. Weil α Limeszahl ist, kann II nach einem α_{2n} < α ein α_{2n+1} < α wählen. Die ganze Partie spielt sich dann unterhalb von α ab. Wenn II seine Ordinalzahlen schließlich genügend groß wählt, wird α das Supremum der Folge. Weil ja I das Spiel gewinnen muß, ist α in A. A enthält den club C ∩ D. □

II hat also genau dann keine Gewinnstrategie, wenn A stationär ist. Ein Spiel heißt determiniert, wenn I oder II eine Gewinnstrategie hat. Der nächste Satz liefert die Existenz nicht–determinierter Spiele.

Satz 8.6 (Solovay) Jede überabzählbare reguläre Kardinalzahl κ läßt sich in κ–viele disjunkte stationäre Mengen zerlegen. (cf [14])

Beweis:

Sei S die (stationäre) Menge der Limeszahlen in κ, die die Kofinalität ω haben. Wir wählen für jedes α ∈ S eine echt aufsteigende Folge (δ_{i}^{α})_{i<ω}, die gegen α konvergiert.

Fixiere ein β < κ. Für jedes α aus der stationären Menge S \ β gibt es ein n(α) mit δ_{n(α)}^{α} > β. Nach der “stationären Version” von Lemma 8.2 gibt es ein n_{β}, sodaß die Menge

R_{β} = {α ∈ (S \ β) | n(α) = n_{β}}

stationär ist. Satz 8.4 angewendet auf die regressive Funktion α ↦ δ_{n_{β}}^{α} liefert eine stationäre Teilmenge S_{β} von R_{β}, auf der diese Funktion konstant einen Wert δ^{β} annimmt.

Weil immer δ_{β} > β, ist die Menge der vorkommenden δ_{β} kofinal in κ, hat also die Mächtigkeit κ. Es gibt daher eine κ–mächtige Teilmenge I von κ, für die alle δ_{β} (β ∈ I) verschieden sind.

Weil cf (κ) > ω, gibt es ein n, sodaß die Menge J = {β ∈ I | n_{β} = n} die Mächtigkeit κ hat. Jetzt sind für alle β ∈ J die stationären Mengen S_{β} disjunkt. Denn, wenn α ∈ S_{β}, ist δ_{n}^{α} = δ^{β}. □

Folgerung 8.7 Jedes κ mit überabzählbarer Kofinalität läßt sich in cf (κ)–viele disjunkte stationäre Teilmengen zerlegen.

Beweis:

Sei C ein club in κ, der isomorph zu cf (κ) ist und f : cf (κ) ⟶ C die Aufzählungsfunktion. Wenn die S_{α} disjunkte stationäre Teilmengen von cf (κ) sind, sind die f[S_{α}] disjunkte stationäre Teilmengen von κ. Die f[S_{α}] sind stationär, weil wegen der Stetigkeit von f für jeden club D von κ f^{−1}[D] ein club in cf (κ) ist. □

Weil alle stationären Teilmengen von κ nicht–leeren Schnitt mit C haben, kann κ nicht mehr als |C| = cf (κ)–viele stationäre disjunkte Teilmengen haben.

9 Der Satz von Silver

Satz 9.1 (Silver) Sei κ eine singuläre Kardinalzahl von überabzählbarer Kofinalität. Wenn 2^{μ} = μ^{+} für eine stationäre Menge von Kardinalzahlen μ unterhalb von κ, dann ist auch 2^{κ} = κ^{+}. (cf [13])

Wir beweisen den Satz im Rest des Kapitels.

Sei E ⊂ κ eine stationäre Menge von Kardinalzahlen μ, für die 2^{μ} = μ^{+}. Wir wählen eine echt wachsende, stetige Folge (κ_{α})_{α<cf (κ)} von unendlichen Kardinalzahlen, deren Supremum κ ist. Dann ist

S = {α < cf (κ) | κ_{α} ∈ E}

stationär in cf (κ).

Wir ordnen jeder Teilmenge A von κ die Funktion

f_{A} = ⟨A ∩ κ_{α} | α ∈ S⟩ ∈ ∏_{α∈S} 𝔓(κ_{α})

zu. Die Familie der Funktionen f_{A} ist fast disjunkt: Wenn A ≠ B, gibt es ein α_{0}, sodaß f_{A}(α) ≠ f_{B}(α) für alle α ≥ α_{0}. Satz 9.1 folgt also aus dem nächsten Satz.

Satz 9.2 Sei λ eine reguläre, überabzählbare Kardinalzahl. α ↦ κ_{α} sei eine Normalfunktion von λ nach Card mit Supremum κ. Wir nehmen an, daß λ < κ = 2 ⌣^{κ}. Weiter seien für alle α aus einer stationären Teilmenge S_{0} von λ Mengen A_{α} von höchstens der Mächtigkeit κ_{α}^{+} gegeben. Dann hat jede fast disjunkte Teilmenge von ∏_{α∈S_{0}} A_{α} höchstens die Mächtigkeit κ^{+}.

Wir brauchen zum Beweis das folgende Lemma.

Lemma 9.3 λ und die κ_{α} seien wie in 9.2. Weiter seien für alle α aus einer stationären Teilmenge S von λ Mengen B_{α} von höchstens der Mächtigkeit κ_{α} gegeben. Dann hat jede fast disjunkte Teilmenge von ∏_{α∈S} B_{α} höchstens die Mächtigkeit κ.

Beweis:

Sei 𝔉 fast disjunkt. Dann ist jedes f ∈ 𝔉 innerhalb von 𝔉 durch seine Werte auf den Limeszahlen von S eindeutig bestimmt. Da die Menge der Limeszahlen aus S wieder stationär ist, können wir also annehmen, daß S nur aus Limeszahlen besteht. Weiter können wir annehmen, daß B_{α} = κ_{α}.

Sei f ∈ 𝔉. Dann istf(α) < κ_{α} für jedes α ∈ S. Es gibt also ein β_{α} < α mit f(α) < κ_{β_{α}}. Nach 8.4 gibt es eine stationäre Teilmenge S_{f} von S und ein β, sodaß f(α) < κ_{β} für alle α ∈ S_{f}. Wegen der Fastdisjunktheit von 𝔉 ist f innnerhalb von 𝔉 durch f ↾ S_{f} eindeutig bestimmt. Jedes f ↾ S_{f} gehört aber zu

𝔗 = ⋃ {^{T} μ | T ⊂ λ, μ < κ} .

Weil |^{T} μ| = μ^{|T |} ≤ μ^{λ} ≤ 2^{max{μ,λ}} ≤ 2 ⌣^{κ} = κ für alle T ⊂ λ und μ < κ, ist

|𝔗| ≤ κ ·_{c} 2^{λ} ·_{c} κ = κ

. □

Wir fahren im Beweis von 9.2 fort. Wir können annehmen, daß A_{α} = κ_{α}^{+}. Sei 𝔉_{0} eine fast disjunkte Teilmenge von ∏_{α∈S_{0}} A_{α}. Wir definieren die Relation < auf 𝔉_{0} durch

f < g gdw. es einen club C gibt mit f(α) < g(α) für alle α ∈ S_{0} ∩ C.

Hilfssatz (1) < ist eine partielle Ordnung.

< ist irreflexiv, weil die Mengen S_{0} ∩ C nicht–leer sind und transitiv, weil der Durchschnitt von zwei clubs wieder ein club ist (8.1).

Hilfssatz (2) Für alle g ∈ 𝔉_{0} ist |{f | g ≮ f}| ≤ κ.

Beweis:

Wenn g ≮ f, enthält die Menge

{α ∈ S_{0} | g(α) < f(α)} ∪ (λ \ S_{0})

keinen club. Also ist {α ∈ S_{0} | f(α) ≤ g(α)} stationär. Weil 𝔉_{0} fast disjunkt ist, ist auch

S = {α ∈ S_{0} | f(α) < g(α)}

stationär (wenn wir annehmen, daß f ≠ g). f gehört also zu

𝔉_{S} = {f ∈ 𝔉_{0} | f ↾ S ∈ ∏_{α∈S} g(α)} .

Weil ein f ∈ 𝔉_{S} innerhalb von 𝔉_{0} durch f ↾ S eindeutig bestimmt ist und die Menge der f ↾ S (f ∈ 𝔉_{0}) fast disjunkt ist, folgt aus Lemma 9.3, daß |𝔉_{S}| ≤ κ. Also hat

{f | g ≮ f} = ⋃ {𝔉_{S} | S ⊂ S_{0}, S stationär} ∪ {g}

höchstens die Mächtigkeit 2^{λ} ·_{c} κ = κ. □

Satz 9.2 folgt schließlich aus dem nächsten Lemma.

Lemma 9.4 Sei < eine partielle Ordnung auf P. Wenn für alle p ∈ P die Menge

P_{p} = {q ∈ P | p ≮ q}

höchstens die Mächtigkeit κ ∈ Card hat, hat P höchstens die Mächtigkeit κ^{+}.

Beweis:

Wir wenden Zorns Lemma (2.6) auf die Menge aller streng monotonen Abbildungen f : δ ⟶ P von Ordinalzahlen nach P an, die wir durch (echte) Inklusion ordnen. Sei f_{0} : δ_{0} ⟶ P maximal. Dann gibt es zu jedem q ∈ P ein α < δ_{0} mit f_{0}(α) ≮ q. Es ist also P = ⋃_{α<δ_{0}} P_{f_{0}(α)} und daher |P | ≤ κ ·_{c} |δ_{0}| = max{κ, |δ_{0}|}. Weil aber f_{0}[α] ⊂ P_{f_{0}(α)} für alle α < δ_{0}, haben alle α < δ_{0} höchstens die Mächtigkeit κ. Es folgt δ_{0} ≤ κ^{+}. □

Übung 9.1

1. Sei λ eine reguläre, überabzählbare Kardinalzahl. α ↦ κ_{α} sei eine Normalfunktion von λ nach Card mit Supremum κ. Wir nehmen an, daß λ < κ = 2 ⌣^{κ}. Weiter seien für alle α aus einer stationären Teilmenge S_{0} von λ Mengen A_{α} von höchstens der Mächtigkeit κ_{α}^{++} gegeben. Dann hat jede fast disjunkte Teilmenge von ∏_{α∈S_{0}} A_{α} höchstens die Mächtigkeit κ^{++}.

2. Sei κ eine singuläre Kardinalzahl von überabzählbarer Kofinalität. Wenn 2^{μ} = μ^{++} für eine stationäre Menge von Kardinalzahlen μ unterhalb von κ, dann ist auch 2^{κ} ≤ κ^{++}.

10 Pfeilrelationen

Das Schubfachprinzip in seiner einfachsten Form lautet: Teilt man eine unendliche Menge ein in endlich viele Teile, so ist ein Teil unendlich. Oder anders ausgedrückt: Ist A unendlich und f : A ⟶ m eine Abbildung von A in eine natürliche Zahl m, dann ist f auf einer unendlichen Teilmenge von A konstant. Der Satz von Ramsey ist eine Verallgemeinerung, die für n = 1 das Schubfachprinzip enthält.

Notation [A]^{n} = {b ⊂ A | |b| = n}

Satz 10.1 (Ramsey) Sei A eine unendliche Menge und f : [A]^{n} ⟶ m eine Abbildung der Menge der n–elementigen Teilmengen von A in die natürliche Zahl m. Dann gibt es eine f–homogene unendliche Teilmenge von A. Das ist eine Teilmenge B, für die f auf [B]^{n} konstant ist. (cf [12])

Beweis:

Wir zeigen den Satz durch Induktion nach n. Für n = 0 ist nichts zu zeigen, weil f auf [A]^{n} = {∅} konstant ist. Sei also n > 0.

Wir definieren rekursiv eine absteigende Folge A_{0} ⊃ A_{1} ⊃ ⋯ von unendlichen Teilmengen von A und eine Folge a_{0}, a_{1}, … von Elementen von A mit a_{i} ∈ A_{j} ⟺ i ≥ j.

Wir beginnen mit A_{0} = A. Sei A_{i} bereits konstruiert. Wir wählen ein beliebiges Element a_{i} ∈ A_{i}. Definiere f_{i} : [A_{i} \ {a_{i}}]^{n−1} ⟶ m durch f_{i}(b) = f({a_{i}} ∪ b). Für A_{i+1} wählen wir eine unendliche f_{i}–homogene Teilmenge von A_{i} \ {a_{i}}.

Sei m_{i} der Wert, den f_{i} auf [A_{i+1}]^{n−1} annimmt. Dann ist für jedes k < m die Menge B = {a_{i} | m_{i} = k} f–homogen: Jede n–elementige Teilmenge c von B hat die Form {a_{i}} ∪ b für ein b ∈ [A_{i+1}]^{n−1}. Es ist also f(c) = f_{i}(b) = k. Nach dem Schubfachprinzip gibt es nun ein k < m, sodaß m_{i} = k für unendlich viele i ∈ ω. B ist für dieses k auch unendlich. □

Definition κ, μ und ν seien Kardinalzahlen und n eine natürliche Zahl. Wir schreiben

κ ⟶ (μ)_{ν}^{n},

wenn es zu jeder Abbildung f : [κ]^{n} ⟶ ν eine f–homogene Teilmenge von κ der Mächtigkeit μ gibt.

Der Satz von Ramsey bedeutet, daß ω ⟶ (ω)_{m}^{n} für alle natürlichen Zahlen n, m. Wenn μ < cf (κ) für eine unendliche Kardinalzahl κ, gilt κ ⟶ (κ)_{μ}^{1}, wie man sich leicht überlegt. Für größere Exponenten ist dergleichen falsch:

Bemerkung 2^{ℵ_{0}} −̸→ (ℵ_{1})_{2}^{2}.

Beweis:

Die Menge ℝ der reellen Zahlen hat die Mächtigkeit 2^{ℵ_{0}}. (Man identifiziere reelle Zahlen mit unendlichen Dezimalbrüchen). Sei < die natürliche Ordnung auf ℝ und ≺ eine Wohlordnung von ℝ. Wir definieren f : [ℝ]^{2} ⟶ 2, indem wir einer zwei–elementigen Menge b den Wert 1 zuordnen, wenn < und ≺ auf b übereinstimmen und sonst den Wert 0. Wenn B ⊂ ℝ f–homogen ist, ist B eine Teilmenge von ℝ, die durch < oder durch <^{−1} wohlgeordnet ist. Solche Mengen sind aber höchstens abzählbar. Denn wenn (r_{α})_{α<δ} eine Aufzählungsfunktion von B ist, liegt für alle α + 1 < δ zwischen r_{α} und r_{α+1} eine rationale Zahl q_{α}. Da es aber nur abzählbar viele rationale Zahlen gibt, muß δ abzählbar sein. □

Übung 10.1 Ein partielle Ordnung < P, < > heißt partielle Wohlordnung, wenn P fundiert ist und es keine unendliche Antikette, eine Menge von paarweise unvergleichbaren Elementen, gibt. Man zeige, daß eine partielle Ordnung genau dann eine partielle Wohlordnung ist, wenn es zu jeder Folge (p_{i})_{i<ω} Indizes i < j mit p_{i} ≤ p_{j} gibt.

Der Satz von Erdös–Rado (10.4), den wir später in diesem Kapitel beweisen, zeigt, daß es zu jedem μ, jedem ν und jeder natürlichen Zahl n eine Kardinalzahl κ mit κ ⟶ (μ)_{ν}^{n} gibt. Zum Beweis brauchen wir noch einige Vorbereitungen.

Definition Ein Baum ist eine partielle Ordnung < T, < >, in der für alle x ∈ T die Menge

T_{(x)} = {y | y < x}

wohlgeordnet (insbesondere also linear geordnet) ist.

Bäume sind also fundiert. Zum Beispiel wird ^{<λ}A = ⋃_{α<λ} ^{α}A, durch Inklusion geordnet, zu einem Baum. Man beachte, daß Bäume kein kleinstes Element haben müssen.^{5}

Für einen Baum T verwenden wir folgende Notationen: Ein Teilbaum S von T ist ein Anfangsstück von T, erfüllt also t < s ∈ S ⟹ t ∈ S. Ein Zweig ist ein linear geordneter (also wohlgeordneter) Teilbaum. Der Ordnungstyp h(x) = otp(T_{(x)}) ist die Höhe von x. Die α–te Schicht T_{α} von T ist die Menge der Elemente der Höhe α. Für jedes x ∈ T_{α} und jedes β ≤ α, gibt es genau ein Element y = x ↾ β aus T_{β}, das kleiner–gleich x ist. Die Höhe h(T) von T ist min{α | T_{α} = ∅}. Die Länge eines Zweiges ist sein Ordnungstyp oder, was das gleiche ist, seine Höhe als Baum. T heißt λ–verzweigt, wenn für jeden Zweig z die Menge N(z) = {x | T_{(x)} = z} der Nachfolger von z höchstens die Mächtigkeit λ hat. Zum Beispiel ist ^{<κ}λ λ–verzweigt. Für ein Element x von T schreiben wir auch N(x) für die Menge der Nachfolger von T_{(x)} ∪ {x}. Es ist klar, daß N(x) = {y ∈ T_{α+1} | x < y}, wenn x ∈ T_{α}.

Lemma 10.2 Sei κ ∈ Card und h(T) ≤ κ. Wenn T λ–verzweigt ist (für ein λ > 1), ist |T | ≤ λ ⌣^{κ} .

Beweis:

Wir wählen für jeden Zweig z eine Injektion f_{z} : N(z) ⟶ λ. Wir ordnen jedem x ∈ T_{α} (α < h(T)) eine Funktion g_{x} : (α + 1) ⟶ λ zu, indem wir setzen

g_{x}(β) = f_{T_{(x↾β)}}(x ↾ β).

Wenn x ≠ y, ist g_{x} ≠ g_{y}. Denn sei β ≤ α minimal mit x ↾ β ≠ y ↾ β. Dann ist T_{(x↾β)} = T_{(y↾β)} und

daher g_{x}(β) ≠ g_{y}(β). Es folgt |T_{α}| ≤ λ^{|α+1|} ≤ λ ⌣^{κ} und daraus |T | ≤ |h(T)| ·_{c} λ ⌣^{κ} = λ ⌣^{κ} . □

Satz 10.3 Sei ν ≤ κ. Dann folgt aus κ^{+} ⟶ (μ)_{ν}^{n}, daß (2^{κ})^{+} ⟶ (μ)_{ν}^{n+1}.

Weil κ^{+} ⟶ (κ^{+})_{κ}^{1}, folgt daraus durch Induktion:

Folgerung 10.4 (Erdös-Rado) (Cf [3]) Definiere "Beth-n-κ" durch ℶ_{0}(κ) = κ und ℶ_{n+1}(κ) = 2^{ℶ_{n}(κ)}. Dann ist

(ℶ_{n}(κ))^{+} ⟶ (κ^{+})_{κ}^{n+1}

Beweis: (10.3)

Sei A eine Menge der Mächtigkeit (2^{κ})^{+}, mit einer Wohlordnung ≺ versehen. Sei f : [A]^{n+1} ⟶ ν gegeben. Sei B eine Teilmenge von A und a ein Element von A \ B. Der Typ von a ist eine Funktion t(a/B) : [B]^{n} ⟶ ν, definiert durch t(a/B)(b) = f(b ∪ {a}). Sei a ∈ A gegeben. Wir versuchen, eine Abbildung g_{a} : On ⟶ A rekursiv zu definieren durch die Vorschrift: g_{a}(α) ist das kleinste Element von A\g_{a}[α], das denselben Typ über g_{a}[α] hat wie a. Weil g_{a} injektiv ist, muß die Rekursion abbrechen bei einer Ordinalzahl δ_{a}, für die g_{a}(δ_{a}) = a. g_{a} ist also auf δ_{a} + 1 definiert. Wir machen nun A zu einem Baum, indem wir a < b setzen, wenn g_{a} ein echtes Anfangsstück von g_{b} ist. Die Höhe von a ist dann gerade δ_{a}.

5Bäume ohne kleinstes Element sind sollte man eigentlich Wälder nennen.

Wenn A_{(a)} = A_{(b)}, ist δ_{a} = δ_{b} und g_{a} und g_{b} stimmen auf δ_{a} überein. Wenn a ≠ b, müssen a und b verschiedenen Typ über g_{a}[δ_{a}] haben. Wir zeigen, daß h(A) größer als κ^{+} ist: Sonst wären alle δ_{a} kleiner als κ^{+} und es gäbe höchstens ν^{κ} ≤ 2^{κ} viele Typen über g_{a}[δ_{a}]. Der Baum wäre also

2^{κ}–verzweigt und aus 10.2 folgte |A| ≤ (2^{κ}) ⌣^{κ^{+}} = 2^{κ}. Wir haben aber |A| = (2^{κ})^{+} vorausgesetzt.

Sei also a ein Element der Höhe κ^{+}. Wenn wir die Voraussetzung κ^{+} ⟶ (μ)_{ν}^{n} auf die Funktion t(a/A_{(x)}) anwenden, erhalten wir ein B ⊂ A_{(a)} der Mächtigkeit μ, sodaß t(a/B) eine konstante Funktion ist. Sei ϵ der Wert der Funktion. Wenn c ∈ [B]^{n+1}, schreiben wir c = b ∪ {x} für eine n– elementige Teilmenge b von A_{(x)}. Weil a und x denselben Typ über A_{(x)} haben, ist f(c) = f(b∪{x}) = f(b ∪ {a}) = ϵ. B ist also f–homogen. □

11 Der Satz von König

Ein Baum, in dem jeder Zweig nur endlich viele Nachfolger hat, heißt endlich verzweigt. Man zeigt leicht durch Induktion nach n, daß in einem endlich verzweigten Baum T alle Schichten T_{n} von endlicher Höhe n endlich sind. Ein unendlicher, endlich verzweigter Baum hat also mindestens die Höhe ω.

Satz 11.1 (König) Ein unendlicher, endlich verzweigter Baum hat einen unendlichen Pfad. (cf [8])

Beweis:

Sei T unendlich und endlich verzweigt. Wir konstruieren rekursiv eine aufsteigende Folge a_{0} < a_{1} < … von Elementen a_{i} der Höhe i. Dabei halten wir als Nebenbedingung fest, daß

T^{a_{i}} = {b ∈ T | a_{i} ≤ b}

unendlich ist. Die Menge der a_{i} ist dann der gesuchte unendliche Zweig. Weil T = ⋃_{c∈T_{0}} T^{c} und T_{0} endlich ist, gibt es ein a_{0} ∈ T_{0}, mit unendlichem T^{a_{0}}. Wenn a_{n} schon konstruiert ist, ist T^{a_{n}} = {a_{n}} ∪ ⋃_{c∈N(a_{n})} T^{c}. Wir finden also ein a_{n+1} für das T^{a_{n+1}} unendlich ist. □

Übung 11.1 Ein Baum T, dessen Schichten alle endlich sind, hat einen durchgehenden Zweig, d.h. einen Zweig der Länge h(T).

Ein Baum, dessen Höhe α eine Limesordinalzahl ist, hat im allgemeinen keinen durchgehenden Zweig. Ein Baum der Höhe α ohne durchgehenden Zweig ist zum Beispiel T = {(γ, δ) | γ ≤ δ < α}, geordnet durch

(γ, δ) < (γ′, δ′) ⟺ γ < γ′ und δ = δ.′

T besteht aus nebeneinandergelegten Zweigen der Länge δ für alle δ < α. Die Mächtigkeit von T_{β} ist |α \ β|. Wenn α = κ eine Kardinalzahl ist, haben alle Schichten die Mächtigkeit κ.

Definition Ein Baum der Höhe κ ∈ Card, ohne durchgehenden Zweig, heißt κ–Aronszajnbaum, wenn alle Schichten eine kleinere Mächtigkeit als κ haben.

Der Satz von König sagt aus, daß es keinen ω-Aronszajnbaum gibt.

Satz 11.2 Es gibt einen ω_{1}–Aronszajnbaum. (cf [10])

Beweis:

Der Baum P = ^{<ω_{1}}ω hat die Höhe ω_{1}, aber auch Zweige der Länge ω_{1}: Jede Funktion f : ω_{1} ⟶ ω liefert einen durchgehenden Zweig z = {f ↾ α | α < ω_{1}} (jeder durchgehende Zweig hat diese Form). Schränkt man sich auf den Teilbaum R der injektiven Funktionen von abzählbaren Ordinalzahlen nach ω ein, so kann es keine Zweige der Länge ω_{1} mehr geben, weil es keine injektiven Funktionen von ω_{1} nach ω gibt. R hat aber immer noch die Höhe ω_{1}.

R ist kein Aronszajnbaum, weil die Schichten zu breit sind: die Elemente von R_{α} sind die injektiven Funktionen von α nach ω. Wenn α unendlich ist, gibt es davon 2^{ω} viele. Wir gehen zunächst zu einem noch kleineren Teilbaum von R über: S sei der Teilbaum, der aus denjenigen Elementen f von R besteht, für die ω \ Wb(f) unendlich ist.

Für zwei Elemente f : α ⟶ ω und g : β ⟶ ω von P definieren wir f ⊑ g, wenn α ≤ β und g auf α nur an endlich vielen Stellen nicht mit f übereinstimmt. ⊑ ist offensichtlich reflexiv und transitiv. ⊑ ist nicht antisymmetrisch, also keine partielle Ordnung. Trotzdem macht es Sinn von Ketten und oberen Schranken bzgl. ⊑ zu sprechen.

Hilfssatz In ⟨S, ⊑⟩ hat jede abzählbare Kette eine obere Schranke.

Beweis: des Hilfssatzes

Die aufsteigende Folge f_{0} ⊑ f_{1} ⊑ f_{2} … sei kofinal in der Kette und f_{i} : α_{i} ⟶ ω. Sei α die Vereinigung der α_{i}. Wir konstruieren g : α ⟶ ω aus S mit f_{i} ⊑ g für alle i. Wir definieren g rekursiv auf den α_{i}, sodaß

1. g_{i} = g ↾ α_{i} injektiv ist,

2. g_{i} auf α_{i} außer an endlich vielen Stellen mit f_{i} übereinstimmt,

3. g_{i} unendlich viele Werte ausläßt.

Außerdem konstruieren wir rekursiv eine Folge (n_{i}) von paarweise verschiedenen natürlichen Zahlen, sodaß g_{i} die Werte n_{0}, … n_{i} ausläßt. g läßt dann die Werte {n_{i} | i ∈ ω} aus.

Wir setzen g_{0} = f_{0}. Sei nun g_{i} und n_{0}, …, n_{i−1} schon konstruiert. Für n_{i} wählen wir eine neue Zahl, die von g_{i} ausgelassen wird. f_{i+1} stimmt auf α_{i} mit g_{i} an fast allen Stellen überein. Sei a die (endliche) Menge der Elemente von α_{i+1}\α_{i}, auf denen f_{i+1} einen Wert aus A = Wb(g_{i})∪{n_{0}, …, n_{i}} annimmt. Wir wählen eine injektive Abbildung h : a ⟶ ω \ A und setzen

g_{i+1} = g_{i} ∪ (f_{i+1} ↾ (α_{i+1} \ (α_{i} ∪ a))) ∪ h.

□(Hilfssatz)

Der Hilfssatz liefert uns jetzt eine Folge f_{α} : α ⟶ ω von Elementen aus S mit f_{α} ⊑ f_{β} für alle α < β. Der gesuchte Teilbaum von S ist T = {g ∈ S | g ⊑ f_{α} für ein α < ω_{1}}. T_{α} besteht gerade aus den Elementen g : α ⟶ ω von S, die fast überall mit f_{α} übereinstimmen und hat also (wenn α > 0) die Mächtigkeit max{ω, |α|} < ω_{1}. □

Übung 11.2 (Specker) (Cf [15]) Wenn κ ∈ Card regulär ist, und 2^{μ} ≤ κ für alle μ < κ, dann gibt es einen κ^{+}–Aronszajnbaum.

12 Schwach kompakte Kardinalzahlen

Überabzählbare, reguläre Limeskardinalzahlen heißen unerreichbar. Eine Limeskardinalzahl κ heißt starke Limeskardinalzahl, wenn 2^{μ} < κ für alle μ < κ. Eine unerreichbare starke Limeszahl heißt stark unerreichbar.

Definition Eine überabzählbare Kardinalzahl κ heißt schwach kompakt, wenn

κ ⟶ (κ)_{2}^{2}.

Lemma 12.1 Schwach kompakte Kardinalzahlen sind stark unerreichbar.

Beweis:

Sei κ schwach kompakt. κ ist disjunkte Vereinigung von cf (κ)–vielen Mengen A_{α} (α < cf (κ)) von kleinerer Mächtigkeit als κ. Definiere f : [κ]^{2} ⟶ 2 durch f{β, γ} = 0, wenn β und γ im gleichen A_{α} liegen, und = 1 sonst. Sei B homogen von der Mächtigkeit κ. Weil B nicht in einer der Mengen A_{α} enthalten sein kann, liegen alle Elemente von B in verschiedenen A_{α}. Also ist κ = |B| ≤ cf (κ). Das zeigt die Regularität.

Wenn κ keine starke Limeszahl ist, gibt es ein μ < κ mit 2^{μ} ≥ κ. Wir wählen μ minimal mit dieser Eigenschaft und haben 2^{ν} < κ für alle ν < μ. Weil κ regulär ist, gibt es ein λ < κ mit 2^{ν} ≤ λ für alle ν < μ, also ist 2 ⌣^{μ} ≤ λ. Die lineare Ordnung des nächsten Lemmas hat die Mächtigkeit 2^{μ} und eine dichte Teilmenge der Mächtigkeit λ. Der Beweis der Bemerkung nach 10.1 zeigt, daß 2^{μ} −̸→ (λ^{+})_{2}^{2}. Daraus folgt aber nun κ −̸→ (κ)_{2}^{2}. □

Lemma 12.2 Für alle μ ∈ Card gibt es eine lineare Ordnung der Mächtigkeit 2^{μ} mit einer dichten Teilmenge der Ordnung 2 ⌣^{μ}.

Beweis:

Wir geben dem Baum T = ^{≤μ}2 eine lineare Ordnung durch

f ≤ g ⟺ \{ \begin{matrix}f ⊂ g & oder \\ f(α) < g(α) und f ↾ α = g ↾ α & für ein α ∈ D(f) ∩ D(g). \end{matrix} \}

Seien f < g aus ^{≤μ}2 und α < μ maximal mit f ↾ α = g ↾ α = h. Dann liegt h ∪ {< α, 1 >} zwischen f und g. ^{<μ}2 liegt also dicht in T. T hat die Mächtigkeit 2^{μ} und ^{<μ}2 die Mächtigkeit 2 ⌣^{μ}. □

Satz 12.3 Für eine überabzählbare Kardinalzahl κ sind äquivalent:

1. κ ist schwach kompakt.

2. κ ⟶ (κ)_{ν}^{n} für alle n ∈ ω und ν < κ.

3. κ ist stark unerreichbar und es gibt keinen κ–Aronszajnbaum.

Beweis:

2. ⇒ 1. Klar

1. ⇒ 3. Sei < T, < > ein Baum der Höhe κ, dessen Schichten alle kleinere Mächtigkeit als κ haben. Wir wählen für jeden Zweig z eine lineare Ordnung ≺′ der Nachfolgermenge N(z). Dann können wir auf T wie im Beweis von 12.2 durch

x ≺ y ⟺ \{ \begin{matrix}x < y & oder \\ x ↾ α ≺′ y ↾ α und T_{(x↾α)} = T_{(y↾α)} & für ein α < min\{h(x), h(y)\} \end{matrix} \}

eine lineare Ordnung definieren mit der folgenden Eigenschaft: Für alle x, y ∈ T_{α} ist

x < x′, y < y′, x ≺ y ⇒ x′ ≺ y′.

Weil κ schwach kompakt ist, hat T eine durch ≺ oder durch ≺^{−1} wohlgeordnete Teilmenge der Mächtigkeit κ. Die beiden Fälle sind symmetrisch. Also nehmen wir an, daß (x_{β})_{β<κ} eine bezüglich ≺ echt aufsteigende Folge ist. Wir halten ein α < κ fest. Weil nach 12.1 κ regulär ist, gibt es weniger als κ viele x_{β} mit höchstens der Höhe α und daher ist für genügend große β die Höhe von x_{β} größer als α. Wegen der besonderen Eigenschaft von ≺ ist also für genügend große β die Folge x_{β} ↾ α schwach monoton wachsend. Wieder können wir aus der Regularität von κ schließen, daß die Folge der x_{β} ↾ α schließlich konstant ist. Sei y_{α} ∈ T_{α} der Wert, der schließlich angenommen wird. Die Menge der y_{α} (α < κ) ist ein Zweig der Länge κ.

3. ⇒ 2. Wir beweisen κ ⟶ (κ)_{ν}^{n} für alle n ∈ ω und ν < κ durch Induktion über n. Das Schubfachprinzip κ ⟶ (κ)_{ν}^{1} gilt für alle regulären Kardinalzahlen.

Der Beweis des Induktionsschritts n ⟶ n + 1 folgt dem Beweis von 10.3: Sei A eine Menge der Mächtigkeit κ, mit einer Wohlordnung ≺. Sei f : [A]^{n+1} ⟶ ν gegeben. Sei B eine Teilmenge von A und a ein Element von A \ B. Der Typ t(a/B) von a über B ist definiert wie in 10.3. Für jedes a ∈ A definieren wir g_{a} : (δ_{a} + 1) ⟶ A rekursiv durch:

1. g_{a}(α) ist das kleinste Element von A \ g_{a}[α], das denselben Typ über g_{a}[α] hat wie a.

2. g_{a}(δ_{a}) = a.

a ≤ b ⟺ g_{a} ⊂ g_{b} definiert eine Baumordnung auf A mit h(a) = δ_{a}.

Wir behaupten, daß A einen Zweig B′ der Länge κ hat: Wenn h(A) > κ, setzen wir B′ = A_{(a)} für ein Element a der Höhe κ. Sei also h(A) ≤ κ und ein α < κ festgehalten. Dann gibt es für alle a mit h(a) < α höchstens max {ω, ν^{|δ_{a}|}} ≤ max{ω, ν^{|α|}} viele Typen über g_{a}[δ_{a}]. Aus Lemma 10.2 folgt |A_{α}| ≤ max{ω, ν^{|α|}} < κ. Es muß also h(A) = κ sein und, weil es keinen κ–Aronszajnbaum gibt, muß ein Zweig B′ der Länge κ existieren.

Für alle b_{0} < … < b_{n} ∈ B′ hängt f({b_{0}, …, b_{n}}) nur von {b_{0}, …, b_{n−1}} ab. Wir schreiben

g({b_{0}, …, b_{n−1}}) = f({b_{0}, …, b_{n}}).

Aus κ ⟶ (κ)_{ν}^{n} folgt, daß B′ eine Teilmenge B der Mächtigkeit κ hat, die g–homogen, und daher auch f–homogen ist. □

Wir haben im Beweis von 3. ⇒ 2. die Regularität von κ nicht verwendet. Man hat in der Tat:

Übung 12.1 Wenn es keinen κ–Aronszajnbaum gibt, ist κ regulär.

Der nächste Satz zeigt, daß es unter jeder schwach kompakten Zahl kofinal viele stark unerreichbare Kardinalzahlen gibt.

Satz 12.4 Schwach kompakte Kardinalzahlen κ sind Mahlo–Kardinalzahlen. Das heißt, daß die Menge aller stark unerreichbaren Kardinalzahlen unterhalb von κ stationär in κ ist.

Beweis:

Sei κ stark unerreichbar und die Menge der stark unerreichbaren Kardinalzahlen unterhalb von κ nicht stationär. Weil die Menge aller überabzählbaren starken Limeskardinalzahlen ein club in κ ist, ist die Menge der regulären Kardinalzahlen unterhalb von κ nicht stationär. Es gibt also einen club C von singulären (überabzählbaren) Kardinalzahlen in κ. Weil κ regulär ist, hat C den Ordnungstyp κ.

Sei T die Menge aller auf echten Anfangsstücken von C definierten regressiven injektiven Funktionen. Durch Inklusion geordnet wird T zu einem Baum. Wir zeigen, daß T ein κ–Aronszajnbaum ist.

T_{α} besteht allen Funktionen von T mit Definitionsbereich μ ∩ C, wobei μ das α–te Element von C ist. Wir haben also |T_{α}| ≤ μ^{μ} < κ. Ein Zweig der Länge κ ergäbe eine regressive injektive auf C definierte Funktion. Das ist nach dem Satz von Fodor (und der Regularität von κ) unmöglich.

Um zu zeigen, daß T die Höhe κ hat, müssen wir beweisen, daß es für jedes μ ∈ C eine regressive injektive Funktion f_{μ} : μ ∩ C ⟶ μ gibt. Wir zeigen das durch Induktion nach μ. Wenn μ ∩ C ein Maximum ν hat, ersetzen wir zuerst f_{ν} durch f′_{ν}(β) = f_{ν}(β) + 1. f′_{ν} ist immer noch regressiv, nimmt aber nicht den Wert 0 an. Jetzt leistet f_{μ} = f′_{ν} ∪ {< ν, 0 >} das Gewünschte. Sonst ist μ ∩ C ein club in μ und nach Lemma 7.1 gibt es eine Normalfunktion α ↦ κ_{α} von λ = cf (μ) nach μ ∩ C, deren Bild kofinal in μ ist. Wir nehmen an, daß λ < κ_{0} und verwenden die Abkürzung g_{α} = f_{κ_{α}}. Dann definieren wir für ν ∈ μ ∩ C

f_{μ}(ν) = \{ \begin{matrix}κ_{α} + g_{α+1}(ν) , wenn & κ_{α} < ν < κ_{α+1} \\ ωg_{0}(ν) , wenn & ν < κ_{0} \\ α + 1 , wenn & ν = κ_{α}. \end{matrix}

f_{μ} ist regressiv und injektiv. Um die Regressivität einzusehen, beachte man, daß ν eine unendliche Kardinalzahl ist. Daraus folgt κ_{α}, g_{α+1}(ν) < ν ⇒ κ_{α} + g_{α+1}(ν) < ν und g_{0}(ν) < ν ⇒ ωg_{0}(ν) < ν. □

13 Meßbare Kardinalzahlen

Ein Filter 𝔽 auf einer Menge I ist ein System von Teilmengen von I mit den folgenden Eigenschaften.

1. ∅ ∉ 𝔽, I ∈ 𝔽

2. 𝔽 ist abgeschlossen unter endlichen Durchschnitten.

3. 𝔽 enthält mit einer Menge A auch alle Teilmengen von I, die A enthalten.

Eine Abbildung f : I ⟶ J transportiert 𝔽 auf J:

f(𝔽) = {A ⊂ J | f^{−1}[A] ∈ 𝔽}

ist ein Filter auf J, das Bild von 𝔽. Wenn I Teilmenge von J ist, induziert insbesondere (durch die Inklusionsabbildung) jeder Filter auf I einen Filter auf J.

Zorns Lemma zeigt, daß jeder Filter in einem maximalen Filter auf I, einem Ultrafilter, enthalten ist.

Lemma 13.1 Für einen Filter 𝔽 auf I sind äquivalent:

1. 𝔽 ist ein Ultrafilter.

2. Für alle Teilmengen A von I gehört (entweder) A oder I \ A zu 𝔽.

3. Wenn A ∪ B ∈ 𝔽, dann gehört A oder B zu 𝔽.

Beweis:

Sei A eine Teilmenge von I. Wenn A nichtleeren Schnitt mit allen Elementen von 𝔽 hat, ist

{B ∈ 𝔓(I) | ∃F ∈ 𝔽 A ∩ F ⊂ B}

ein Filter (der kleinste), der A und 𝔽 enthält. Also ist 𝔽 ein Ultrafilter genau dann, wenn 𝔽 alle Mengen A enthält, die alle Elemente von 𝔽 schneiden.

Wenn nun weder B noch A zum Ultrafilter 𝔽 gehören, sind A und B disjunkt zu F und G aus 𝔽. Dann ist A ∪ B disjunkt zu F ∩ G und kann nicht zu 𝔽 gehören. Das beweist 1. ⇒ 3.

Nehmen wir an, daß 𝔽 die Eigenschaft 2. (ein Spezialfall von 3. ) hat und 𝔾 eine Erweiterung von 𝔽 ist. Für alle A gilt dann A ∈ 𝔾 ⇒ (I \ A) ∉ 𝔾 ⇒ (I \ A) ∉ 𝔽 ⇒ A ∈ 𝔽. Also ist 𝔽 = 𝔾 und 𝔽 muß ein Ultrafilter sein. □

Man sieht nun leicht, daß das Bild eines Ultrafilters wieder ein Ultrafilter ist.

Der von ∅ ≠ A ⊂ I erzeugte Hauptfilter ist der Filter 𝔽 aller Teilmengen von I, die A enthalten. 𝔽 ist genau dann ein Ultrafilter, wenn A eine Einermenge ist. Wir nennen einen solchen Ultrafilter trivial. Ein Filter, der eine Einermenge enthält, ist ein trivialer Ultrafilter. Ein Ultrafilter, der eine endliche Menge enthält, enthält wegen Lemma 13.1.3. auch eine Einermenge und ist daher trivial.

Lemma 13.2 Auf jeder unendlichen Menge gibt es einen nichttrivialen Ultrafilter.

Beweis:

Sei 𝔽 das System

{A ⊂ I | (I \ A) endlich}

der koendlichen Teilmengen von I. Die nichttrivialen Ultrafilter auf I sind genau die Ultrafilter, die 𝔽 enthalten. Wenn I unendlich ist, ist 𝔽 ein Filter und also in einem Ultrafilter enthalten. □

Definition Ein Filter 𝔽 heißt κ–vollständig, wenn der Durchschnitt von weniger als κ–vielen Elementen von 𝔽 wieder zu 𝔽 gehört.

Jeder Filter ist ω-vollständig. Hauptfilter sind κ–vollständig für jedes κ. Das Bild eines κ–vollständigen Filters ist wieder κ–vollständig.

Lemma 13.3 Sei 𝕌 ein Ultrafilter auf I und κ eine Kardinalzahl. Dann sind äquivalent:

1. 𝕌 ist κ–vollständig.

2. Der Durchschnitt von weniger als κ-vielen Elementen von 𝕌 ist nichtleer.

3. Wenn eine Vereinigung von weniger als κ–vielen Mengen zu 𝕌 gehört, dann gehört schon eine dieser Mengen zu 𝕌.

Beweis:

2. folgt sofort aus der κ–Vollständigkeit. Wenn umgekehrt für ein μ < κ alle A_{α} (α < μ) zu 𝕌 gehören, ihr Durchschnitt D aber nicht, dann gehören alle (A_{α} \ D) zu 𝕌 und ihr Durchschnitt ist leer.

Geht man zu Komplementen über, sieht man mit Hilfe von 13.1, daß 3. nur die duale Formulierung der κ–Vollständigkeit ist. □

Aus 3. folgt, daß jeder κ–vollständige Ultrafilter, der eine Menge von kleinerer Mächtigkeit als κ enthält, ein Hauptfilter sein muß. Insbesondere ist jeder κ^{+}–vollständige Ultrafilter auf κ ein Hauptfilter.

Definition Ein nichttrivialer κ–vollständiger Ultrafilter auf einer überabzählbaren Kardinalzahl κ, heißt meßbar. Eine überabzählbare Kardinalzahl, die einen meßbaren Ultrafilter trägt, heißt meßbare Kardinalzahl.

Ein Filter 𝔽 auf κ heißt uniform, wenn er nicht von einem Filter auf einer Teilmenge induziert wird, die kleinere Mächtigkeit als κ hat. Oder äquivalent: wenn alle Elemente von 𝔽 die Mächtigkeit κ haben. Es ist klar, daß meßbare Ultrafilter uniform sind.

Lemma 13.4 Wenn es für ein überabzählbares λ einen nichttrivialen λ–vollständigen Ultrafilter auf I gibt, gibt es eine meßbare Kardinalzahl κ mit λ ≤ κ ≤ |I|.

Beweis:

Sei 𝕌 ein λ–vollständiger Ultrafilter auf I. Weil 𝕌 nicht |I|^{+}–vollständig ist, gibt es ein κ ≤ |I| und eine Familie (A_{α})_{α<κ} von Elementen von 𝕌 mit leerem Schnitt. Wenn wir κ minimal wählen, ist κ die größte Kardinalzahl, für die 𝕌 κ–vollständig ist. Wähle nun für jedes a ∈ I ein f(a) = α ∈ κ mit a ∉ A_{α}. Der Bildfilter f(𝕌) ist ein κ–vollständiger Ultrafilter auf κ, der nichttrivial ist, weil alle f^{−1}[{α}] disjunkt zu A_{α} sind und also nicht zu 𝕌 gehören. □

Satz 13.5 Meßbare Kardinalzahlen sind schwach kompakt.

Beweis:

Sei 𝕌 ein nichttrivialer, κ–vollständiger Ultrafilter auf κ.

1. κ ist regulär: Sonst ist κ Vereinigung von weniger als κ vielen Mengen A_{α} von kleinerer Mächtigkeit. Wegen 13.3 muß dann eine der Mengen A_{α} zu 𝕌 gehören. 𝕌 enthält aber keine Menge von kleinerer Mächtigkeit als κ.

2. κ ist starke Limeszahl: Sei μ < κ und f : κ ⟶ 𝔓(μ) eine Abbildung. Dann ist 𝔙 = f(𝕌) ein κ–vollständiger Ultrafilter auf 𝔓(μ). Sei für a ∈ μ ℍ_{a} der von a erzeugte Hauptfilter. Sei 𝔽 der Durchschnitt aller Mengen der Form ℍ_{a} und 𝔓(μ) \ ℍ_{a}, die zu 𝔙 gehören. Dann gehört 𝔽 zu 𝔙. Andererseits ist 𝔽 = {A}, wobei A = {a ∈ μ | ℍ_{a} ∈ 𝔙}. 𝔙 ist also trivial, woraus folgt, daß f nicht injektiv sein kann. Folglich ist 2^{μ} < κ.

3. Es gibt keinen κ–Aronszajnbaum: Sei T ein Baum der Höhe κ, dessen Schichten alle kleinere Mächtigkeit als κ haben. Weil |T | = κ, gibt es einen nichttrivialen κ–vollständigen Ultrafilter auf T. Weil κ regulär ist, hat für alle α < κ die Vereinigung aller T_{β} (β < α) kleinere Mächtigkeit als κ, gehört also nicht zu 𝕌. Es folgt, daß ⋃_{a∈T_{α}} T^{a} und also ein T^{a_{α}} für^{6} ein a_{α} ∈ T_{α} zu 𝕌 gehört. Die a_{α} (α < κ) bilden einen Zweig der Länge κ. □

Definition Ein meßbarer Ultrafilter 𝕌 auf κ heißt normal, wenn es zu jeder auf einer Menge U ∈ 𝕌 regressiven Funktion f eine Teilmenge V ∈ 𝕌 gibt, auf der f konstant ist (Fodoreigenschaft).

Die Elemente U eines normalen Ultrafilters 𝕌 sind immer stationär: Denn sonst gäbe es, wie wir im Anschluß an Satz 8.4 gesehen haben, auf U \{0} eine regressive Funktion f, die keinen Wert kofinal oft annimmt, f wäre also auf keiner Ultrafiltermenge konstant.

Daraus folgt, daß 𝕌 alle clubs enthält.

Übung 13.1

1. Ein uniformer Ultrafilter auf κ, der die Fodoreigenschaft hat, ist κ–vollständig.

2. Ein uniformer Ultrafilter 𝔽 ist genau dann normal, wenn der Diagonaldurchschnitt von Elementen von 𝔽 wieder zu 𝔽 gehört.

Übung 13.2 Sei 𝕌 ein normaler Ultrafilter auf κ und für ein n < ω und λ < κ f : [κ]^{n} ⟶ λ. Dann hat f eine homogene Menge aus 𝕌.

Satz 13.6 Auf meßbaren Kardinalzahlen gibt es normale Ultrafilter.

Beweis:

Sei 𝕌 ein meßbarer Ultrafilter auf κ. Sei R eine n–stellige Relation und f_{1}, …, f_{n} auf κ definierte Funktionen. Wir sagen, daß

R(f_{1}, …, f_{n}) (mod 𝕌)

wenn die Menge aller α ∈ κ für die R(f_{1}(α), …, f_{n}(α)) gilt, zum Ultrafilter gehört. Man sieht leicht, daß für beliebige Filter 𝕌 sich Reflexivität, Transitivität und Symmetrie von R auf R (mod 𝕌) übertragen. Die Gleichheit (mod 𝕌) ist also eine Äquivalenzrelation auf der Klasse aller auf κ definierten Funktionen. Die Ultrapotenz

a^{𝕌}

einer Menge a ist die Menge der Äquivalenzklassen aller Funktionen von κ nach a. Das Bestehen einer Relation R(f_{1}, …, f_{n}) (mod 𝕌) hängt nur von den Äquivalenzklassen der f_{i} ab. Es ist also eine Relation R^{𝕌} auf der Ultrapotenz definiert.

Wenn r eine lineare Ordnung auf a ist, ist r^{𝕌} eine lineare Ordnung auf a^{𝕌}. Denn weil ∅ = {α ∈ κ | α < α} ∉ 𝕌, ist r^{𝕌} irreflexiv und damit eine partielle Ordnung. Weil für alle f, g ∈ ^{κ}a

κ = {α | f(α) < g(α)} ∪ {α | f(α) = g(α)} ∪ {α | g(α) < f(α)},

liegt eine dieser Mengen im Ultrafilter 𝕌. Das zeigt, daß r^{𝕌} eine totale Ordnung ist.

6Erinnerung: T^{a} = {b ∈ T | a ≤ b}

Wenn r fundiert ist, ist auch r^{𝕌} fundiert: Wenn f_{i+1}r^{𝕌}f_{i} für i = 0, 1 …, sind die A_{i} = {α | f_{i+1}(α)rf_{i}(α)} aus 𝕌. Für α aus dem Durchschnitt der A_{i} ist dann (f_{i}(α)) eine unendliche absteigende Folge, die der Fundiertheit von r widerspricht.

Wir betrachten nun die Ultrapotenz κ^{𝕌}. Für jedes α ∈ κ sei ᾱ die Äquivalenzklasse der konstanten Funktion mit Wert α. κ^{𝕌} wird durch < (mod 𝕌) wohlgeordnet. Aus der κ–Vollständigkeit von 𝕌 folgt nun, daß die Abbildung α ↦ ᾱ eine ordnungstreue Abbildung von κ auf ein Anfangsstück von κ^{𝕌} ist: Wenn die Äquivalenzklasse von f kleiner als β̄ ist, gehört

{α | f(α) < β} = ⋃_{γ<β}{α | f(α) = γ}

zu 𝕌. Also muß für ein γ die Menge {α | f(α) = γ} zu 𝕌 gehören. Das heißt, γ̄ ist die Äquivalenzklasse von f.

Sei f eine Funktion , deren Äquivalenzklasse das Supremum der ᾱ (α < κ) in κ^{𝕌} ist. Wir setzen 𝕍 = f(𝕌). 𝕍 ist ein κ–vollständiger Ultrafilter auf κ. 𝕍 ist nichttrivial, weil f nicht auf einer Menge aus 𝕌 konstant ist. Sei nun g auf einer Menge aus 𝕍 regressiv. Dann gehört {α | (g ∘ f)(α) < f(α)} zu 𝕌. Nach der Wahl von f ist g ∘ f auf einer Menge U ∈ 𝕌 konstant. Dann ist g konstant auf f[U] ∈ 𝕍. □

Satz 13.7 Wenn 𝕌 ein normaler Ultrafilter auf κ ist, gehört die Menge aller schwach kompakten Kardinalzahlen unterhalb von κ zu 𝕌.

Beweis:

Weil 𝕌 normal ist, gehört der club der überabzählbaren Kardinalzahlen unterhalb von κ zu 𝕌. Nehmen wir an, daß der Satz falsch ist. Dann gibt es eine Ultrafiltermenge U_{0} von nicht schwach–kompakten überabzählbaren Kardinalzahlen unterhalb von κ. Wähle für jedes λ ∈ U_{0} ein f_{λ} : [λ]^{2} ⟶ 2, das keine homogene Menge der Mächtigkeit λ hat. Definiere das “Ultraprodukt” f : [κ]^{2} ⟶ 2 der f_{λ} durch

f(a) = i ⟺ {λ ∈ U_{0} | a ⊂ λ ∧ f_{λ}(a) = i} ∈ 𝕌.

Das ist eine wohldefinierte Funktion, weil für alle a die Menge der λ aus U_{0}, die a enthalten, in 𝕌 liegt. Wir werden zeigen, daß f keine homogene Menge der Mächtigkeit κ haben kann, und erhalten damit den gewünschten Widerspruch zu 13.5.

Jede Teilmenge B von κ ist “Ultraprodukt” der B_{α} = B ∩ α (α < κ), in dem Sinn, daß für alle β < κ

β ∈ B ⟺ {α | β ∈ B_{α}} ∈ 𝕌.

Wenn B homogen für f ist (sagen wir mit Wert 0), sind die B_{λ} homogen für f_{λ} mit Wert 0 für ultrafilterviele λ. Denn sonst gibt es für alle λ aus einer Ultrafiltermenge U_{1} ⊂ U_{0} Elemente α_{λ}^{1} < α_{λ}^{2} < λ aus B mit f_{λ}(α_{λ}^{1}, α_{λ}^{2}) = 1. Weil 𝕌 normal ist, sind aber die Funktionen λ ↦ α_{λ}^{j} auf einer Ultrafiltermenge U_{2} ⊂ U_{1} aus 𝕌 konstant = α^{j}. Auf einer weiteren Ultrafiltermenge U_{3} ⊂ U_{2} ist f_{λ}(α^{1}, α^{2}) = f(α^{1}, α^{2}). Also ist f(α^{1}, α^{2}) = 1. Widerspruch.

Wenn B die Mächtigkeit κ hat, haben für ultrafilterviele α die B_{α} die Mächtigkeit α. Um das einzusehen, wählen wir eine injektive Abbildung g : κ ⟶ B. Sei C die Menge der unter g abgeschlossenen Kardinalzahlen unterhalb von κ, das heißt der Kardinalzahlen α < κ mit g[α] ⊂ α. Man sieht leicht, daß C ein club ist. Dann bildet g alle α ∈ C injektiv nach B_{α} ab. C gehört aber zu 𝕌.

Jetzt sehen wir, daß f keine homogene Menge der Mächtigkeit κ haben kann. Denn sonst wären für ultrafilterviele λ die B_{λ} Mengen der Mächtigkeit λ und homogen für f_{λ}. □

14 Transitive Modelle der Mengenlehre

Ein Modell der Mengenlehre ist eine Struktur 𝔪 =< m, e >, in der alle Axiome von ZFC (oder eines Fragments von ZFC) gelten. Wenn wir von einer Menge m als einem Modell sprechen, meinen wir die Struktur < m, ∈↾ m >. Wenn das Modell m transitiv ist, nennen wir m ein transitives Modell.

Satz 14.1 (Isomorphiesatz von Mostowski) (Cf [11]) Für eine Struktur 𝔪 = < m, e > sind äquivalent:

1. 𝔪 ist isomorph zu einer transitiven Menge.

2. 𝔪 ist ein Modell des Extensionalitätsaxioms und e ist eine fundierte Relation.

Der in 1. behauptete Isomorphismus ist eindeutig bestimmt.

Wenn für eine Menge m die Struktur 𝔪 = < m, ∈↾ m > das Extensionalitätsaxiom erfüllt, nennen wir die zu 𝔪 isomorphe transitive Menge den transitiven Kollaps von m.

Beweis:

1.⇒2. Die ∈–Relation ist fundiert. Wenn x und y zwei verschiedene Elemente der transitiven Menge a sind, gibt es ein Element z von x, das nicht zu y gehört (oder umgekehrt). Wegen der Transitivität ist z Element von a. Also haben x und y auch in a nicht die gleichen Elemente. Das beweist, daß a das Extensionalitätsaxiom erfüllt. 2.⇒1. Wir zeigen zuerst die Eindeutigkeit: Sei f : m ⟶ a ein Isomorphismus von 𝔪 mit der Menge a. Dann ist für jedes x ∈ m f(x) ∩ a = f[m_{(x)}], wobei m_{(x)} die Menge der e–Vorgänger von x ist. Wenn a transitiv ist, erfüllt also f die Rekursionsgleichung

(*) f(x) = f[m_{(x)}].

Wegen Übung 4.1 und der Fundiertheit von e ist f (und a = f[m]) durch (*) eindeutig bestimmt. Umgekehrt gibt es wegen 4.1 ein f : m ⟶ V, das (*) erfüllt. Das Bild a von f ist transitiv, weil jedes Element von f(x) Bild eines Elements von m_{(x)} ist. Daß jedes b ∈ a nur ein Urbild hat, zeigen wir durch ∈–Induktion: Wenn f(x) = f(y) = b, ist nach (*) und Induktionsvoraussetzung m_{(x)} = f^{−1}[b] = m_{(y)}. Weil das Extensionalitätsaxiom in 𝔪 gilt, folgt x = y. f : m ⟶ a ist also eine Bijektion. Daß xey ⇔ f(x) ∈ f(y) folgt jetzt sofort aus (*). □

Man beachte, daß zwar ein fundiertes Modell 𝔪 (damit meinen wir ein 𝔪 =< m, e > mit fundiertem e) das Fundierungsaxiom erfüllt, die Umkehrung aber nicht gelten muß. Der Kompaktheitssatz der Modelltheorie hat vielmehr zur Folge, daß eine Theorie, die Modelle 𝔪 mit beliebig langen Ketten x_{n}ex_{n−1}e … ex_{0} hat, auch ein nicht fundiertes Modell haben muß. In 14.8 werden wir zeigen, daß die Existenz von Modellen von ZFC nicht die Existenz von fundierten Modellen impliziert.

Wenn ZFC konsistent ist, läßt sich nach dem zweiten Gödelschen Unvollständigkeitssatz ([6]) in ZFC nicht beweisen, daß ein Modell von ZFC existiert. Wir können aber für jedes endliche Teilsystem von ZFC zeigen, daß es sogar ein transitives Modell besitzt.

Definition Eine Menge a reflektiert die Formel ϕ(x_{1}, …, x_{n}) (ohne Klassenvariablen), wenn für alle b_{1}, …, b_{n} ∈ a

ϕ(b_{1}, …, b_{n}) ⟺ a ⊧ ϕ(b_{1}, …, b_{n}).

Wir sagen auch: ϕ ist absolut für a.

Es seien Formeln ϕ_{1}, …, ϕ_{m} gegeben. Dann gilt:

Satz 14.2 (Reflexionssatz) Die V_{α} reflektieren ϕ_{1}, …, ϕ_{m} für beliebig große α.

Beweis:

Es genügt zu zeigen, daß jede Formel ϕ von allen V_{α}, α aus einem club C_{ϕ} (einer unbeschränkten abgeschlossenen Teilklasse von On), reflektiert wird. Der Beweis geht durch Induktion über den Aufbau von ϕ. Formeln ohne Quantoren werden von allen Mengen reflektiert. Wir können C_{¬ϕ} = C_{ϕ}, C_{ϕ∧ψ} = C_{ϕ} ∩ C_{ψ} setzen.

Wenn ϕ(x_{1}, …, x_{n}) = ∃x_{0} ψ(x_{0}, …, x_{n}), definiere die Funktionale

F (b_{1}, …, b_{n}) = \{ \begin{matrix}0 , & wenn ¬ϕ(b_{1}, …, b_{n}) \\ min\{α | ∃x_{0}ϵV_{α} ψ(x_{0}, b_{1}, …, b_{n})\}, & sonst \end{matrix} \}

und

G(β) = sup {F (b_{1}, …, b_{n}) | b_{1}, …, b_{n} ∈ V_{β}} .

Dann können wir für C_{ϕ} den club der unter G abgeschlossenen Elemente von C_{ψ} nehmen (vgl. den Beweis des Hilfssatzes für 8.5). Denn für α ∈ C_{ϕ} und b_{1}, …, b_{n} ∈ V_{α} ist dann

ϕ(b_{1}, …, b_{n})  ⇔ (weil α G–abgeschlossen ist) es gibt b_{0} ∈ V_{α} mit ψ(b_{0}, …, b_{n}) ⇔  (weil α ∈ C_{ψ}) V_{α} ⊧ ϕ(b_{1}, …, b_{n}).  □

Sei T ein endliches Fragment von ZFC. Dann gilt

Folgerung 14.3 T hat ein Modell der Form V_{α}.

Man beachte daß wir nicht etwa gezeigt haben

ZFC ⊢ (Jedes endliche Fragment von ZFC hat ein Modell).

Sondern nur für jedes endliche Fragment T

ZFC ⊢ (T hat ein Modell).

Mit Hilfe des (in ZFC beweisbaren) Kompaktheitssatzes würde aus der ersten Version folgen, daß

ZFC ⊢ (ZFC hat ein Modell)

… und ZFC wäre inkonsistent.

Übung 14.1 Zeige in ZC, daß das Ersetzungsaxiom genau dann gilt, wenn je endlich viele Formeln von beliebig großen Mengen reflektiert werden (das heißt, daß jede Menge in einer Menge enthalten ist, die diese Formeln reflektiert).

Notation Def (m) bezeichne die Menge aller in m mit Parametern definierbaren Teilmengen von m. Also die Menge aller Mengen der Form

{a_{0} ∈ m | m ⊧ ϕ(a_{0}, …, a_{n})},

für Formeln ϕ und a_{1}, … a_{n} ∈ m.

Lemma 14.4 Eine transitive Menge m ist genau dann ein Modell von ZFC, wenn 1. a ∈ m ∧ b ∈ Def (m) ⇒ a ∩ b ∈ m

2. ∅ ∈ m

3. a, b ∈ m ⇒ {a, b} ∈ m

4. a ∈ m ⇒ ⋃ a ∈ m

5. a ∈ m ⇒ 𝔓(a) ∩ m ∈ m

6. Wenn f ∈ Def (m) eine Funktion ist, ist f[a] ∈ m für alle a ∈ m.

7. ω ∈ m

8. Jedes a ∈ m, das die leere Menge nicht enthält, hat eine Auswahlfunktion aus m.

.

Beweis:

Wir haben schon gesehen, daß das Extensionalitätsaxiom und das Fundierungsaxiom in transitiven Mengen gelten.

Für beliebige Mengen n besagt das Aussonderungsaxiom, daß es für alle a ∈ n und b ∈ Def (n) ein c ∈ n gibt mit a ∩ b = n ∩ c. Wenn n transitiv ist, bedeutet das a ∩ b ∈ n. 1. ist also zur Gültigkeit des Aussonderungsaxioms äquivalent.

Eine Menge n erfüllt das Leere Menge Axiom, wenn es ein a ∈ n gibt mit n ⊧ (a ist leer). Für transitive n ist aber

n ⊧ (a ist leer) ⇔ a ∩ n = ∅ ⇔ a ist leer.

2 ist also das Leere Menge Axiom für m. Die eben hingeschriebene Äquivalenz heißt, daß für transitive Mengen die Formel “… ist leer” absolut ist.

Sei a, b ∈ m. Das Paarmengenaxiom für m bedeutet, daß es ein c ∈ m mit m ⊧ (c =^{.} {a, b}) gibt. Man rechnet leicht nach, daß für transitive Mengen die Formel z =^{.} {x, y} absolut ist. m erfüllt also das Paarmengenaxiom genau dann, wenn 3. gilt.

Die Gültigkeit des Vereinigungsmengenaxioms ist zu 4. äquivalent, weil die Formel x =^{.} ⋃ y absolut für transitive Mengen ist.

Die Formel x ∈ 𝔓(y) ist absolut für transitive Mengen. Also ist m ⊧ b =^{.} 𝔓(a) äquivalent zu b = 𝔓(a) ∩ m. Daraus folgt, daß 5. das Potenzmengenaxiom für m ist.

Das Ersetzungsaxiom bedeutet für beliebige Mengen m, daß es für alle a ∈ m und alle definierbaren f : a ∩ m ⟶ m ein b ∈ m mit b ∩ m = f[a ∩ m] gibt. Wenn m transitiv ist, bedeutet das gerade 6.

Das Unendlichkeitsaxiom ist (auf der Basis der übrigen Axiome) äquivalent dazu, daß ω eine Menge ist. Weil (modulo der anderen Axiome) die Formel x =^{.} ω absolut für transitive Mengen ist (siehe 14.5), sagt das Unendlichkeitsaxiom für m gerade ω ∈ m.

“x ist Auswahlfunktion von y” ist absolut für transitive Mengen (siehe 14.5). Also ist 8. das Auswahlaxiom für m. □

Definition Eine Formel (ohne Klassenvariable) heißt Δ_{0}–Formel, wenn alle Quantoren beschränkt sind. Das heißt, nur in der Form ∃x (xϵy ∧ …) oder ∀x (xϵy → …) vorkommen. Eine Formel heißt Δ_{0}^{ZFC}, wenn sie, beweisbar in ZFC, zu einer Δ_{0}–Formel äquivalent ist.

Der Sinn der zweiten Definition ist, daß man sich z.B. kaum erinnern wird, wie der offizielle Formelausdruck für x =^{.} ω war. Man kann aber eine äquivalente Δ_{0}–Formel angegeben.

Die für transitive Mengen absoluten Formeln des letzten Beweises sind alle Δ_{0}^{ZFC}:

Beispiele: Δ_{0}–Formeln sind

x =^{.} ∅ ⟺ ∀yϵx¬y ∈ x
x =^{.} {y, z} ⟺ (yϵx ∧ zϵx ∧ ∀wϵx(w =^{.} y ∨ w =^{.} z))
x =^{.}< y, z > ⟺ ∃u, vϵx(x =^{.} {u, v} ∧ u =^{.} {x, y} ∧ v =^{.} {x})
x =^{.} ⋃ y ⟺ ((∀wϵx∃zϵy wϵz) ∧ (∀zϵy∀wϵz wϵx))
x ⊂ y ⟺ ∀zϵx zϵy
x transitiv ⟺ ∀yϵx y ⊂ x
xϵOn ⟺ ∀yϵx∀zϵy(zϵx ∧ ∀wϵz wϵy)
Lim(x) ⟺ xϵOn ∧ ¬x =^{.} ∅ ∧ ∀yϵx∃zϵx yϵz (x ist Limeszahl)
xϵω ⟺ xϵOn ∧ ¬Lim(x) ∧ ∀yϵx ¬Lim(y)
x =^{.} ω ⟺ Lim(x) ∧ ∀yϵx ¬Lim(y)

Lemma 14.5 Δ_{0}–Formeln sind absolut für transitive Mengen. Δ_{0}^{ZFC}–Formeln sind absolut für transitive Modelle von ZFC.

Beweis:

Leicht, durch Induktion über den Aufbau der Δ_{0}–Formeln. □

Folgerung 14.6 V_{α} ist genau dann Modell von ZFC (mit eventueller Ausnahme des Unendlichkeitsaxioms und des Ersetzungsaxioms), wenn α Limeszahl ist. Das Unendlichkeitsaxiom gilt genau dann, wenn α größer als ω ist. Wenn α eine stark unerreichbare Kardinalzahl ist, gilt auch das Ersetzungsaxiom.

Beweis:

Nur die letzte Aussage bedarf noch eines Beweises: Sei κ eine stark unerreichbare Kardinalzahl. Man zeigt leicht durch Induktion über α, daß |V_{α}| < κ für alle α < κ. Dann haben also alle a ∈ V_{κ} eine kleinere Mächtigkeit als κ. Wenn f : a ⟶ V_{κ}, ist also {rang(f(b)) | b ∈ a} beschränkt in κ, sagen wir durch β < κ. Dann ist f[a] ⊂ V_{β+1}. Also f[a] ∈ V_{κ}. □

Übung 14.2 Wenn das in der Übung 1.1 definierte Modell fundiert ist, ist es isomorph zu V_{ω}.

Seien ϕ und ψ Aussagen der Mengenlehre, wie zum Beispiel “es gibt eine unerreichbare Kardinalzahl” oder “es gibt eine meßbare Kardinalzahl”. CON(ϕ) sei die Aussage “ZFC + ϕ ist konsistent”. Wir sagen, daß die Konsistenzstärke von ϕ größer ist als die Konsistenzstärke von ψ, wenn

ZFC ⊢ CON(ϕ) ⟶ CON(ψ).

Die Konsistenzstärke ist echt größer, wenn man unter der Voraussetzung, daß ZFC+CON(ψ) konsistent ist, zeigen kann, daß

ZFC ⊬ CON(ψ) ⟶ CON(ϕ).

Es ist klar, daß die Konsistenzstärke von ϕ größer ist als die Konsistenzstärke von ψ, wenn ZFC ⊢ ϕ ⟶ ψ.

Aus dem zweiten Gödelschen Unvollständigkeitssatz folgt:

Lemma 14.7 Die Konsistenzstärke von CON(ϕ) ist echt größer als die Konsistenzstärke von ϕ.

Beweis:

(Wir notieren ZFC nicht mehr.) Daß ⊢ CON(CON(ϕ)) ⟶ CON(ϕ), ist ganz allgemein richtig. Aus CON(ϕ) ⊢ CON(CON(ϕ)) folgt die Inkonsistenz von CON(ϕ) nach dem zweiten Gödelschen Unvollständigkeitssatz. □

Satz 14.8 Die folgenden Aussagen sind nach echt größer werdender Konsistenzstärke geordnet:

1. 0 =^{.} 0

2. ZFC hat ein Modell.

3. ZFC hat ein transitives Modell.

4. Es gibt eine stark unerreichbare Kardinalzahl.

5. Es gibt eine schwach kompakte Kardinalzahl.

6. Es gibt eine meßbare Kardinalzahl.

Beweis:

Die späteren Aussagen implizieren die früheren. Wir haben also nur die Echtheit zu zeigen.

2. ist echt konsistenzstärker als 1.: Das folgt aus 14.7.

3. ist echt konsistenzstärker als 2.: Sei m ein transitives Modell von ZFC. Dann gilt natürlich CON(ZFC). Nach dem Vollständigkeitssatz ist eine Aussage der Form CON(ϕ) eine arithmetische Aussage, also nach Kapitel 15 absolut für transitive Modelle von ZFC. m ist also auch ein Modell von CON(ZFC). Wir haben gezeigt:

ZFC ⊢ (es gibt ein transitives Modell von ZFC) ⟶ CON(CON(ZFC))

Aus 14.7 folgt nun die Behauptung.

4. ist echt konsistenzstärker als 3.: Sei κ eine stark unerreichbare Kardinalzahl. Der Satz von Löwenheim-Skolem (Kapitel 15, S.62) liefert uns eine abzählbare Teilmenge a von V_{κ}, die ebenfalls ein Modell von ZFC ist. Nach 14.1 ist a isomorph zu einem abzählbaren transitiven Modell m. Wie jede erblich abzählbare Menge ist m Element von V_{ω_{1}}, also auch von V_{κ}. (Eine Menge ist erblich abzählbar, wenn sie abzählbar ist und ihre Elemente erblich abzählbar sind.) Nach Kapitel 15 sind Formeln der Form x ⊧ ϕ absolut in transitiven Modellen. Also ist V_{κ} ⊧ (m ist transitives Modell von ZFC) und wir haben gezeigt:

ZFC ⊢ (es gibt eine stark unerreichbare Kardinalzahl) ⟶ CON(ZFC hat ein transitives Modell)

Die Behauptung folgt jetzt aus 14.7.

5. ist echt konsistenzstärker als 4.: Wenn κ schwach kompakt ist, gibt es nach 12.4 eine stark unerreichbare Kardinalzahl in V_{κ}. Man überlegt leicht, daß die Formel

x ist stark unerreichbar

absolut ist für Modelle der Form V_{α} (ebenso wie die Formeln (x ist schwach kompakt) und (x ist meßbar)). Also ist

V_{κ} ⊧ (ZFC + es gibt eine stark unerreichbare Kardinalzahl).

Jetzt folgt die Behauptung mit 14.7.

6. ist echt konsistenzstärker als 5.: Wie im letzten Teil des Beweises mit 13.7. □

Will man auch Klassen als Modelle zulassen, muß man Vorsicht walten lassen. Zunächst ziehen wir uns auf ZFC zurück und meinen, wenn wir von Klassen sprechen, nur Klassen, die durch Formeln (mit eventuellen Parametern) definiert sind – wie zum Beispiel V durch die Formel x =^{.} x. Dann müssen wir beachten, daß es keine Modelltheorie für Klassen gibt, weil es keine Formel gibt, die für Klassen K

x ist eine Aussage ∧ K ⊧ x

vernünftig ausdrückt. Es macht nur Sinn von einzelnen Aussagen ϕ die Formel

K ⊧ ϕ

zu bilden. (Man relativiert einfach die Quantoren in ϕ nach K.) So ist zum Beispiel für jedes Axiom ϕ von ZFC

V ⊧ ϕ

(trivialerweise) in ZFC beweisbar. Die “Aussage”

V ⊧ ZFC

ist aber gar nicht wirklich formulierbar. Würde eine solche Aussage doch irgendwie Sinn machen, hätte man in ZFC die Existenz eines Modells von ZFC bewiesen, was nach Gödels Satz nur bedeuten könnte, daß ZFC inkonsistent wäre. Wenn wir in Zukunft zum Beispiel K ⊧ ZFC schreiben, meinen wir die unendlich vielen Aussagen K ⊧ ϕ für jedes Axiom ϕ.

Satz 14.9 Sei eine Folge K_{α} (α ∈ On) von transitiven Mengen gegeben und es gelte K_{α} ∈ K_{α+1} für alle α und K_{λ} = ⋃_{α<λ} K_{α} für alle Limeszahlen λ. Dann ist K = ⋃_{α∈On} K_{α} genau dann ein Modell von ZF, wenn Def (K_{α}) ∈ K für alle α ∈ On.

Beweis:

Wir werden in Kapitel 15 sehen, daß die Formel x =^{.} Def (y) absolut für transitive Modelle ist (auch für transitive Klassen, in denen ein genügend großes Fragment von ZF gilt). Wenn K ein Modell von ZF ist, muß es ein a ∈ K mit K ⊧ a =^{.} Def (K_{α}) geben. Nach unserer Vorbemerkung ist dann a = Def (K_{α}).

Für die Umkehrung machen wir von 14.4 Gebrauch, das sich sofort auf transitive Klassen überträgt. Sei also Def (K_{α}) ∈ K für alle α. Wir verifizieren die Bedingungen von 14.4 mit der Ausnahme von 8. Die Bedingungen 2,3,4. haben ähnliche Beweise. Zum Beispiel, wenn a ∈ K_{α}, ist ⋃ a ∈ Def (K_{α}) ∈ K. Weil K transitiv ist, ist ⋃ a ∈ K und 4. ist verifiziert.

Um Bedingung 5. zu zeigen, sei für ein a ∈ K die Ordinalzahl α so groß gewählt, daß alle b ∈ 𝔓(a) ∩ K in K_{α} liegen. Jetzt ist aber 𝔓(a) ∩ K ∈ Def (K_{α}) und wir sind fertig.

Für Bedingung 7. überlegen wir, daß aus dem bisher bewiesenen folgt, daß alle natürlichen Zahlen in K und darum in einem genügend großen K_{α} liegen. Weil xϵω absolut für transitive Mengen (und Klassen) ist, ist ω ∈ Def (K_{α}). Daraus folgt die Bedingung.

Um 1. und 6. zu verifizieren überzeugen wir uns zuerst, daß man 14.2 für K ebenso beweisen kann: Für jedes ϕ gibt es beliebig große K_{α}, die ϕ in K reflektieren. Das heißt, daß für alle a_{1}, …, a_{n} ∈ K_{α}

K ⊧ ϕ(a_{1}, …, a_{n}) ⇔ K_{α} ⊧ ϕ(a_{1}, …, a_{n}).

Wir beweisen 1. Sei also a ∈ K und B ⊂ K definierbar in K. Für eine Formel ϕ(x, y_{1}, …, y_{n}) und Parameter b_{1}, …, b_{n} aus K ist also B = {b ∈ K | K ⊧ ϕ(b, b_{1}, …, b_{n})}. α sei nun so groß, daß K_{α} a und die Parameter enthält und ϕ in K reflektiert. Dann ist

a ∩ B = {b ∈ a | K_{α} ⊧ ϕ(b, b_{1}, …, b_{n})} ∈ Def (K_{α}).

Bedingung 6. folgt leicht aus 1: Wenn a ∈ K und F : a ⟶ K ein Funktional ist, gibt es ein α mit F [a] ⊂ K_{α}. Ist F zusätzlich definierbar in K, so ist auch F [a] definierbar in K. Es folgt F [a] = K_{α} ∩ F [a] ∈ K. □

Folgerung 14.10 Definiere die konstruktible Hierarchie durch

L_{0} = ∅
L_{α+1} = Def (L_{α})
L_{λ} = ⋃_{α<λ} L_{α} (λ Limeszahl)

und setze L = ⋃_{α∈On} L_{α}. L – die Klasse der konstruktiblen Mengen – ist ein Modell von ZF.

Wir werden in Kapitel 15 sehen, daß L ein Modell von ZFC ist, in dem GCH gilt.

Beweis:

Wenn L_{α} transitiv ist, ist auch L_{α+1} = Def (L_{α}) transitiv, weil jedes Element a ∈ L_{α} eine definierbare Teilmenge von L_{α} ist. Jetzt folgt durch Induktion, daß alle L_{α} transitiv sind. Weil L_{α} eine definierbare Teilmenge von sich ist, ist L_{α} ∈ L_{α+1}. □

Übung 14.3 Eine Menge der Form

{a ∈ V_{α_{0}} | V_{α_{0}} ⊧ ϕ(a, α_{1}, …, α_{n})},

mit einer Formel ϕ und Ordinalzahlparametern α_{i} aus V_{α_{0}} heißt ordinaldefinierbar. OD sei die Klasse der ordinaldefinierbaren Mengen,

HOD = {a | th(a) ⊂ OD}

die Klasse der erblich (hereditär) ordinaldefinierbaren Mengen. Man zeige

1. Eine Menge der Form {a | ϕ(a, α_{1}, …, α_{n})} ist ordinaldefinierbar.

2. HOD ist ein Modell von ZF.

15 V=L

Wir zeigen in diesem Kapitel, daß L ein Modell von ZFC, GCH und V=L ist.

Definition Eine Σ_{1}–Formel ist eine Formel der Form

∃x ϕ,

wobei ϕ eine Δ_{0}–Formel ist. Eine Σ_{1}^{ZFC}–Formel ist eine Formel, die in ZFC beweisbar zu einer Σ_{1}– Formel äquivalent ist. Eine Δ_{1}^{ZFC}–Formel ist eine Σ_{1}^{ZFC}–Formel, deren Negation ebenfalls eine Σ_{1}^{ZFC}– Formel ist. Eine Σ_{1}^{ZFC}–Funktion ist ein auf V^{n} vermöge

a_{0} = F (a_{1}, …, a_{n}) ⇔ ϕ(a_{0}, …, a_{n})

durch eine Σ_{1}^{ZFC}–Formel ϕ definiertes Funktional F, für das die Funktionalität

∀x_{1}, …, x_{n}∃!x_{0} ϕ(x_{0}, …, x_{n})

in ZFC beweisbar ist.

Lemma 15.1

1. Σ_{1}–Formeln ϕ sind persistent für transitive Mengen: Für Elemente a_{1}, …, a_{n} einer transitiven

Menge m ist

m ⊧ ϕ(a_{1}, …, a_{n}) ⇒ ϕ(a_{1}, …, a_{n}).

2. Δ_{1}^{ZFC}–Formeln sind absolut für transitive Modelle von ZFC.

3. Σ_{1}^{ZFC}-Funktionen F sind absolut für transitive Modelle m von ZFC: Für alle a_{0}, …, a_{n} ∈ m ist

m ⊧ a_{0} =^{.} F (a_{1}, …, a_{n}) ⇔ a_{0} = F (a_{1}, …, a_{n}).

Transitive Modelle sind abgeschlossen unter Σ_{1}^{ZFC}-Funktionen.

Beweis:

1. ist leicht.

2. folgt aus 1.

3. folgt aus der Tatsache, daß die definierende Formel einer Σ_{1}^{ZFC}–Funktion auch Δ_{1}^{ZFC} ist. Wir haben nämlich

ZFC ⊢ (¬ϕ(x_{0}, …, x_{n})) ⟷ ∃y (¬y =^{.} x_{0} ∧ ϕ(y, x_{1}, …, x_{n})).

Aus dem nächsten Lemma folgt, daß die rechte Seite wieder eine Σ_{1}^{ZFC}–Formel ist. □

Lemma 15.2 Σ_{1}^{ZFC}–Formeln sind abgeschlossen unter

1. ∨

2. ∧

3. ∃

4. ∀x ϵ y

5. Einsetzung von Σ_{1}^{ZFC}–Funktionen.

Im folgenden seien ϕ_{i} = ∃x_{0}ψ_{i}(x_{0}, …, x_{n}), i = 1, 2, Σ_{1}–Formeln. Die folgenden Äquivalenzen sind in ZFC beweisbar.

(1)  ϕ_{1} ∨ ϕ_{2} ⟷ ∃x_{0} (ψ_{1} ∨ ψ_{2})
(2)  ϕ_{1} ∧ ϕ_{2} ⟷ ∃y ((∃x_{0} ϵ y ψ_{1}) ∧ (∃x_{0} ϵ y ψ_{2}))
(3)  ∃x_{1} ϕ_{1} ⟷ ∃y∃x_{1} ϵ y∃x_{0} ϵ y ψ_{1}
(4)  ∀x_{1} ϵ y ϕ_{1} ⟷ ∃z∀x_{1} ϵ y∃x_{0} ϵ z ψ_{1}
(5)  ϕ_{1}(F (x_{2}, …, x_{n}), x_{2}, …, x_{n}) ⟷ ∃x_{1}(x_{1} =^{.} F (x_{2}, …, x_{n}) ∧ ϕ_{1})

Rechts stehen Σ_{1}^{ZFC}–Formeln. □

Die folgenden Funktionale sind Σ_{1}^{ZFC}–Funktionen: {x, y}, < x, y >, ⋃ x, x[y], y(x), y ↾ x, x × y, x ∪ y, x ∩ y, x \ y, ω (0-stellig). 𝔓(x) ist der Prototyp eines Funktionals, das nicht Σ_{1}^{ZFC} ist. Das zweistellige Funktional 𝔓(x) ∩ y ist dagegen eine Σ_{1}^{ZFC}–Funktion.

Das nächste Lemma ist die Σ_{1}^{ZFC}–Version von 4.2.

Lemma 15.3 Für jede Σ_{1}^{ZFC}–Funktion G : V × V ⟶ V gibt es eine eindeutig bestimmte Σ_{1}^{ZFC}– Funktion F : V × On ⟶ V, die die Rekursionsgleichung F (x, α) = G(x, F_{x} ↾ α) erfüllt, wobei F_{x} : On ⟶ V definiert ist durch F_{x}(y) = F (x, y).

Beweis:

Es ist

y = F (x, α) ⟺ ∃f(f ist Funktion ∧ ∀β ∈ (α + 1) f(β) = G(x, f ↾ β) ∧ f(α) = y).

Beachte, daß (x ist Funktion) eine Δ_{0}–Formel ist. □

Zum Beispiel ist ⋃^{n} x, definiert durch ⋃^{0} x = {x} und ⋃^{n+1} x = ⋃ ⋃^{n} x, eine Σ_{1}^{ZFC}–Funktion. Also nach dem Beweis von 5.5 auch die transitive Hülle th(x) = ⋃{⋃^{n} x | n ∈ ω}.

Aus dem Lemma folgt, daß die Ordinalzahloperationen +, · und Exponentiation Σ_{1}^{ZFC}–Funktionen sind. In der Struktur < ω, 0, +, ·, <> elementar definierbare Relationen heißen arithmetisch.

Folgerung 15.4 Arithmetische Relationen sind Δ_{1}^{ZFC}.

Satz 15.5 x ↦ Def (x) ist eine Σ_{1}^{ZFC}–Funktion.

Beweis:

Wir beweisen den Satz nur für transitive x. Das genügt für die Konstruktion von L.

Def_{n}(x) sei (für n > 0) die Menge der n–stelligen ohne Parameter definierbaren Relationen auf x. Zum Beispiel sind für i < j < n die Relationen

∈_{n}^{i,j}= {< x_{0}, …, x_{n−1} >∈ x^{n} | x_{i} ∈ x_{j}},
∋_{n}^{i,j}= {< x_{0}, …, x_{n−1} >∈ x^{n} | x_{i} ∋ x_{j}}

und

=_{n}^{i,j}= {< x_{0}, …, x_{n−1} >∈ x^{n} | x_{i} = x_{j}}

aus Def_{n}(x). Weil z.B. alle Tripel Paare sind, sind die verschiedenen Def_{n}(x) nicht disjunkt. Wir setzen daher Def_{∗}(x) = ⋃_{0<n<ω}{n} × Def_{n}(x).

Hilfssatz Def_{∗}(x) ist die kleinste Menge D, mit den folgenden Abschlußeigenschaften. (Es sei D_{n} = {a |< n, a >∈ D} und immer n > 0.)

1. Für alle n ist x^{n} ∈ D_{n}.

2. Für alle i < j < n gehören ∈_{n}^{i,j} und ∋_{n}^{i,j} zu D_{n}.

3. Für alle i < j < n ist =_{n}^{i,j}∈ D_{n}.

4. a, b ∈ D_{n} ⇒ a ∩ b ∈ D_{n}.

5. a, b ∈ D_{n} ⇒ a \ b ∈ D_{n}.

6. a ∈ D_{n+1} ⇒ ∃_{n}a ∈ D_{n}, wobei ∃_{n}a = {< b_{0}, …, b_{n−1} >| ∃b_{n} < b_{0}, …, b_{n} >∈ a}.

Beweis:

Weil Def_{∗}(x) die angegebenen Eigenschaften hat, ist D ⊂ Def_{∗}(x). Für die umgekehrte Inklusion zeigt man durch Induktion über den Aufbau von ϕ, daß jede durch ϕ(x_{0}, …, x_{n−1}) definierte Relation auf x in D_{n} liegt. Wenn ϕ atomar ist, macht man von 2. und 3. Gebrauch. Die dabei zunächst vermißten Relationen ∈_{n}^{i,i}, ∋_{n}^{i,i} und =_{n}^{i,i} sind ∅ = x^{n} \ x^{n} und x^{n}, die wegen 1. und 5. in D_{n} liegen. Wenn ϕ eine Negation oder Konjunktion ist, verwendet man 5. und 4. Wenn ϕ eine Existenzformel ist, folgt die Behauptung aus 6. □(Hilfssatz)

Betrachte die folgenden elf Σ_{1}^{ZFC}-Funktionen:

F_{1}^{x}(u, v) = ∈↾ x^{2}
F_{2}^{x}(u, v) = {< a, b, c >∈ x^{3} | b ∈ c}
F_{3}^{x}(u, v) = ∋↾ x^{2}
F_{4}^{x}(u, v) = {< a, b, c >∈ x^{3} | b ∋ c}
F_{5}^{x}(u, v) = =↾ x^{2}
F_{6}^{x}(u, v) = u ∩ v
F_{7}^{x}(u, v) = u \ v
F_{8}^{x}(u, v) = u × x
F_{9}^{x}(u, v) = {< a, b, c >|< a, c >∈ u, b ∈ x}
F_{10}^{x}(u, v) = {< a, b, c, d >|< a, c, d >∈ u, b ∈ x}
F_{11}^{x}(u, v) = {a | ∃b ∈ x < a, b >∈ u}

Nun sei D(x) die kleinste Menge, die x enthält und unter diesen Funktionen (bei festgehaltenem x) abgeschlossen ist. Dann gilt für alle positiven n

Def_{n}(x) = 𝔓(x^{n}) ∩ D(x). (∗)

Um Def_{n}(x) ⊂ D(x) einzusehen, genügt es zu zeigen, daß das System der D_{n}(x) = 𝔓(x^{n}) ∩ D(x) die sechs Abschlußeigenschaften des letzten Hilfssatzes erfüllt:

1: Wenn wir die Funktion F_{8}^{x} n − 1–mal auf x anwenden, erhalten wir x^{n} ∈ D(x).

2: ∈_{2}^{0,1}= F_{1}^{x}(x, x) und ∈_{3}^{1,2}= F_{2}^{x}(x, x) sind in D(x). Für n ≥ 3 ist F_{10}^{x}(∈_{n}^{n−2,n−1}, x) =∈_{n+1}^{n−1,n}. Also gehören alle ∈_{n}^{n−2,n−1} zu D(x). Weil F_{9}^{x}(∈_{n}^{i,n−1}, x) =∈_{n+1}^{i,n}, sind alle ∈_{n}^{i,n−1} in D(x). Daraus erhalten wir mit k–maliger Anwendung von F_{8}^{x} den allgemeinen Fall: ∈_{n+k}^{i,n−1}. Ebenso zeigt man, daß die ∋_{n}^{i,j} zu D(x) gehören: Man beginnt mit F_{3}^{x} und F_{4}^{x}.

3: Hier argumentiert man wie für 2. aber beginnt mit F_{5}^{x}.

4: D(x) ist abgeschlossen unter F_{6}^{x}.

5: D(x) ist abgeschlossen unter F_{7}^{x}.

6: Wenn a ∈ D_{n+1}(x), ist ∃_{n}a = F_{11}^{x}(a, x) ∈ D_{n}(x).

Die andere Richtung von (∗) folgt sofort aus

(∗∗) {u | ∀n u ∩ x^{n} ∈ Def_{n}(x)} ist abgeschlossen unter den F_{i}^{x}.

(∗∗) ist leicht zu beweisen. Zum Beispiel die Abgeschlossenheit unter F_{1}^{x}: Zu zeigen ist, daß für alle n die Menge

e_{n} = (∈↾ x^{2}) ∩ x^{n}

in Def_{n}(x) liegt. Weil x transitiv ist, läßt sich zum Beispiel < x_{1}, x_{2} >= x_{3} in x definieren und es gilt für a_{i} ∈ x

a_{0} ∈ e_{1} ⇔ x ⊧ ∃x_{0}, x_{1} a_{0} =^{.}< x_{0}, x_{1} > ∧x_{0} ϵ x_{1}
< a_{0}, a_{1} >∈ e_{2} ⇔ x ⊧ a_{0} ϵ a_{1}
< a_{0}, …, a_{n−2}, a_{n−1} >∈ e_{n} ⇔ x ⊧ ∃y y =^{.}< a_{0}, …, a_{n−2} > ∧y ϵ a_{n−1}

Damit ist (∗) bewiesen.

Sei nun u aus Def (x). Dann gibt es Parameter a_{0}, …, a_{n−1} aus x und eine Formel ϕ, sodaß

u = {b ∈ x | x ⊧ ϕ(a_{0}, …, a_{n−1}, b)}.

Sei v die durch ϕ definierte n + 1–stellige Relation auf x. Dann ist u = v_{a}, wobei a =< a_{0}, …, a_{n−1} > und

v_{a} = {b ∈ x |< a, b >∈ v}.

Man sieht leicht, daß v ∈ D(x) und a ∈ ⋃ D(x). Also ist

Def (x) = {v_{a} | v ∈ D(x) ∧ a ∈ ⋃ D(x)}. (∗ ∗ ∗)

(Daß v_{a} immer mit Parametern definierbar ist, folgt aus der einfach zu beweisenden Tatsache, daß alle Elemente von ⋃ D(x) Tupel von Elementen von x sind.)

Setze nun F^{x}(u) = ⋃_{0<i<12} F_{i}^{x}[u × u] und definiere G^{x}(n) rekursiv durch G^{x}(0) = {x} und G^{x}(n + 1) = G^{x}(n) ∪ F^{x}(G^{x}(n)). Dann ist D(x) = G^{x}[ω]. Weil F eine Σ_{1}^{ZFC}–Funktion ist, sind wegen 15.3 auch G und damit auch D(x) Σ_{1}^{ZFC}–Funktionen. Man sieht leicht, daß (v, a) ↦ v_{a} eine Σ_{1}^{ZFC}–Funktion ist. Aus (∗ ∗ ∗) folgt nun die Behauptung des Satzes. □

Folgerung 15.6 Das Funktional α ↦ L_{α} ist eine Σ_{1}^{ZFC}–Funktion.

Beweis:

Das folgt leicht aus 15.5 und 15.3. □

Folgerung 15.7 (Gödel) L ist absolut für transitive Modelle M von ZFC, die alle Ordinalzahlen enthalten: Es ist

L^{M} = L.

Beweis:

Sei M ein transitives Modell von ZFC. Weil M unter der Σ_{1}^{ZFC}–Funktion α ↦ L_{α} abgeschlossen ist, ist L^{M} das Bild von On^{M}. On ist aber ein Δ_{0}–Prädikat, also ist On^{M} = On ∩ M. Wenn M alle Ordinalzahlen enthält, ist daher L^{M} = L. Sonst ist On ∩ M eine Limesordinalzahl α und wir haben L^{M} = L_{α}. □

Folgerung 15.8

L ⊧ V = L

Man überzeugt sich leicht, daß wir in Wirklichkeit bei der Konstruktion von L das Auswahlaxiom nicht verwendet haben. Daraus folgt:

Folgerung 15.9 Wenn ZF konsistent ist, ist auch ZF+V=L konsistent.

Satz 15.10 (Gödel) (Cf [7])

ZFC + V = L ⊢ GCH

Beweis:

Wir beginnen mit einem Lemma.

Lemma 15.11 Für unendliche α ist |L_{α}| = |α|.

Beweis: (Lemma)

Wenn x endlich ist, ist Def (x) = 𝔓(x). Also ist L_{ω} = V_{ω} abzählbar unendlich. Für unendliche x ist |Def (x)| = |x|. Denn |x| ≤ Def (x)|, weil alle a für a ∈ x definierbar sind. Umgekehrt ist

|Def (x)| ≤ |Formeln| ·_{c} |Parametertupel aus x| = ω ·_{c} |x| = |x|.

Es ist also für unendliche α immer |L_{α}| = |L_{α+1}| und für Limeszahlen ist |L_{λ}| = |λ| ·_{c} sup_{α<λ} |L_{α}|. Daraus folgt die Behauptung leicht durch Induktion. □(Lemma)

Wir wählen noch eine Σ_{1}-Formel ϕ(x_{0}, x_{1}) die das Funktional α ↦ L_{α} definiert.

Sei jetzt V=L vorausgesetzt. Dann ist die Aussage

ψ = ∀x∃y, z ϕ(y, z) ∧ x ϵ y

wahr. Wir fixieren eine beliebige Teilmenge a einer unendlichen Kardinalzahl κ. Sei α so groß, daß κ ∪ {a} ⊂ L_{α}. Wegen Satz 14.2 (der ebenso für die L_{α} gilt) können wir α so wählen, daß

L_{α} ⊧ ψ

Wir wenden jetzt den Satz von Löwenheim-Skolem auf die Struktur < L_{α}, ∈↾ L_{α} > und die Teilmenge κ ∪ {a} an:

Satz (Löwenheim-Skolem) Sei 𝔄 eine Struktur mit abzählbarer Sprache und B eine unendliche Teilmenge von A. Dann gibt es eine elementare Unterstruktur C, die B enthält und die gleiche Mächtigkeit wie B hat.

Dabei heißt eine Unterstruktur elementar, wenn sie alle Formeln reflektiert. Sei also jetzt C eine elementare Unterstruktur von L_{α}, die alle β < κ und a enthält und die Mächtigkeit κ hat. Aus der Elementarität folgt

C ⊧ ψ ∧ Extensionalität.

Sei f : C ⟶ D der von 14.1 gelieferte Isomorphismus von C mit einer transitiven Menge D. Weil κ∪{a} transitiv ist, muß (wegen der in 14.1 bewiesenen Eindeutigkeit) f die Identität auf κ∪{a} sein. Wir schließen κ ⊂ D und a ∈ D. Weil ψ auch in D gilt, gibt es y, z ∈ D mit a ∈ y und D ⊧ ϕ(y, z). ϕ ist persistent für D, also ist ϕ(y, z) wahr und y ist ein L_{β} ∈ D. Weil D transitiv ist, ist L_{β} eine Teilmenge von D und hat daher höchstens die Mächtigkeit κ. Weil β ⊂ L_{β}, folgt β < κ^{+}.

Es ergibt sich so, daß jedes a ⊂ κ in einem L_{β} (β < κ^{+}) liegt. Also ist 𝔓(κ) Teilmenge von L_{κ^{+}} und hat nach 15.11 höchstens die Mächtigkeit κ^{+}. □

Übung 15.1 Verwende die Methode des Beweises von Satz 15.5 um zu zeigen, daß BG endlich axiomatisierbar ist.

Satz 15.12

ZF + V = L ⊢ AC

Beweis:

Daß die Menge aller Formeln der Mengenlehre abzählbar ist, läßt sich ohne AC beweisen. Sei also < eine Wohlordnung aller Formeln (natürlich ohne Klassenvariable). Sei x eine Menge, die ∅ enthält und < eine Wohlordnung von x, die mit ∅ beginnt. Die Menge x^{∗} aller unendlichen Folgen von Elementen von x, die fast überall = ∅ sind, trägt eine kanonische Wohlordnung, wie in 4.6 angegeben. Die Menge aller Paare {< ϕ, a >| ϕ Formel, a ∈ x^{∗}} versehen wir mit der lexikographischen Ordnung. Jedes solche Paar definiert eine Menge c aus Def (x) durch

c = {b ∈ x | x ⊧ ϕ(b, a)}.

Damit hat man eine kanonische Wohlordnung von Def (x): Es ist c < c′, wenn c′ durch kein Paar < ϕ′, a′ > definiert werden kann, das kleiner-gleich < ϕ, a > ist.

Jetzt definieren wir rekursiv ein Funktional, daß jeder Ordinalzahl α eine Wohlordnung <_{α} von L_{α} so zuordnet, daß für β < α, < L_{β}, <_{β}> ein Anfangsstück von < L_{α}, <_{α}> ist. Für α = 0, 1 gibt es keine Wahl und für Limeszahlen λ können wir für <_{λ} die Vereinigung der früheren <_{α} nehmen. Beim Nachfolgerschritt nehmen wir an, daß <_{α} schon definiert ist. Wie oben beschrieben, ist damit eine natürliche Wohlordnung < auf L_{α+1} = Def (L_{α}) gegeben, die aber im allgemeinen keine Enderweiterung von <_{α} sein wird. Wir setzen daher

c <_{α+1} c′ ⇔ \{ \begin{matrix}c <_{α} c′ & falls c, c′ ∈ L_{α} \\ c < c′ & falls c, c′ ∉ L_{α} \\ c = c & falls c ∈ L_{α}, c′ ∉ L_{α}. \end{matrix}

Jetzt ist ⋃_{α∈On} <_{α} eine Wohlordnung von L. □

Folgerung 15.13 Wenn ZF konsistent ist, so ist auch ZFC konsistent.

Literatur

[1] Georg Cantor. In Ernst Zermelo, editor, Gesammelte Abhandlungen, Die Grundlehren der Mathematischen Wissenschaften in Einzeldarstellungen. Springer Verlag, Berlin und New York, 1932.

[2] W. Easton. Powers of regular cardinals. Ann. Pure Appl. Logic, 1:139–78, 1970.

[3] Paul Erdös and Richard Rado. A partition calculus in set theory. Bull. Amer. Math. Soc. (N.S.), 62:427–489, 1956.

[4] Géza Fodor. Eine Bemerkung zur Theorie der regressiven Funktionen. Acta Sci. Math. (Szeged), 17:139–142, 1956.

[5] Abraham A. Fraenkel. Zu den Grundlagen der Cantor–Zermeloschen Mengenlehre. Math. Ann., 86:230–237, 1922.

[6] Kurt Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Monatsh. Math., 38:173–198, 1931.

[7] Kurt Gödel. The consistency of the axiom of choice and of the generalized continuum hypothesis. Proc. Nat. Acad. Sci. U.S.A., 24:556–557, 1938.

[8] Denés König. Über eine Schlußweise aus dem Endlichen ins Unendliche. Acta Litt. Acad. Sci. Hung., 3:121–130, 1927.

[9] Julius König. Zum Kontinuumproblem. Math. Ann., 60:177–180, 1905.

[10] Duro Kurepa. Ensembles ordonné et ramifié. Publ. Math. Univ. Belgrade, 4:1–138, 1935.

[11] Andrzej Mostowski. An undecidable arithmetical statement. Fund. Math., 36:143–164, 1949.

[12] Frank P. Ramsey. On a problem of formal logic. Proc. London Math. Soc. (3), 30:264–286, 1930.

[13] Jack H. Silver. On the singular cardinals problem. In Proc. Int. Congr. Math. Vancouver, pages 265–268, 1974.

[14] Robert M. Solovay. Real-valued measurable cardinals. In D. Scott, editor, Axiomatic Set Theory, pages 397–428. Proc. Symp. Pure Math, Amer. Math. Soc., 1971.

[15] Ernst Specker. Sur une problème de Sikorski. Colloq. Math., 2:9–12, 1951.

[16] Ernst Zermelo. Beweis, daß jede Menge wohlgeordnet werden kann. Math. Ann., 59:514–516, 1904.

[17] Ernst Zermelo. Untersuchungen über die Grundlagen der Mengenlehre I. Math. Ann., 65:261–281, 1908.

[18] Max Zorn. A remark on method in transfinite algebra. Bull. Amer. Math. Soc. (N.S.), 41:667–670, 1935.

Index

A ⊂ B, 5 L, 57 L_{α}, 57 A ∩ B, 5 A ∪ B, 5 A \ B, 5 A^{n}, 7 ℵ_{α}, 27 Ā, 5 ⋂ A, 5 aB, 8 Card, 27 cf (α), 29 CON(ϕ), 54 Def ( ), 52 D(R), 7

=^{.}, 4

∃!, 4 ∈-Induktion, 8 ϵ, 4 ∋, 7 F : A ⟶ B, 7 h(x), 40 id_{A}, 7 κ ⟶ (μ)_{ν}^{n}, 39 κ ⌣^{μ}, 29

μ ⌣^{κ} , 29

N(z), 40 ω_{α}, 27 On, 15 otp(ū), 16 𝔓( ), 5 Q ∘ R, 7 R^{−1}, 7 R[A], 7 R ↾ A, 7 rang(x), 21 T^{a}, 42 T_{α}, 40 th(a), 23 T_{(x)}, 40 U_{(a)}, 12 ⋃ A, 5 V, 4 V_{α}, 24 Wb(R), 7 |x|, 25 ≺, 13

absolut, 51 abzählbare Menge, 26 AC, 9 aleph, 27 Allklasse, 4 Anfangsstück, 12, 40 Antikette, 39 Arithmetische Relationen, 59 Aronszajnbaum, 42 Aufzählungsfunktion, 16 Aussonderungsaxiom, 5 Auswahlfunktion, 9

Baum, 40 Schicht, 40 Teilbaum, 40 Zweig, 40

durchgehender, 42 Länge, 40

Bernays-Gödel, 3

Bernstein, Satz von, 25

Bild, 7

Cantor, Satz von, 26

Cantorsche Normalform, 21 Cartesisches Produkt, 7 CH, 27 club, 33

de Morgansche Regel, 5 Definitionsbereich, 7 Diagonaldurchschnitt, 33 Diagonalvereinigung, 34 Differenz, 5 disjunkt, 5 Durchschnitt, 5

Einschränkung, 7 endliche Menge, 26 Erdös–Rado, Satz von, 40 Ersetzungsaxiom, 7 Extensionalität, 3

Familie, 8

fast disjunkt, 37

Filter, 47 Bild von, 47 uniformer, 48 vollständiger, 48

Fodor, Satz von, 34

Formeln Δ_{0}–, 53

Δ_{0}^{ZFC}–, 53
Δ_{1}^{ZFC}–, 58

Σ_{1}–, 58 Σ_{1}^{ZFC}–, 58 beschränkte, 4 persistente, 58

fundiert, 12 Fundierungsaxiom, 8 Fundierungsrang, 21 Funktion, 8

Σ_{1}^{ZFC}–, 58 regressiv, 34

Funktional, 7

GCH, 27 gleichmächtig, 25

Höhe, 40 Hauptfilter, 47

Identität, 7 Isomorphiesatz von Mostowski, 51 Isomorphismus, 12

König, 42 König, Satz von, 31 Kardinalität, 25 Kardinalzahl, 25

Addition, 27 Exponentiation, 27 Limes–, 26 Mahlo–, 45 meßbare, 48 Multiplikation, 27 reguläre, 29 schwach kompakte, 44 stark unerreichbare, 44 starke Limes–, 44 unerreichbare, 44

Klasse abgeschlossene, 26 leere, 4 wohlgeordnete, 12

kofinale Menge, 12 Kofinalität, 29 Kollaps,transitiver, 51 Komplement, 5 Komprehensionsaxiom, 3

naives, 3 konnexe Relation, 15 konservative Erweiterung, 4 Konsistenzstärke, 54 konstruktible Hierarchie, 57 Kontinuumshypothese, 27

verallgemeinerte, 27

Löwenheim-Skolem, Satz von, 62 Leere-Menge-Axiom, 5 Limeselement, 12 Limeszahl, 17

Mächtigkeit, 25 Modell, 51

transitives, 51 Morse-Kelley-Mengenlehre, 4 Mostowski

Isomorphiesatz von, 51

n-Tupel, 6 Nachfolger, 12

eines Zweiges, 40 Nachfolgerkardinalzahl, 26 Nachfolgeroperation, 9 natürliche Zahlen, 22 Normalfunktion, 27

ordinaldefinierbar, 57 Ordinalzahl

Addition, 18

Exponentiation, 18 Multiplikation, 18

Ordinalzahlen Rechengesetze für, 19

Paar

geordnetes, 6 Paarklasse, 6 Paarmengenaxiom, 6 Peanoaxiome, 22 Potenzklasse, 5 Potenzmengenaxiom, 7

Ramsey, Satz von, 39 Rang, 21 Reflexionssatz, 52 Rekursionsgleichung, 12, 18 Rekursionssatz, 18 Relation, 7

inverse, 7 konnexe, 15

Russelsches Paradox, 3

Schubfachprinzip, 39 Solovay, Satz von, 35 Specker, 43 Spiel, 35 stationäre Menge, 34 Stetigkeit, 18, 27

Teilklasse, 5 Teilmenge, 5 transitive Hülle, 23 transitive Menge, 15 transitiver Kollaps, 51

Ultrafilter, 47 meßbarer, 48 normaler, 49 trivialer, 47

Ultrapotenz, 49 unendliche Folge, 23 Unendlichkeitsaxiom, 9

Vereinigung, 5 Vereinigungsmengenaxiom, 6 Verknüpfung, 7 Verzweigung, 40 von Neumann Hierarchie, 24 vorgängerklein, 12

Wertebereich, 7 Wohlordnungen, 12

isomorphe, 12 kürzere, 13 vergleichbare, 13

Wohlordnungssatz, 13

Z, 11 ZC, 11 ZF, 10 ZFC, 9 Zorns Lemma, 14

16 Änderungen

Version 3 (26.3.95) Gunter Geisler gründlich durchgesehene Version Version 4: (5.2.97) Errata (neu) Version 5: (26.7.97) Neu durchgesehen von Hans Scheuermann: Kleine Druckfehler und Ungenauigkeiten wurden verbessert, der Index erweitert. Version 6: (6.2.2000) Geringfügige Verbesserungen in den Abschnitten 4, 5, 6, 7, 8,13, 14, 15 nach einer Fehlerliste von Immanuel Herrman. Version 7: (28.8.2010) Verbesserungen nach einer Durchsicht von Nina Frohn. Korrektur von 15.5. Version 7bis: (30.1.2014) Korrektur von Übung 13.2.