3. Ordinalzahldefinierbare Mengen
In diesem Kapitel arbeiten wir wieder in ZF. Wir möchten ein inneres Modell von ZF mit Hilfe des Begriffs der Ordinalzahldefinierbarkeit konstruieren: Eine Menge soll dem Modell angehören, wenn sie sich durch eine Formel definieren lässt, deren Parameter beliebige Ordinalzahlen sind. Die formale Definition dieser offenbar sehr reichhaltigen Klasse von Mengen ist nicht so ohne Weiteres möglich, da wir die Gültigkeitsrelation des Universums nicht durch eine ∈ -Formel ausdrücken können. Für einzelne Formeln auf der Metaebene können wir problemlos definieren:
Definition (ordinalzahldefinierbar durch eine Formel)
Sei φ(y, p1, …, pn) eine Formel, und sei x eine Menge. Dann heißt x ordinalzahldefinierbar durch φ, falls α1, …, αn ∈ On existieren mit:
x = { y | φ(y, α1, …, αn) }.
Dagegen ist „x ist ordinalzahldefinierbar durch irgendeine Formel“ nicht mehr direkt formalisierbar. Wir werden aber dennoch eine formal korrekte Definition finden, die alles leistet, was wir möchten. Hierzu benötigen wir ein für sich interessantes und an vielen Stellen nützliches Prinzip über die Gültigkeit von Formeln in Hierarchien.
Das Reflexionsprinzip
Satz (Reflexionsprinzip)
Sei φ(x1, …, xn) eine Formel. Dann existiert eine Klasse C ⊆ On mit:
(i) | C ist club in On. |
(ii) | Für alle α ∈ C ist φ absolut für Vα, d. h. für alle x1, …, xn ∈ Vα gilt: φ(x1, …, xn) gdw Vα ⊨ φ(x1, …, xn). |
Wir sagen auch, dass die Stufe Vα die Formel φ in V reflektiert, falls (ii) gilt. Das Reflexionsprinzip besagt dann, dass jede Formel club-oft in der Vα-Hierarchie reflektiert wird.
Beweis
Wir zeigen die Behauptung durch Induktion über den Aufbau von φ. Dabei konstruieren wir explizit eine Formel ψ(α) derart, dass die Ordinalzahlklasse
C = { α ∈ On | ψ(α) }
abgeschlossen und unbeschränkt in den Ordinalzahlen ist und Vα die Formel φ für alle α ∈ C reflektiert.
φ ist atomar :
Wir setzen Cφ = On = { α | α ist Ordinalzahl }.
φ = φ0 ∧ φ1 :
Seien Cφ0 = { α | ψ0(α) } und Cφ1 = { α | ψ1(α) } die konstruierten club-Klassen für φ0 bzw. φ1. Wir setzen Cφ = { α | ψ0(α) ∧ ψ1(α) }.
φ = ¬ φ0:
Sei Cφ0 = { α | ψ0(α) } die konstruierte club-Klasse für φ0. Wir setzen Cφ = Cφ0.
φ = ∃x φ0:
Sei φ0 = φ0(x1, …, xn, x), und sei Cφ0 = { α | ψ0(α) } die konstruierte club-Klasse für φ0. Weiter sei χ(α) die Formel
∀x1, …, xn ∈ Vα. ∃x φ0(x1, …, xn, x) → ∃x ∈ Vα φ0(x1, …, xn, x).
Dann ist D = { α | χ(α) } club in On (!). Wir setzen
Cφ = { α | ψ0(α) ∧ χ(α) }.
Insbesondere wird jedes ZF-Axiom und weiter jede in ZF beweisbare Aussage club-oft reflektiert:
Korollar (Reflexion von Aussagen)
Sei φ eine in ZF beweisbare Aussage. Dann existiert eine club-Klasse C von Ordinalzahlen mit Vα ⊨ φ für alle α ∈ C.
Damit haben wir überraschend einfach bewiesen, dass jede zu ZF äquivalente Axiomatik der ∈ -Sprache aus unendlich vielen Axiomen bestehen muss:
Korollar (ZF ist nicht endlich axiomatisierbar)
ZF ist nicht endlich axiomatisierbar, es sei denn, ZF ist widerspruchsvoll.
Beweis
Annahme, es gibt eine endliche Axiomatisierung φ1, …, φn von ZF, d. h. φ1, …, φn sind in ZF beweisbare Aussagen der ∈ -Sprache derart, dass für jedes Axiom φ von ZF gilt, dass φ0, …, φn ⊢ φ. Sei dann
ψ = φ1 ∧ … ∧ φn.
Dann existiert ein α ∈ On mit Vα ⊨ ψ, und damit ist Vα ein Modell von ZF. Also beweist die Theorie ZF, dass es ein Modell von ZF gibt. Also ist ZF widerspruchsvoll.
Das gleiche Argument zeigt, dass jede Theorie T ⊇ ZF, die endlich axiomatisierbar ist, widerspruchsvoll ist.
Den Rückgriff auf den Gödelschen Unvollständigkeitssatz können wir hier sogar vermeiden:
Übung
Zeigen Sie obigen Satz ohne Verwendung des Gödelschen Unvollständigkeitssatzes.
[ Sei ψ wie im Beweis oben. Sei α ∈ On minimal mit Vα ⊨ ψ. Dann gilt
Vα ⊨ „es gibt ein β ∈ On mit Vβ ⊨ ψ“.
Wegen VβVα = Vβ für alle β < α gibt es also ein β < α mit Vβ ⊨ ψ, Widerspruch. ]
Zuweilen taucht beim Nachdenken über das Reflexionsprinzip die Frage auf, ob es uns nicht gestattet, ein Mengenmodell von ZF zu konstruieren. Die vermeintliche Konstruktion eines Modells verläuft in etwa wie folgt: „Wir listen alle ZF-Axiome auf als φ0, φ1, …, φn, …, und betrachten zugehörige club-Klassen Cn = Cφn ⊆ On von Reflexionspunkten. Dann ist C = ⋂n ∈ ω Cn eine club-Klasse in On, und für alle α ∈ On ist Vα ein Modell aller φn, also ein Modell von ZF.“ Dieses Argument ist in ZF aber nicht formalisierbar. Wir können zu jedem φn effektiv eine Cn definierende Formel angeben, sodass Cn club in On ist und jedes α ∈ Cn die Formel φ reflektiert. Wir können aber die Klassen Cn nicht uniform definieren, d. h. es gibt keine Formel ψ(n, α) mit Cn = { α ∈ On | ψ(n, α) }. Das Reflexionsprinzip schließt wie oben gezeigt die endliche Axiomatisierung von ZF aus. Es zeigt die Existenz von club-vielen Vα-Modellen für jedes endliche Teilsystem von ZF, aber es erlaubt uns keine Konstruktion einer Ordinalzahl α mit Vα ⊨ ZF. Hierzu werden substantiell stärkere Prinzipien gebraucht. Ist zum Beispiel κ eine unerreichbare Kardinalzahl, so ist { α ∈ κ | Vα ⊨ ZF } eine club-Menge in κ.
Das Reflexionsprinzip gilt in vielen Varianten. Obiger Beweis macht von der speziellen Natur der Vα-Hierarchie keinen Gebrauch. Statt der Vα-Hierarchie kann man etwa die Hκ-Hierarchie oder unter V = L auch die Lα-Hierarchie zugrunde legen. Allgemein zeigt der Beweis:
Satz (allgemeines Reflexionsprinzip)
Sei 〈 Wα | α ∈ On 〉 eine ⊆-aufsteigende Folge mit Wλ = ⋃α < λ Wα für alle Limesordinalzahlen λ. Weiter sei W = ⋃α ∈ On Wα. Sei φ(v1, …, vn) eine Formel. Dann existiert eine club-Klasse C ⊆ On derart, dass für alle α ∈ C und alle x1, …, xn ∈ Wα gilt:
W ⊨ φ(x1, …, xn) gdw Wα ⊨ φ(x1, …, xn).
Das Reflexionsschema liefert einen neuen Beweis für die Gültigkeit des Aussonderungsschemas im konstruktiblen Universum:
Übung
Zeigen Sie mit Hilfe des Reflexionsschemas für die Lα-Hierarchie, dass in L das Aussonderungsschema gilt.
[ Sei z = { x ∈ y | L ⊨ φ(x1, …, xn, x) } für eine Formel φ und y, x1, …, xn ∈ L. Es ist zu zeigen, dass y ∈ L. Sei hierzu α ∈ On derart, dass y, x1, …, xn ∈ Lα und Lα die Formel φ reflektiert. Dann ist z definierbar über Lα, also z ∈ Lα + 1 ⊆ L. ]
Da die restlichen Axiome von ZF in L problemlos nachzuweisen sind, erhalten wir einen neuen Beweis dafür, dass L ein inneres Modell von ZF ist.
Wir kehren nun zu unserer ursprünglichen Problemstellung zurück, und arbeiten wieder in ZF.
Ordinalzahldefinierbare Mengen
Das Reflexionsprinzip können wir nun dazu benutzen, um eine Klasse zu definieren, die unseren Erwartungen an den Begriff „ordinalzahldefinierbar“ gerecht wird. Wir definieren (mit Hilfe des Formelbegriffs der Objektebene):
Definition (die Klassen OD und HOD)
Wir setzen:
| OD | = { x | ∃α ∃s ∈ α< ω ∃φ x = { a ∈ Vα | Vα ⊨ φ[ a, s ] } } |
| HOD | = { x ∈ OD | x ⊆ HOD } (= { x ∈ OD | t. c.(x) ⊆ OD }) |
OD heißt die Klasse der ordinalzahldefinierbaren Mengen, und HOD heißt die Klasse der erblich ordinalzahldefinierbaren Mengen.
Dabei steht OD für engl. ordinal definable und HOD für hereditarily ordinal definable.
Mit dem Reflexionsprinzip können wir nun zeigen, dass jede Menge, die mit Hilfe einer Formel und Ordinalzahlparametern definierbar ist, ein Element der Klasse OD ist:
Satz (ordinalzahldefinierbare Mengenkomprehensionen)
Sei φ(x, p1, …, pn) eine Formel. Dann gilt für alle α1, …, αn ∈ On:
{ y | φ(y, α1, …, αn) } ∈ V impliziert { y | φ(y, α1, …, αn) } ∈ OD.
Beweis
Seien α1, …, αn ∈ On derart, dass x = { y | φ(y, α1, …, αn) } ∈ V. Weiter sei α > α1, …, αn derart, dass φ absolut für Vα ist. Schließlich sei φ* die Entsprechung von φ auf der Objektebene. Dann ist
x = { y | Vα ⊨ φ* [ y, α1, …, αn ] } ∈ OD.
Allgemeiner verbleiben wir im Bereich der durch eine Formel ordinalzahldefinierbaren Mengen, wenn wir Parameter aus OD anstelle von ordinalen Parametern zulassen:
Korollar (OD-definierbare Mengenkomprehensionen)
Sei φ(y, p1, …, pn) eine Formel. Dann gilt für alle p1, …, pn ∈ OD:
{ y | φ(y, p1, …, pn) } ∈ V impliziert { y | φ(y, p1, …, pn) } ∈ OD
Beweis
Wir nehmen zur Vereinfachung der Notation an, dass φ nur einen Parameter p ∈ OD enthält. Seien dann α ∈ On, s ∈ α< ω, ψ ∈ Form mit
p = { a ∈ Vα | Vα ⊨ ψ[ a, s ] }.
Sei x = { y | φ(y, p) } ∈ V. Dann gilt
x = { y | ∃z. φ(y, z) ∧ z = { α ∈ Vα | Vα ⊨ ψ[ a, s ] } }.
Also ist x ordinalzahldefinierbar mit Parametern α, s(0), …, s(|s| − 1), und damit ist x ∈ OD nach obigem Satz.
Sei nun umgekehrt φ(x1, …, xn) eine Formel, und seien x ∈ V, α ∈ On und s = 〈 α1, …, αn 〉 ∈ α< ω derart, dass
x = { y ∈ Vα | Vα ⊨ φ*[ a, s ] },
wobei wieder φ* die Entsprechung von φ auf der Objektebene ist. Dann gilt
x = { y | ψ(x, α, α1, …, αn) }
für eine effektiv angebbare Formel ψ der Metaebene. Also ist x ordinalzahldefinierbar durch die Formel ψ.
Wir zeigen nun mit Hilfe unseres Kriteriums für innere Modelle, dass die erblich ordinalzahldefinierbaren Mengen die ZF-Axiome erfüllen:
Satz (das innere Modell HOD)
HOD ist ein inneres Modell von ZF.
Beweis
HOD ist transitiv:
Gilt nach Konstruktion.
HOD ist fast universell:
Wir beobachten zunächst, dass für alle α ∈ On die Menge
Wα = Vα ∩ HOD
ein Element von HOD ist. Wegen Wα ⊆ HOD genügt es hierzu zu zeigen, dass Wα ∈ OD. Aber
Wα = { y | y ∈ Vα ∧ y ∈ HOD }.
Also ist Wα ordinalzahldefinierbar mit Parameter α, sodass Wα ∈ OD. Sei nun x ⊆ HOD, und sei α derart, dass x ⊆ Vα. Dann gilt
x ⊆ Vα ∩ HOD = Wα ∈ HOD.
HOD erfüllt Σ0-Aussonderung:
Sei φ(u, p) eine Σ0-Formel, und seien x, p ∈ HOD. (Wir arbeiten zur Vereinfachung der Notation mit nur einem Parameter.) Da φ eine Σ0-Formel ist, genügt es zu zeigen:
y = { u | u ∈ x ∧ φ(u, p) } ∈ HOD.
Wegen y ⊆ x ⊆ HOD genügt es zudem zu zeigen, dass y ∈ OD. Aber y ist definierbar durch die Parameter x, p ∈ OD. Also ist y ∈ OD nach dem obigen Korollar.
Weiter gilt das Auswahlaxiom in HOD:
Satz (Auswahlaxiom in HOD)
In HOD gilt (AC).
Beweis
Die Elemente von OD sind gegeben durch eine Formelnummer und eine endliche Folge von Ordinalzahlen, bestehend aus einem Hierarchieindex und Ordinalzahlparametern. Die im letzten Kapitel konstruierte Wohlordnung der Klasse ω × On< ω liefert also ein surjektives F : On → OD. Durch durch Ausdünnung und Neuaufzählung erhalten wir ein surjektives G : On → HOD. Wir setzen nun
gα = G|α für alle α ∈ On.
Dann gilt gα ∈ OD für alle α ∈ On, denn gα ist definierbar mit dem Parameter α. Offenbar ist gα ⊆ HOD. Also ist gα ∈ HOD für alle α ∈ On. Ist nun x ∈ HOD beliebig, so existiert ein α mit x ⊆ rng(gα). Wie üblich induziert gα ∈ HOD nun eine Wohlordnung < auf x durch Vergleich der kleinsten gα-Urbilder:
a < b, falls min(gα−1″ { a }) < min(gα−1″ { b }).
Jedes x ist also wohlordenbar in HOD, und damit gilt (AC) in HOD.
Damit haben wir einen von L unabhängigen Beweis der relativen Konsistenz des Auswahlaxioms gefunden. Die Klasse HOD ist wohlordenbar in V, und die Anfangsstücke jeder Wohlordnung von HOD sind Elemente von HOD. Folglich gilt der Wohlordnungssatz in HOD.
Die folgende Übung behandelt eine weitere Möglichkeit, die Klasse OD zu definieren:
Übung
Es gilt:
| OD | = „der Abschluss von { Vα | α ∈ On } unter Gödel-Funktionen“ |
| = ⋃α ∈ On cl({ Vβ | β < α }). |
Analog zu „V = L“ kann man die Axiome „V = OD“ und „V = HOD“ betrachten. Hier gelten die folgenden Äquivalenzen:
Satz (Äquivalenzen zu V = OD)
Die folgenden Aussagen sind äquivalent:
(i) | „V = OD“, d. h. ∀x x ∈ OD. |
(ii) | „V = HOD“, d. h. ∀x x ∈ HOD. |
(iii) | Es existiert ein F : On → V surjektiv. |
(iv) | Es existiert eine definierbare Wohlordnung von V. |
Wie üblich ist die Quantifikation über echte Klassen in (iii) und (iv) effektiv zu lesen. Für (iii) gilt etwa: Gilt V = OD (= HOD), so können wir eine Formel φ(α, x) angeben, sodass F = { (α, x) | φ(α, x) } eine funktionale Klasse von On nach V ist. Weiß man umgekehrt von einer Formel φ(α, x), dass sie eine Surjektion F : On → V definiert, so kann man beweisen, dass V = OD = HOD gilt.
Beweis
(i) ↷ (ii):
Sei x ∈ V. Wegen V = OD ist x ∈ OD und x ⊆ OD. Also ist x ∈ HOD.
(ii) ↷ (iii):
Wie im Beweis oben gewinnen wir aus einer surjektiven Funktion G : On → On × On< ω ein surjektives F : On → HOD.
Gilt V = HOD, so ist F wie gewünscht.
(iii) ↷ (iv):
Wir setzen wieder x < y, falls das kleinste F-Urbild von x kleiner ist als das kleinste F-Urbild von y ist.
(iv) ↷ (i):
Sei 〈 xα | α ∈ On 〉 = { (α, x) | φ(α, x) } eine Wohlordnung von V. Dann gilt für alle α ∈ On:
xα = { y | y ∈ xα } = { y | ∃z. y ∈ z ∧ φ(α, z) }
Also ist xα ordinalzahldefinierbar durch φ mit Parameter α. Damit ist x ∈ OD.
Damit können wir die Aussage „V = HOD“ als starke Form des Wohlordnungssatzes und damit des Auswahlaxioms lesen.
Der Leser wird nun wahrscheinlich eine Diskussion der Absolutheit erwarten und vermuten, dass HOD in HOD konstruiert wieder HOD ergibt. Man kann aber nicht zeigen, dass HODHOD = HOD gilt. Im Allgemeinen ist HODHOD eine echte Teilklasse von HOD, und dann gilt HOD ⊨ V ≠ HOD. Insbesondere kann man also ohne weitere Voraussetzung in HOD keine Wohlordnung des Universums konstruieren, da sonst V = HOD nach dem obigen Charakterisierungssatz in HOD gelten würde. Die Anfangsstücke einer Wohlordnung von HOD sind in HOD, aber die die Wohlordnung definierende Formel liefert i. A. keine Wohlordnung des Universums in HOD. Andererseits gilt natürlich HODL = L und weiter
L ⊨ HODHOD = HOD = L = V.
Die mangelnde Absolutheit macht das innere Modell HOD für gewisse Zwecke unattraktiv. Der folgende Satz, den wir ohne Beweis angeben, zeigt, dass wir das Modell HOD abgesehen von (AC) für keine weiteren relativen Konsistenzresultate nutzen können (siehe [ Roguski 1977 ]):
Satz (Theorie von HOD)
Für alle Aussagen φ sind äquivalent:
(i) | ZF ⊢ φHOD |
(ii) | ZFC ⊢ φ |
Der Leser betrachte noch einmal die Äquivalenz:
ZF ⊢ L ⊨ φ gdw ZF + (V = L) ⊢ φ
Nach dem Satz über HOD gilt dagegen:
ZF ⊢ HOD ⊨ φ gdw ZF + (AC) ⊢ φ
Damit spielt das Auswahlaxiom für das Klassenmodell HOD genau die Rolle, die das Axiom der Konstruierbarkeit (V = L) für das Klassenmodell L spielt.
Die Relativierungen OD(A) und HOD(A)
Wir betrachten noch eine Variante der Ordinalzahldefinierbarkeit, bei der wir zusätzliche Parameter zur Definition zulassen.
Definition (die Klassen OD(A) und HOD(A))
Sei A eine Menge. Wir setzen:
| OD(A) | = { x | ∃α ∃s ∈ α< ω ∃φ ∃t ∈ t. c.(A)< ω | |
| x = { a ∈ Vα | Vα ⊨ φ[ a, s, t, A ] } } | ||
| HOD(A) | = { x ∈ OD(A) | x ⊆ OD(A) } |
Für alle A ist HOD(A) ein inneres Modell von ZF. Weiter gilt A ∈ HOD(A). Dagegen ist HOD(A) im Allgemeinen kein Modell des Auswahlaxioms mehr. Wir werden im fünften Kapitel ein solches Modell HOD(A) angeben.