4. Wohlfundierte Relationen
Die tragende Eigenschaft der Induktion und der Rekursion über Wohlordnungen ist die Existenz kleinster Elemente in nichtleeren Teilmengen. Wir wollen nun auf die Linearität und sogar auf die Transitivität der Ordnung verzichten, und einen allgemeinen Strukturbegriff einführen, für den Induktion und Rekursion möglich sind. Ein Beispiel ist uns de facto schon begegnet: Mit Hilfe des Fundierungsaxioms und des Satzes, dass jede nichtleere Klasse ein ∈ -minimales Element besitzt, konnten wir zeigen, dass die von Neumann-Zermelo-Hierarchie das Universum ausschöpft. Die ∈ -Relation ist weder linear noch transitiv, aber sie erlaubt immer noch die Argumentation über ein „minimales Gegenbeispiel“.
Fundierte relationale Klassen
Wir betrachten im Folgenden eine beliebige zweistellige relationale Klasse E auf einer Klasse A. Beispiele sind: E = ∈ und A = V, E = < und A = On, E = ⊲ und A = WO. Jeder Klasse E können wir einen Extensionsbegriff zuordnen:
Definition (E-Extension, extE(x))
Sei E eine relationale Klasse auf A. Wir setzen für x ∈ A:
extE(x) = { y ∈ A | y E x }.
Die Menge extE(x) heißt die E-Extension von x.
Die E-Extension eines x ∈ A kann eine echte Klasse sein. Ist zum Beispiel A = On + On = On × { 0 } ∪ On × { 1 } und E die Summenordnung auf A (d. h. (α, i) E (β, j), falls i < j oder i = j und α < β), so ist extE((0, 1)) = On × { 0 } eine echte Klasse. Diese Situation ist in vielen Fällen hinderlich, da wir nicht über Klassen quantifizieren dürfen. Wir werden sie im Folgenden ausschließen, indem wir fordern, dass die Extensionsoperation immer eine Menge liefert:
Definition (V-relationale Klasse)
Sei E eine relationale Klasse auf A. E heißt V-relational, falls extE(x) ∈ V gilt für alle x ∈ A.
Im Hinblick auf Induktion und Rekursion definieren wir nun:
Definition (fundierte und wohlfundierte relationale Klassen)
Sei E eine relationale Klasse auf A.
(i) | E heißt fundiert, falls jede nichtleere Menge x ⊆ A ein E-minimales Element besitzt, d. h. es gibt ein y ∈ x mit extE(y) ∩ x = ∅. |
(ii) | E heißt wohlfundiert, falls E fundiert und V-relational ist. |
Für die ∈ -Relation auf V ist ext ∈ (y) = y, und damit ist das Fundierungsaxiom gleichwertig zur Aussage, dass ∈ eine fundierte Relation auf V ist. Trivialerweise ist die ∈ -Relation auch wohlfundiert.
Wie für die ∈ -Relation existieren minimale Elemente automatisch auch für nichtleere Klassen. Um dies zu zeigen, brauchen wir wieder einen transitiven extensionalen Abschluss.
Definition (E-transitiv)
Sei E eine V-relationale Klasse auf A. Eine Klasse B ⊆ A heißt E-transitiv, falls für alle x ∈ B gilt, dass extE(x) ⊆ B.
Definition (E-transitiver Abschluss, t. c.E(x))
Sei E eine V-relationale Klasse auf A, und sei x ∈ A. Wir definieren durch Rekursion über n ∈ ω:
x0 = extE(x),
xn + 1 = ⋃y ∈ xn extE(y) für alle n ∈ ω.
Dann heißt t. c.E(x) = ⋃n ∈ ω xn der E-transitive Abschluss von x.
In der Tat ist t. c.E(x) die ⊆-kleinste x umfassende E-transitive Menge. Im Falle E = ∈ ist E-transitiv unser altes transitiv und es gilt t. c. ∈ (x) = t. c.(x), denn dann ist x0 = x und xn + 1 = ⋃y ∈ xn ext ∈ (y) = ⋃y ∈ xn y = ⋃ xn für alle n ∈ ω.
Ist E eine transitive Relation auf A, so ist t. c.E(x) = extE(x) für alle x ∈ A. Die Abschluss-Operation gibt uns eine einfache Möglichkeit, V-relationale Klassen zu transitivieren:
Definition (transitive Erweiterung von V-relationalen Klassen)
Sei E eine V-relationale Klasse auf A. Wir definieren für alle x, y ∈ A:
y E′ x, falls y ∈ t. c.E(x).
Dann heißt E′ die transitive Erweiterung von E.
Offenbar ist E′ eine V-relationale Klasse auf A, und E′ ist transitiv: Aus x E′ y und y E′ z folgt immer x E′ z. Weiter ist E′ die kleinste transitive Oberklasse von E. Wir können E′ auch wie folgt über die Verknüpfung von Relationen darstellen:
E′ = ⋃n ∈ ω En, wobei
E1 = E und En + 1 = E ∘ En = { (x, y) | es gibt ein z mit (x, z) ∈ E und (z, y) ∈ En }
Ist E eine echte Klasse, so sind alle En echte Klassen und obige Rekursion über n ∈ ω ist dann durch unsere Rekursionssätze nicht abgedeckt. Formal korrekt können wir für alle 1 ≤ n ∈ ω uniform (durch eine bestimmte Formel φ(x, y, n)) Klassen En definieren durch:
| En = { (x, y) | | es gibt eine Folge 〈 xi | i ≤ n 〉 mit |
| x0 = x, xn = y und xi E xi + 1 für alle i < n }. |
Dann gilt E1 = E und En + 1 = E ∘ En für alle n ∈ ω, und wir können erneut setzen:
E′ = ⋃n ∈ ω En = { (x, y) | es gibt ein 1 ≤ n < ω mit (x, y) ∈ En }.
Wir werden gleich zeigen, dass die Klasse E′ immer noch fundiert ist. Vorab definieren wir:
Definition (E-minimal und E′-minimale Elemente)
Sei E eine V-relationale Klasse auf A. Weiter sei B eine Teilklasse von A.
(i) | Ein x ∈ B heißt E-minimales Element von B, falls extE(x) ∩ B = ∅. |
(ii) | Ein x ∈ B heißt E′-minimales Element von B, falls clE(x) ∩ B = ∅. |
Offenbar ist ein x ∈ B genau dann ein E′-minimales Element von B, wenn x ein minimales Element von B in der transitiven Erweiterung von E ist. Damit ist die Definition konsistent mit der E′-Notation für die transitive Erweiterung.
Ist z. B. E = { (n, n + 1) | n ∈ ω } und B die Menge der geraden Zahlen, so ist jedes n ∈ B minimal in B. Die transitive Erweiterung E′ ist in diesem Fall die ∈ -Relation auf ω, und 0 ist das eindeutige E′-minimale Element von B.
Wir können nun folgende Verallgemeinerung des Satzes über die Existenz von ∈ -minimalen Elementen in nichtleeren Klassen zeigen:
Satz (Existenz von E′-minimalen Elementen in nichtleeren Klassen)
Sei E wohlfundiert auf A, und sei B ⊆ A eine nichtleere Klasse. Dann besitzt B ein E′-minimales Element.
Beweis
Wir zeigen zunächst, dass B ein E-minimales Element besitzt. Sei hierzu x ∈ B beliebig. Ist x ein E-minimales Element von B, so sind wir fertig. Andernfalls existiert ein E-minimales Element y der nichtleeren Menge t. c.E(x) ∩ B. Dann ist aber y ein E-minimales Element von B.
Um ein E′-minimales Element von B zu finden, setzen wir:
C = B ∪ { a ∈ A | es gibt ein b ∈ B mit b ∈ t. c.E(a) }.
Nach dem bereits Gezeigten existiert ein E-minimales x ∈ C.
Dann gilt:
(+) x ist ein E′-minimales Element von C.
Beweis von (+)
Andernfalls existiert ein z ∈ t. c.E(x) ∩ C. Wegen extE(x) ∩ C = ∅ und
t. c.E(x) = extE(x) ∪ ⋃y ∈ extE(x) t. c.E(y)
existiert also ein y ∈ extE(x) mit z ∈ t. c.E(y). Wegen z ∈ C gilt y ∈ C nach Definition von C. Dann gilt aber y ∈ extE(x) ∩ C = ∅, Widerspruch.
Nun ist aber x ∈ B, denn andernfalls existiert ein b ∈ B mit b ∈ t. c.E(x), und wegen B ⊆ C gilt dann b ∈ t. c.E(x) ∩ C, im Widerspruch zu (+).
Insgesamt ist dann also x ein E′-minimales Element von B ⊆ C.
Korollar (Wohlfundiertheit der transitiven Erweiterung)
Ist E wohlfundiert auf einer Klasse A, so ist auch die transitive Erweiterung E′ von E wohlfundiert auf A.
Der wohlfundierte Teil einer Relation
In jeder V-relationalen Klasse können wir einen größten Teilbereich finden, auf welchem die Relation E wohlfundiert ist:
Satz
Sei E eine V-relationale Klasse auf A, und sei
W = { x ∈ A | E ist wohlfundiert auf t. c.E(x) }.
Dann ist W eine E-transitive Klasse und E ist wohlfundiert auf W.
Weiter ist W die größte Teilklasse von A mit diesen Eigenschaften.
Beweis
W ist E-transitiv:
Sei x ∈ W, und sei y ∈ A mit y E x. Dann ist E wohlfundiert auf t. c.E(x), also auch wohlfundiert auf t. c.E(y) ⊆ t. c.E(x). Also ist y ∈ W.
E ist wohlfundiert auf W:
Sei z eine nichtleere Teilmenge von W, und sei x ∈ z beliebig.
Ist x E-minimal in z, so sind wir fertig. Andernfalls ist t. c.E(x) ∩ z eine nichtleere Teilmenge von t. c.E(x), hat also wegen x ∈ W ein E-minimales Element y. Dieses y ist dann auch ein E-minimales Element von z.
zur Maximalität von W:
Sei W′ eine E-transitive Teilklasse von A, und sei E wohlfundiert auf W′. Sei x ∈ W′ beliebig. Wegen W′ E-transitiv ist dann t. c.E(x) ⊆ W′.
Da E wohlfundiert auf W′ ist, ist E auch wohlfundiert auf t. c.E(x) ⊆ W′. Also ist x ∈ W nach Definition von W.
Wir definieren entsprechend:
Definition (wohlfundierter Teil einer V-relationalen Klasse)
Sei E eine V-relationale Klasse auf A. Dann heißt die Klasse
W = { x ∈ A | E ist wohlfundiert auf t. c.E(x) }
der wohlfundierte Teil von A bzgl. E.
Eine konstruktivere Darstellung des wohlfundierten Teils erhalten wir durch eine zur Vα-Hierarchie analoge Stufenbildung:
Definition (die wohlfundierte Hierarchie)
Sei E eine V-relationale Klasse auf A. Wir definieren rekursiv für α ∈ On:
| A0 | = ∅ |
| Aα + 1 | = { x ∈ A | extE(x) ⊆ Aα } für alle α ∈ On |
| Aλ | = ⋃α < λ Aα für alle Limesordinalzahlen λ |
Dann heißt 〈 Aα | α ∈ On 〉 die wohlfundierte Hierarchie in A bzgl. E.
Ein kleineres technisches Problem dieser Definition ist: Die Aα können echte Klassen sein. Dies ist z. B. für die Klasse A = WO aller Wohlordnungen unter der Anfangsstückrelation E = ⊲ der Fall, denn hier ist A0 = ∅, A1 = { 〈 ∅, ∅ 〉 }, aber A2 = { 〈 { x }, ∅ 〉 | x ∈ V }) ist eine echte Klasse. (Ist dagegen E derart, dass für alle x ∈ A gilt: { y ∈ A | extA(x) = extE(y) } ∈ V, so sind alle Aα Mengen, und wir haben dann keine formalen Komplikationen.)
In diesem Fall ist obige Rekursion nicht formal gerechtfertigt (da unsere Rekursionsfunktionen V-wertig sind). Offiziell definieren wir deswegen die wohlfundierte Hierarchie wie oben zuerst nur für Mengen, und setzen dann für allgemeine V-relationale Klassen E auf A uniform für alle α ∈ On:
| Aα = { x ∈ A | | x ∈ Bα, wobei 〈 Bβ | β ∈ On 〉 die wohlfundierte Hierarchie |
| in der Menge t. c.E(x) ∪ { x } bzgl. E ist }. |
Diese Klassendefinition setzt die Mengendefinition fort, und die Klassen Aα erfüllen wie gewünscht die Rekursionsgleichungen der Mengendefinition.
Die wohlfundierte Hierarchie liefert nun die erwünschte konstruktive Darstellung des fundierten Teils einer V-relationalen Klasse:
Satz (Extension der wohlfundierten Hierarchie)
Sei E eine V-relationale Klasse auf A, und sei W der wohlfundierte Teil von A.
Weiter sei 〈 Aα | α ∈ On 〉 die wohlfundierte Hierarchie in A bzgl. E.
Dann gilt W = ⋃α ∈ On Aα.
Beweis
Sei W′ = ⋃α ∈ On Aα. Dann ist W′ E-transitiv und E ist wohlfundiert auf der Klasse W′. Also ist W′ ⊆ W nach Maximalität von W.
Umgekehrt gilt aber auch W ⊆ W′: Denn andernfalls hat die nichtleere Klasse W − W′ ein E-minimales Element x. Dann ist extE(x) ⊆ W′ nach Minimalität von x. Nach dem Ersetzungsschema gibt es dann ein α mit extE(x) ⊆ Aα, und dann ist x ∈ Aα + 1 ⊆ W′, Widerspruch.
Wir hatten bereits erwähnt, dass wir die Vα-Hierarchie in ZF ohne das Fundierungsaxiom definieren können. Wir setzen dann V* = ⋃α ∈ On Vα. Die Klasse V* ist dann der wohlfundierte Teil des Universums:
Korollar
In ZF − (Fun) gilt: V* ist der wohlfundierte Teil von V unter ∈ , d. h. V* = { x ∈ V | ∈ ist wohlfundiert auf t. c. (x) }.
Mit Hilfe der Hierarchie können wir einen Rangbegriff einführen:
Definition (Rangfunktion für wohlfundierte Relationen, rangE(x))
Sei E wohlfundiert auf A, und sei 〈 Aα | α ∈ On 〉 die zugehörige wohlfundierte Hierarchie. Für alle x ∈ A setzen wir dann:
rangE(x) = „das kleinste α mit extE(x) ⊆ Aα“.
Für alle x ∈ A heißt rangE(x) der E-Rang von x in A.
Für die Rangfunktion gelten viele der Eigenschaften der ∈ -Rangfunktion, z. B. gilt rangE(y) < rangE(x) für alle x ∈ A und alle y ∈ t. c.E(x). Dagegen haben aber alle E-minimalen x ∈ A den E-Rang 0, während nur der leeren Menge der ∈ -Rang 0 zukommt.
Die Rangfunktion liefert einen neuen Beweis für den Satz, dass für jede wohlfundierte Relation E auf einer Klasse A auch der transitive Abschluss E′ von E wohlfundiert ist: Ist nämlich B ⊆ A nichtleer, so sei α = min { rankE(y) | y ∈ B }. Dann ist jedes y ∈ B mit rankE(y) = α ein E′-minimales Element von B.
Wohlfundierte Induktion und Rekursion
Wir können nun leicht induktive Beweise und rekursive Definitionen über wohlfundierte Relationen rechtfertigen. Dabei ist an der Stelle x der Rückgriff auf t. c.E(x) erlaubt, d. h. wir dürfen im Falle der Induktion annehmen, dass eine Eigenschaft bereits für alle y ∈ t. c.E(x) bewiesen ist, und im Falle der Rekursion, dass die Funktion F bereits für alle y ∈ t. c.E(x) definiert ist.
Satz (wohlfundierte Induktion)
Sei E wohlfundiert auf A. Sei φ(x) eine Eigenschaft, sodass für alle x ∈ A gilt:
(+) Gilt φ(y) für alle y ∈ t. c.E(x), so gilt φ(x).
Dann gilt φ(x) für alle x ∈ A.
Beweis
Andernfalls ist B = { x ∈ A | non φ(x) } eine nichtleere Klasse. Sei dann x ein E′-minimales Element von B. Nach Minimalität von x gilt dann φ(y) für alle y ∈ t. c.E(x). Also gilt φ(x) nach (+), im Widerspruch zu x ∈ B.
Satz (wohlfundierte Rekursion)
Sei E wohlfundiert auf A, und sei G(x, y) : V2 → V.
Dann existiert genau eine funktionale Klasse F : A → V mit:
F(x) = G(x, F|t. c.E(x)) für alle x ∈ A.
Im Allgemeinen können wir x nicht aus t. c.E(x) errechnen. Da wir zur Definition von F(x) sicher auch x selbst verwenden möchten, brauchen wir ein zweistelliges G.
Ist E′ der transitive Abschluss von E, so ist E′ wohlfundiert auf A, und die Rekursionsgleichung ist wegen t. c.E(x) = extE′(x) identisch mit F(x) = G(x, F|extE′(x)) für alle x ∈ A. Damit ist jede wohlfundierte Rekursion darstellbar als eine wohlfundierte Rekursion über eine transitive Relation.
Beweis
Der Beweis des Rekursionssatzes für wohlfundierte Relationen verläuft analog zum Beweis des Rekursionssatzes für On. Wir setzen für alle x ∈ A:
F(x) = G(x, f), wobei f : t. c.E(x) → V die eindeutige Funktion ist mit:
(#) Für alle y ∈ t. c.E(x) ist f (y) = G(y, f|t. c.E(y)).
Die Existenz und Eindeutigkeit einer solchen x-Approximationsfunktion wird durch wohlfundierte Induktion über x ∈ A bewiesen. Zum Beweis der Existenz definieren wir mit Hilfe des Ersetzungsschemas eine Funktion f : t. c.E(x) → V durch
f (y) = G(y, fy) für alle y ∈ t. c.E(x),
wobei fy die nach I. V. eindeutig existierende y-Approximationsfunktion ist für alle y ∈ t. c.E(x). Dann ist die Funktion f die eindeutige x-Approximationsfunktion.
Da sich extE(x) aus x und damit F|extE(x) aus x und F|t. c.E(x) errechnet, schließt der Satz die einfacheren Rekursionen ein, bei denen wir nur x und F|extE(x) zur Definition von F(x) heranziehen. Ist in einer solchen einfachen Rekursion speziell E = ∈ |A und A transitiv, so genügt eine einstellige Rekursionsfunktion G, da sich dann auch x aus F|extE(x) errechnet, nämlich als x = dom(F|extE(x)). Wir halten diesen wichtigen Spezialfall explizit fest:
Korollar (Rekursionssatz für transitive Klassen)
Sei A eine transitive Klasse, und sei G : V → V. Dann existiert genau eine funktionale Klasse F : A → V mit
F(x) = G(F|x) für alle x ∈ A.
Wir bemerken noch, dass uns die Methode des Zurückschneidens von Klassen zu Mengen erlaubt, den Induktionssatz für beliebige fundierte Relationen zu zeigen, bei denen die Extension eines Elementes i. A. eine echte Klasse ist:
Satz (fundierte Induktion)
Sei E eine fundierte Relation auf A. Dann gilt:
(i) | Jede nichtleere Teilklasse B von A hat ein E-minimales Element. |
(ii) | Es gilt der Induktionssatz für E. |
Beweis
Der Induktionssatz folgt wie oben aus der Existenz von E-minimalen Elementen in nichtleeren Teilklassen von A. Es genügt also, (i) zu zeigen. Sei hierzu B ⊆ A nichtleer. Ohne Einschränkung ist E ∩ B2 ≠ ∅. Wir setzen:
R = { (y, x) ∈ E ∩ B2 | y hat minimalen ∈ -Rang unter allen z ∈ B mit z E x }.
Dann ist R eine wohlfundierte Relation auf C = dom(R) ∪ rng(R) ⊆ B.
Sei also x ∈ C ≠ ∅ R-minimal. Dann ist x auch ein E-minimales Element von B (denn gibt es ein y ∈ B mit y E x, so gibt es ein y′ ∈ C mit y′ E x).
Der Beweis benutzt zut Definition von F wesentlich das Fundierungsaxiom.
Wir diskutieren nun einige Anwendungen der wohlfundierten Induktion und Rekursion.
Die rekursive Rangfunktion
Die wohlfundierte Rekursion erlaubt uns eine gleichwertige rekursive Fassung des oben bereits eingeführten Rangbegriffs:
Satz (rekursive Darstellung der Rangfunktion)
Sei E wohlfundiert auf A. Dann kann die Rangfunktion rangE : A → On rekursiv für alle x ∈ A definiert werden durch:
(+) rangE(x) = strsupy E x rangE(y) (= supy E x (rangE(y) + 1)).
Beweis
Eine E-Induktion zeigt, dass für alle x ∈ A die Gleichung (+) erfüllt ist.
Übung
Sei E eine V-relationale Klasse auf A. Dann sind äquivalent:
(i) | E ist wohlfundiert. |
(ii) | Es gibt ein F : A → On, sodass für alle x, y ∈ A gilt: x E y gdw f (x) < f (y). |
(iii) | Es gibt genau ein F : A → On, sodass für alle x, y ∈ A gilt:
|
Es ist bemerkenswert, dass (i) eine einfache Aussage des Typs „für alle …“ ist, während (ii) eine einfache Aussage des Typs „es gibt …“ darstellt. Derartige Überlegungen werden bei der Betrachtung von Modellen eine wichtige Rolle spielen.
Übung
Sei E wohlfundiert auf A, und sei E′ die Transitivierung von E. Dann gilt:
rangE(x) = rangE′(x) für alle x ∈ A.
Erbliche Eigenschaften
Mit Hilfe von wohlfundierter Rekursion können wir aus jeder durch E wohlfundierten Klasse A den E-transitiven Anteil herauslösen:
Satz (Erblichkeitssatz)
Sei E wohlfundiert auf A. Dann existiert genau eine Klasse B ⊆ A mit
B = { x ∈ A | extE(x) ⊆ B }.
Beweis
Wir definieren F : A → { 0, 1 } durch wohlfundierte Rekursion für alle x ∈ A durch:
Sei B = { x ∈ A | F(x) = 1 }. Dann gilt für alle x ∈ A:
| x ∈ B | gdw F(x) = 1 gdw F(y) = 1 für alle y E x |
| gdw y ∈ B für alle y E x gdw extE(x) ⊆ B |
Also ist B = { x ∈ A | extE(x) ⊆ B }. Ist nun C eine weitere Teilklasse von A mit C = { x ∈ A | extE(x) ⊆ C }, so zeigt eine wohlfundierte Induktion, dass für alle x ∈ A gilt:
x ∈ B gdw extE(x) ⊆ B gdwI. V. extE(x) ⊆ C gdw x ∈ C.
Also gilt B = C.
Die Klasse B des Satzes ist offenbar E-transitiv, und genauer ist B die größte E-transitive Teilklasse von A. Weiter gilt, wie man leicht zeigt:
B = { x ∈ A | t. c.E(x) ⊆ B }.
Nach dem Fundierungsaxiom ist ∈ wohlfundiert auf V. Damit erhalten wir den folgenden wichtigen Spezialfall:
Korollar (Erblichkeitssatz für ∈ )
Sei A eine Klasse. Dann existiert genau eine Klasse B ⊆ A mit
B = { x ∈ A | x ⊆ B }.
Für jede Eigenschaft φ(x) können wir also eindeutig eine Klasse B definieren durch:
B = { x | φ(x) und x ⊆ B }.
Klassen sind Formeln, und der obige Beweis erlaubt, gegeben φ, die Konstruktion einer Formel ψ mit B = { x | ψ(x) }. Hierzu ist die wohlfundierte Rekursion des Beweises in eine Formel aufzulösen.
Definition (E-erblich in A)
Sei E wohlfundiert auf A. Dann heißt die eindeutige Klasse B mit B = { x ∈ A | extE(x) ⊆ B } die Klasse der E-erblichen Mengen von A.
Statt ∈ -erblich sagen wir kurz auch erblich.
Ein Beispiel für eine Erblichkeits-Definition ist:
Definition (Hκ und H′κ)
Sei κ eine Kardinalzahl. Wir definieren Hκ durch:
Hκ = { x | |x| < κ und x ⊆ Hκ }.
Hκ heißt die Klasse der Mengen, die erblich die Kardinalität < κ haben.
Wir setzen weiter H′κ = { x | |t. c.(x)| < κ }.
Alle Hκ und H′κ sind Mengen, und für viele κ gilt Hκ = H′κ:
Übung
(i) | H′ω = Hω = Vω. |
(ii) | H′κ ⊆ Hκ ⊆ Vκ für alle κ. |
(iii) | H′κ = Hκ für alle regulären κ. |
(iv) | H′κ ⊆ H′μ, Hκ ⊆ Hμ für alle μ ≤ κ. |
(v) | H′μ = ⋃κ < μ H′μ für alle Limeskardinalzahlen μ > ω. |
(vi) | Hℵω ⊃ ⋃n < ω Hℵn. |
(vii) | Für alle x und alle Kardinalzahlen κ gilt: x ∈ H′κ impliziert t. c.(x) ∈ H′κ ; x ∈ Hκ impliziert t. c.(x) ⊆ Hκ. |
(viii) | Für alle x existiert ein κ mit x ∈ Hκ. |
[ Für (vi) betrachten wir z. B. { ℵn | n ∈ ω } ].
Die funktionalen Klassen 〈 Hκ | κ ∈ Kard 〉 und 〈 H′κ | κ ∈ Kard 〉 sind also kumulative Hierarchien, die (mit (AC)) das ganze Universum ausschöpfen. Die Folge der H′κ ist zudem stetig.
In der Literatur werden zuweilen alle Hκ über den transitiven Abschluss definiert und als die Systeme der Mengen bezeichnet, die erblich die Kardinalität < κ haben. Die in der Übung betrachtete Menge M = { ℵn | n ∈ ω } hat aber im eigentlichen Wortsinn erblich die Kardinalität kleiner als ℵω: M selbst ist sogar abzählbar, und steigen wir die ∈ -Relation in M hinab, so finden wir nur Mengen der Kardinalität kleiner als ℵω. Dagegen ist ℵω = t. c.(M), und damit M ∉ H′ℵω.
Eine weitere Erblichkeitseigenschaft werden wir im zweiten Abschnitt in den erblich ordinalzahldefinierbaren Mengen kennen lernen.
Starrheit transitiver Klassen
Wir zeigen, dass wir transitive Klassen nur in trivialer Form bijektiv und strukturerhaltend aufeinander abbilden können:
Satz (Automorphiesatz für transitive Klassen)
Seien B, C transitive Klassen, und sei π : B → C ein ∈ -Isomorphismus, d. h. π ist eine bijektive funktionale Klasse, und für alle x, y ∈ A gilt:
(+) x ∈ y gdw π(x) ∈ π(y).
Dann gilt B = C und π = IdB. Insbesondere ist die Identität der einzige ∈ -Isomorphismus auf einer transitiven Klasse.
Beweis
Wir zeigen durch ∈ -Induktion, dass π(x) = x für alle x ∈ B gilt.
x ⊆ π(x):
Für alle z ∈ x gilt z = π(z) ∈ π(x) nach I. V. und (+).
π(x) ⊆ x:
Sei z′ ∈ π(x) ⊆ C. Dann gibt es ein z ∈ B mit π(z) = z′.
Wegen π(z) = z′ ∈ π(x) ist dann aber z ∈ x nach (+).
Übung
Zeigen Sie den obigen Satz allgemeiner für eine wohlfundierte Relation E auf einer Klasse A, E-transitive Teilklassen B, C von A und einen E-Isomorphismus π : B → C, falls E die folgende Bedingung erfüllt:
(+) Für alle x, y ∈ A gilt: extE(x) = extE(y) impliziert x = y.
Zeigen Sie, dass der Satz ohne die Voraussetzung (+) i. A. nicht gilt.
[ Obiges Argument zeigt in einer E-Induktion, dass extE(x) = extE(π(x)) gilt, und aus (+) folgt dann x = π(x). ]
Die Extensionalitäts-Bedingung (+) wird im folgenden Zwischenabschnitt eine wichtige Rolle spielen.
Der Mostowski-Kollaps
Das wichtigste Beispiel für eine wohlfundierte Rekursion ist vielleicht der transitive Kollaps einer „guten“ wohlfundierten Relation E auf einer Klasse A. Dieser Kollaps transitiviert A und verwandelt dabei E strukturerhaltend in die vertraute ∈ -Relation. Insgesamt ergibt sich dann eine transitive Klasse B und eine bijektive funktionale Klasse π : A → B, sodass für alle x, y ∈ A gilt:
x E y gdw π(x) ∈ π(y).
Die geeigneten „guten“ wohlfundierten Relationen E können wir ermitteln, wenn wir den folgenden allgemeinen Ansatz analysieren:
Definition (transitiver Mostowski-Kollaps)
Sei E eine wohlfundierte Relation auf A. Wir definieren eine funktionale Klasse π : A → V durch wohlfundierte Rekursion durch:
π(x) = { π(y) | y E x } für alle x ∈ A.
Die Klasse π : A → rng(π) heißt der transitive (Mostowski)-Kollaps von E.
Die folgenden Eigenschaften folgen unmittelbar aus der Definition:
(a) | Es gilt π(x) = π″ extE(x) für alle x ∈ A. |
(b) | Ist E die ∈ -Relation, so ist π(x) = π″ x für alle x ∈ A. |
(c) | Für alle x ∈ rng(π) ist x ⊆ rng(π) für alle x ∈ rng(π). Also ist rng(π) in der Tat eine transitive Klasse. |
(d) | Für alle x, y ∈ A gilt: x E y impliziert x ∈ y. |
Alle E-minimalen Elemente werden durch den transitiven Kollaps auf die leere Menge abgebildet, und damit ist π im Allgemeinen nicht injektiv. Weiter gilt dann die Umkehrung der Implikation in (d) nicht. Um diese Umkehrung zu erreichen, brauchen wir eine zusätzliche Bedingung an die Relation E.
Definition (extensionale Relationen)
Sei E eine Relation auf A. E heißt extensional, falls für alle x, y ∈ A gilt:
extE(x) = extE(y) impliziert x = y.
Eine Relation E auf A ist also genau dann extensional, wenn sich je zwei verschiedene Elemente von A durch ihre E-Extension unterscheiden. Diese Bedingung kann man als Extensionalitätsaxiom für E ansehen. Das Extensionalitätsaxiom von ZFC besagt genau, dass die ∈ -Relation extensional auf V ist.
Für extensionale wohlfundierte Relationen gilt nun der folgende wichtige Isomorphiesatz. Er ist sich interessant ist und spielt eine fundamentale Rolle in mengentheoretischen Modellkonstruktionen.
Satz (Mostowski-Isomorphiesatz)
Sei E eine wohlfundierte und extensionale Relation auf A. Dann existiert eine transitive Klasse W und eine funktionale Klasse π : A → W derart, dass 〈 A, E 〉 isomorph zu 〈 W, ∈ 〉 ist, d. h.:
(i) | π : A → W ist bijektiv |
(ii) | für alle x, y ∈ A gilt: x E y gdw π(x) ∈ π(y) |
Beweis
Sei π : A → W der Mostowski-Kollaps von A. Wir zeigen, dass W und π wie gewünscht sind. Dabei wissen wir bereits, dass W transitiv ist, und dass die Implikation von links nach rechts in (ii) gilt.
Wir zeigen zuerst, dass π injektiv ist. Hierzu zeigen wir für alle x ∈ A:
(+) Für alle y ∈ A mit y ≠ x ist π(x) ≠ π(y).
Beweis von (+) durch E-Induktion nach x ∈ A
Sei also y ∈ A mit x ≠ y. Dann ist extE(x) ≠ extE(y).
1. Fall: Es gibt ein a E x mit non(a E y).
Dann ist π(a) ≠ π(b) für alle b E y, da nach I. V. sonst a = b für ein b E y und damit a E y gelten würde. Also ist
π(a) ∉ { π(b) | b E y } = π(y).
Aber π(a) ∈ π(x) wegen a E x. Also π(x) ≠ π(y).
2. Fall: Es gibt ein b E y mit non(b E x).
Analog.
Also ist π injektiv. Damit folgt nun die Rückrichtung von (ii):
(++) Für alle x, y ∈ A gilt: π(x) ∈ π(y) impliziert x E y.
Beweis von (++)
Es gelte also π(x) ∈ π(y) = { π(z) | z E y }. Dann existiert ein z E y mit π(x) = π(z). Dann ist aber x = z nach Injektivität von π, also x E y.
Wir wollen noch zeigen, dass der Mostowski-Kollaps eindeutig bestimmt ist. Sind π1 : A → W und π2 : A → W′ Isomorphismen wie im Satz über den Mostowski-Kollaps, so ist π2 π1−1 : W → W′ ein Isomorphismus zwischen zwei transitiven Klassen. Nach dem Satz über die Starrheit transitiver Klassen gilt also
W = W′ und π2 π1−1 = IdW,
d. h. π1 = π2. Damit haben wir:
Korollar (Eindeutigkeit des transitiven Kollaps)
Die Klasse W und der Isomorphismus π im Mostowski-Isomorphiesatz sind eindeutig bestimmt.
Alternativ kann man diese Eindeutigkeitsaussage auch direkt zeigen:
Übung
Zeigen Sie durch E-Induktion, dass für jeden Isomorphismus σ : A → W′ auf einer transitiven Klasse W′ gilt:
σ(x) = { σ(y) | y E x } für alle x ∈ A.
Folglich ist σ der Mostowski-Kollaps π.
Spezialfälle des Satzes sind Wohlordnungen 〈 M, < 〉 mit Mengen M. Diese Wohlordnungen sind wohlfundiert und weiter extensional, denn für alle x ∈ M gilt ext<(x) = { y ∈ M | y < x } = Mx, d. h. ext<(x) ist das durch x gegebene Anfangsstück von M. Also ist ext<(x) ≠ exty(x) für je zwei verschiedene x, y ∈ M. Ist nun π : M → W der Mostowski-Kollaps, so ist W transitiv und wohlgeordnet durch die ∈ -Relation, also ist W eine Ordinalzahl. Genauer ist W der Ordnungstyp von M, und π der eindeutige ordnungserhaltende Isomorphismus von M nach W. Damit liefert der Mostowski-Kollaps eine weitere Motivation für die Ordinalzahldefinition „transitiv und durch ∈ wohlgeordnet“, und er unterstützt das Prädikat „kanonisch“ für diese Definition.
Man kann sogar die Ordinalzahlen über den Mostowski-Kollaps einführen. Der Eleganz und Ökonomie dieses Zugangs stehen didaktische und historische Argumente entgegen. Die Definition der Ordinalzahlen nach von Neumann und Zermelo lässt sich auch anders gut motivieren, und sie liegt zeitlich deutlich vor dem Mostowski-Kollaps von 1949 und seinen von Gödel benutzten Vorstufen aus den 1930er-Jahren.
Wir betrachten weiter noch den Fall, dass E die auf eine Klasse eingeschränkte Elementrelation ist.
Korollar (transitiver Kollaps für extensionale Klassen, Kompressionssatz)
Sei A eine extensionale Klasse, d. h. ∈ |A ist extensional auf A. Dann existieren eindeutig eine transitive Klasse W und ein ∈ -Isomorphismus π : A → W. Weiter ist π die Identität auf dem transitiven Teil von A.
Beweis
Existenz und Eindeutigkeit folgen aus dem Satz oben für den Fall E = ∈ |A.
Für alle x ∈ A ist ext ∈ |A(x) = x ∩ A und damit gilt:
(+) π(x) = { π(y) | y ∈ x ∩ A } für alle x ∈ A.
Sei B der transitive Teil von A. Wir zeigen durch ∈ -Induktion, dass π(x) = x für alle x ∈ B gilt: Für x ∈ B ist x ⊆ B ⊆ A und nach (+) gilt dann
π(x) = { π(y) | y ∈ x } =I. V. { y | y ∈ x } = x.
Die Menge der geraden Zahlen fällt durch den Mostowski-Kollaps auf die Menge der natürlichen Zahlen zusammen. Eine ähnliche Anschauung gilt allgemein für ∈ -extensionale Mengen und Klassen A. Der Kollaps entfernt die Transitivitätslücken A und komprimiert dadurch die ∈ -Struktur auf A in einer nicht weiter reduzierbaren Weise. Stellen wir uns A als gerichteten Graphen vor, bei dem für alle x, y ∈ A mit x ∈ y ein Pfeil von x nach y führt, so können wir den Mostowski-Kollaps als eine Umbenennung der Ecken x des Graphen ansehen: Wir benennen jede Ecke x mit der Menge der neuen Namen der auf x zeigenden Ecken. Die Extensionalitätsbedingung ist notwendig, damit nicht zwei Ecken den gleichen neuen Namen erhalten. Insgesamt bleibt die alte Pfeilstruktur vollständig erhalten, und die Umbenennung der Knoten ist gerade die Abbildung π.
Das Antifundierungsaxiom
Wir diskutieren im Zusammenhang mit dem Mostowski-Kollaps noch kurz ein Prinzip, das dem Fundierungsaxiom widerspricht, nämlich das so genannte Antifundierungsaxiom von Peter Aczel. Wir betrachten hierzu die definierende Gleichung des Mostowski-Kollaps, also
π(x) = { π(y) | y E x },
auch für nicht wohlfundierte Relationen. Folgende Sprechweisen und Anschauungen sind in diesem Umfeld nützlich:
Definition (dekorierter Graph)
Sei G = 〈 M, E 〉 ein gerichteter Graph, d. h. M ist eine Menge und E ist eine zweistellige Relation auf M. Eine Funktion π : M → V heißt eine Dekoration von G, falls für alle x ∈ M gilt:
π(x) = { π(y) | y E x }.
In diesem Fall heißt dann 〈 M, E, π 〉 ein dekorierter Graph.
Der Mostowski-Isomorphiesatz besagt, dass 〈 M, E 〉 eine eindeutige Dekoration besitzt, falls E eine wohlfundierte Relation auf M ist. Das Antifundierungsaxiom fordert nun die Ausdehnung dieses Ergebnisses auf alle Graphen:
Antifundierungsaxiom (AF)
Jeder Graph besitzt eine eindeutige Dekoration.
Dieses Prinzip widerspricht dem Fundierungsaxiom, wie wir gleich sehen werden. Man kann zeigen, dass die Theorie T = ZF − (Fun) + (AF) konsistent ist relativ zu ZF (indem man in ZF ein Modell von T konstruiert).
Satz
In T = ZF − (Fun) + (AF) gilt: Es existiert genau eine Menge x mit x = { x }.
Insbesondere ist also das Fundierungsaxiom falsch.
Beweis
zur Existenz:
Sei p eine beliebige Menge. Wir setzen:
M = { p } und E = { (p, p) }.
Nach (AF) existiert eine Dekoration π : M → V des Graphen 〈 M, E 〉. Dann gilt wegen { q | q E p } = { p }, dass
π(p) = { π(q) | q E p } = { π(p) }.
Sei also x = π(p). Dann gilt x = { x }.
zur Eindeutigkeit:
Sei x′ eine Menge mit x′ = { x′ }. Sei 〈 M, E, π 〉 wie im Beweis der Existenz. Wir definieren σ : M → V durch σ(p) = x′. Dann gilt:
σ(p) = x′ = { x′ } = { σ(p) } = { σ(q) | q E p }.
Also ist σ eine Dekoration auf 〈 M, E 〉. Nach (AF) ist eine Dekoration eindeutig bestimmt. Also gilt σ = π und damit x′ = σ(p) = π(p) = x.
Die eindeutige Menge x mit x = { x } wurde als „das ultimativ frustrierende Geschenk“ bezeichnet: Stellt man sich x = { x } als Paket vor, so findet man nach Öffnung des Pakets wieder x, also ein Paket. Öffnet man dieses, findet man wieder x, usw. Vielleicht noch frustrierender ist eine Menge y mit y = { y, ∅ }. In diesem Paket findet man wieder das Paket y, und zudem das leere Paket ∅. Ein solches y existiert nach (i) der folgenden Übung.
Übung
In T = ZF − (Fun) + (AF) gilt:
(i) | Es gibt genau ein y mit y = { y, ∅ }. |
(ii) | Es gibt genau ein z mit z = { { z } }. Für dieses z gilt dann z = { z }. |
(iii) | Sind x und y Mengen mit x = { y } und y = { x }, so ist x = y und x = { x }. |
[ zu (i): Dekoriere G = 〈 { p, q }, { (p, p), (q, p) } 〉 für beliebige p ≠ q.
zu (ii): Ist x die eindeutige Menge mit x = { x }, so gilt x = { { x } }. Zum Nachweis der Eindeutigkeit sei G = 〈 { p, q }, { (p, q), (q, p) } 〉 für beliebige p ≠ q. Ist nun z eine Menge mit z = { { z } }, so sind π(p) = z, π(q) = { z } und π′(p) = { z }, π′(q) = z Dekorationen von G, also gilt z = { z } wegen π = π′.
zu (iii): Gilt x = { y } und y = { x }, so ist x = { { x } } und y = { { y } }. ]
Der Leser zeichne einen Punkt p auf ein Papier sowie einen kreisförmigen Pfeil, der von diesem Punkt ausgeht und auf den Punkt selbst zeigt. Die Dekoration dieses Graphen liefert die Menge x = { x }. Fügt man diesem Graphen einen weiteren Punkt q und einen Pfeil von q nach p hinzu, so gelangt man zur eindeutigen Menge y mit y = { y, ∅ } wie in (i) der Übung. Man kann in dieser Weise leicht eine Unzahl weiterer Konstellationen erzeugen. Die so erhaltenden Repräsentationen sind allerdings nicht eindeutig. So führt etwa der Graph im Hinweis zu (ii) der Übung wieder zur eindeutigen Menge x mit x = { x }.