7. Endliche Mengenlehre
Einer axiomatischen Mengenlehre, die sich nur auf endliche Mengen beschränkt, kommt ein natürliches Interesse zu: Sie ist überschaubar und intuitiv zugänglich wie die reine Zahlentheorie, erlaubt aber eine viel freiere Objektbildung. In der reinen Zahlentheorie müssen wir jedes Objekt, das keine Zahl ist, erst kodieren, z. B. das Zahlenpaar (a, b) durch 2a · 3b. In der endlichen Mengenlehre stehen uns alle endlichen kombinatorischen Objekte unmittelbar zur Verfügung.
Das intendierte Universum V der endlichen Mengenlehre ist das der erblich endlichen Mengen, d. h. wir haben V = Vω = ⋃n ∈ ω Vn im Blick. Diese Anschauung lässt sich auf zwei verschiedene Weisen durch Axiome einfangen. Zum einen können wir ZFC modifizieren. Zum anderen können wir den zahlentheoretischen Charakter von einer endlichen Mengenwelt betonen und entsprechend ein „arithmetisches Induktionsschema“ in das Zentrum der Axiomatik rücken. Wir beschreiben diese beiden Wege und zeigen, dass sie äquivalente Theorien hervorbringen. Die Untersuchung wirft auch ein interessantes Licht auf das Fundierungsaxiom.
Wir wiederholen im Folgenden bewusst einige bereits bekannte Argumente, um eine unabhängige Lektüre zu unterstützen. Die Darstellung wird dadurch nur unwesentlich länger.
Endliche und arithmetische Mengenlehre
Wir beginnen mit einer Modifikation von ZFC. Wir betrachten hierzu:
Endlichkeits-Axiom (Fin)
Jede Menge ist Tarski-endlich.
∀x ∀z ≠ ∅. ∀u ∈ z u ⊆ x → ∃u ∈ z ∀v ∈ z ¬ (u ⊂ v).
Fundierungsschema (FuS)
Für jede Formel φ(v) (mit Parametern) gilt:
∃x φ(x) → ∃x. φ(x) ∧ ∀y ∈ x ¬ φ(y).
Das Fundierungsschema besagt also, dass jede nichtleere Klasse A = { x | φ(x) } ein ∈ -minimales Element besitzt: Es gibt ein x ∈ A mit A ∩ x = ∅. Insbesondere impliziert das Fundierungsschema das Fundierungsaxiom (Fun).
In ZFC genügt das einzelne Axiom (Fun), da wir das Fundierungsschema mit Hilfe des transitiven Abschlusses einer Menge beweisen können (vgl. Kapitel 2). Zur Konstruktion des transitiven Abschlusses wird das Unendlichkeitsaxiom benutzt.
Kontraposition liefert das zu (FuS) rein logisch gleichwertige Schema der Epsilon-Induktion:
Epsilon-Induktion ( ∈ -Ind)
Für jede Formel ψ(v) (mit Parametern) gilt:
(∀x. ∀y ∈ x ψ(y) → ψ(x)) → ∀x ψ(x).
Genauer gilt (ErS) für φ(v) genau dann, wenn ( ∈ -Ind) für ψ(v) = ¬ φ(v) gilt.
Wir definieren nun:
Definition (die endliche Mengenlehre FST)
Die Theorie FST besteht aus den folgenden Axiomen:
(Ext), (LM), (Pa), (Ver), (Pot), (Aus), (Fin), (FuS).
Weiter sei FST− = FST − (FuS). Die Theorie FST heißt die endliche Mengenlehre, und FST− heißt die nicht fundierte endliche Mengenlehre.
Die Abkürzung FST steht für finite set theory.
Es wird sich herausstellen, dass sowohl (AC) als auch das Ersetzungsschema in FST beweisbar sind, und deswegen brauchen wir diese Axiome nicht in die Theorie zu integrieren. Neben den reinen Konsequenzen der Theorie sind auch noch Varianten der „Axiomatisierung durch Modifikation von ZFC“ von Interesse. So kann man etwa die Frage stellen, ob man statt (Fin) einfach die Negierung des Unendlichkeitsaxioms verwenden kann. Wir werden sehen, dass dieser Ansatz eine äquivalente Theorie hervorbringt, wenn man zusätzlich noch das Ersetzungsschema hinzunimmt.
Bevor wir diesen Fragen weiter nachgehen, wollen wir noch den zweiten Weg über ein arithmetisches Induktionsschema diskutieren. Statt der Nachfolgerfunktion S(n) = n + 1 bietet sich in der Mengenlehre die Erweiterung um ein Element an, also die Operation S(x, y) = x ∪ { y }. Für diese Operation können wir ein Induktionsschema formulieren, wie wir es aus der Theorie der natürlichen Zahlen kennen. Dabei taucht allerdings eine Neuerung auf: Da unsere mengentheoretische Nachfolgeroperation zweistellig ist, können wir eine Induktionsvoraussetzung entweder nur für x oder stärker sowohl für x als auch für das zu x hinzugefügte y betrachten. Diese Überlegungen führen zu den folgenden Axiomen. Wir nehmen bei ihrer Formulierung an, dass das Extensionalitätsaxiom gilt, und dass die leere Menge existiert.
Das elementare Existenzaxiom in diesem Kontext ist:
Erweiterungsaxiom (Erw)
Für alle x, y existiert x ∪ { y }. ∀x, y ∃z ∀u. u ∈ z ↔ u ∈ x ∨ u = y.
Aus { x } = ∅ ∪ { x } und { x, y } = { x } ∪ { y } folgt leicht, dass für alle x, y das geordnete Paar (x, y) = { { x }, { x, y } } existiert.
Die beiden Induktionsschemata lauten nun:
Endliches Induktionsschema (Ind−)
Für jede Formel φ(v) (mit Parametern) gilt:
φ(∅) ∧ (∀x, y. φ(x) → φ(x ∪ { y })) → ∀x φ(x).
(Starkes) Induktionsschema (Ind)
Für jede Formel φ(v) (mit Parametern) gilt:
φ(∅) ∧ (∀x, y. φ(x) ∧ φ(y) → φ(x ∪ { y })) → ∀x φ(x).
(Ind) impliziert (Ind−) : Im starken Induktionsschema haben wir die beiden Induktionsvoraussetzungen φ(x) und φ(y) zur Verfügung, um φ(x ∪ { y }) zu zeigen, im endlichen Induktionsschema dagegen nur φ(x). Der Nachweis von φ(x ∪ { y }) ist einfacher mit den beiden Induktionsvoraussetzungen, aber der postulierte Schluss auf die universelle Gültigkeit von φ ist dafür stärker.
Wir definieren nun:
Definition (die arithmetische Mengenlehre AST)
Die Theorie AST besteht aus den Axiomen (Ext), (LM), (Erw), (Ind). Weiter sei AST− = AST − (Ind) + (Ind−). AST heißt die arithmetische Mengenlehre, und AST− heißt die nicht fundierte arithmetische Mengenlehre.
Die Abkürzung AST steht für arithmetical set theory.
Wir zeigen zunächst die Äquivalenz der beiden nicht fundierten Theorien. Wir verwenden dabei die üblichen mengentheoretischen Notationen.
Satz (Äquivalenz von FST− und AST−)
FST− und AST− sind äquivalente Theorien.
Beweis
FST− ⊢ (Ext), (LM), (Erw):
(Ext) und (LM) sind Axiome von FST−. Nach (Pa) und (Ver) existiert für alle x, y die Menge x ∪ { y } = ⋃ { x, { y } }.
FST− ⊢ (Ind−):
Sei φ(v) eine Formel (mit Parametern). Es gelte φ(∅) und für alle x, a mit φ(x) gelte φ(x ∪ { a }). Wir zeigen, dass φ(y) für alle y gilt. Sei y beliebig, und sei z = { x ⊆ y | φ(x) } nach (Pot) und (Aus). Dann ist z ≠ ∅, da ∅ ∈ z. Nach (Fin) gibt es ein ⊆-maximales x ∈ z. Für alle a ∈ y gilt φ(x ∪ { a }) nach Voraussetzung, also ist x ∪ { a } = x nach Maximalität von x, d. h. a ∈ x. Also ist x = y, und folglich gilt φ(y).
AST− ⊢ (Ext), (LM):
Ist trivial.
AST− ⊢ (Pa):
Es gilt { x, y } = (∅ ∪ { x }) ∪ { y }. Also gilt (Pa). Insbesondere existiert also (x, y) = { { x }, { x, y } } für alle x, y.
AST− ⊢ (Ver):
Sei z beliebig. Wir zeigen durch Induktion nach x, dass z ∪ x existiert:
Es gilt z ∪ ∅ = z und z ∪ (x ∪ { y }) = (z ∪ x) ∪ { y } für alle x, y.
Damit zeigen wir nun induktiv, dass ⋃ x für alle x existiert:
Es gilt ⋃ ∅ = ∅ und ⋃(x ∪ { y }) = ⋃x ∪ y für alle x, y.
AST− ⊢ (Pot):
Sei z beliebig. Wir zeigen durch Induktion nach x, dass { u ∪ { z } | u ∈ x } existiert:
Dies ist klar für ∅, und es gilt
{ u ∪ { z } | u ∈ x ∪ { y } } = { u ∪ { z } | u ∈ x } ∪ { y ∪ { z }.
Damit zeigen wir nun induktiv, dass ℘(x) für alle x existiert:
Es gilt ℘(∅) = { ∅ } und
℘(x ∪ { y }) = ℘(x) ∪ { u ∪ { y } | u ∈ ℘(x) }.
AST− ⊢ (Aus):
Wir zeigen induktiv, dass Aφ(x) = { z ∈ x | φ(z) } existiert:
Es gilt Aφ(∅) = ∅ und für alle x, y gilt
Aφ(x ∪ { y }) = Aφ(x) oder Aφ(x ∪ { y }) = Aφ(x) ∪ { y }.
AST− ⊢ (Fin):
Wir zeigen durch Induktion, dass jedes x Tarski-endlich ist:
Dies ist klar für x = ∅. Sei also x Tarski-endlich, und sei y beliebig. Sei z ⊆ ℘(x ∪ { y }) nichtleer. Wir setzen
z′ = { u ∩ x | u ∈ z }.
Dann ist z′ ≠ ∅. Sei u ⊆-maximal in z′. Ist u ∪ { y } ∈ z, so ist u ∪ { y } ⊆-maximal in z. Ist u ∪ { y } ∉ z, so ist u ⊆-maximal in z.
Alternativ können wir (Aus) und (Pot) aus dem Ersetzungsschema gewinnen, das in AST− sehr leicht zu zeigen ist (siehe unten).
Auf der Grundlage des obigen Satzes können wir nun zeigen:
Satz (Äquivalenz von FST und AST)
Die Theorien FST und AST sind äquivalent. Genauer gilt für alle Formeln φ(v) (mit Parametern):
FST− + „( ∈ -Ind) für φ(v)“ ⊢ „(Ind) für φ(v)“
AST− ⊢ „(Ind) für ∀u ∈ v φ(u)“ ↔ „( ∈ -Ind) für φ(v)“
Beweis
FST− + „( ∈ -Ind) für φ(v)“ ⊢ „(Ind) für φ(v)“:
Sei φ(v) eine Formel derart, dass φ(∅) gilt, und dass mit φ(x) und φ(a) stets auch φ(x ∪ { a }) gilt. Wir zeigen φ(y) für alle y durch ∈ -Induktion. Sei also y eine Menge mit φ(a) für alle a ∈ y. Sei wieder
z = { x ⊆ y | φ(x) }.
Nach Voraussetzung ist z ≠ ∅, da ∅ ∈ z. Wegen y Tarski-endlich besitzt z ein ⊆-maximales Element x. Sei a ∈ y beliebig. Dann gilt φ(x) und φ(a), also gilt φ(x ∪ { a }) nach Voraussetzung. Wegen x maximal in z ist x ∪ { a } = x, und damit a ∈ x. Folglich gilt x = y und damit φ(y).
AST− ⊢ „(Ind) für ∀u ∈ v φ(u)“ ↔ „( ∈ -Ind) für φ(v)“:
Die Voraussetzung von (Ind) für die Formel ∀u ∈ v φ(u), also
∀u ∈ ∅ φ(u) ∧ ∀x, y. ∀u ∈ x φ(u) ∧ ∀u ∈ y φ(u) → ∀u ∈ x ∪ { y } φ(u)
ist äquivalent zur Voraussetzung von ( ∈ -Ind) für die Formel φ(v), also
∀y. ∀u ∈ y φ(u) → φ(y).
Weiter sind die beiden zugehörigen Konklusionen ∀y ∀u ∈ y φ(u) und ∀y φ(y) äquivalent, da { y } für alle y existiert.
Etwas grob gesprochen gilt also: Das Fundierungsschema schenkt uns die Induktionsvoraussetzung in der zweiten Komponente − und umgekehrt.
Folgerungen und Modifizierungen der Axiome von FST
Nicht besonders überraschend für eine endliche Welt ist:
Satz (Ersetzungsschema und Auswahlaxiom)
In FST− (oder gleichwertig AST−) sind (Ers) und (AC) beweisbar.
Beweis
AST− ⊢ (Ers):
Wir zeigen induktiv, dass F″x für alle x existiert:
Es gilt F″∅ = ∅ und F″(x ∪ { y }) = F″x ∪ { F(y) } für alle x, y.
AST− ⊢ (AC):
Wir zeigen, dass jede nichtleere Menge von paarweise disjunkten Mengen eine Auswahlmenge besitzt. Dies ist klar für x = ∅. Sei also x ∪ { y } eine Menge von paarweise disjunkten nichtleeren Mengen, und sei z eine Auswahlmenge für x. Wegen y ≠ ∅ gibt es ein a ∈ y. Dann ist z ∪ { a } eine Auswahlmenge für x ∪ { y }.
Alternativ kann man (Ers) und (AC) auch leicht direkt in FST− beweisen. Wir werden gleich zeigen, dass in FST das Auswahlaxiom dann sogar in einer sehr starken Form gilt: Es gibt eine definierbare Wohlordnung des Universums.
Wie üblich definieren wir in FST− die Ordinalzahlen als die Klasse On aller transitiven und durch ∈ wohlgeordneten Mengen. On ist eine echte Klasse und die ∈ -Relation ist eine Wohlordnung auf On. In FST− hat jede Ordinalzahl ungleich 0 einen eindeutigen Vorgänger. Wir schreiben auch Ω statt On und nennen Ω die Klasse der natürlichen Zahlen.
Der Induktionssatz für Ω gilt in FST− als Schema: Ist φ(v) eine Formel derart, dass φ(0) gilt und mit φ(n) stets auch φ(n + 1) gilt, so gilt φ(n) für alle n ∈ Ω. Auch der Rekursionssatz steht zur Verfügung: Ist G : V → V eine funktionale Klasse, so existiert genau eine funktionale Klasse F : Ω → V mit F(n) = G(F|n) für alle n ∈ Ω. Insbesondere ist V* = ⋃n ∈ Ω Vn definiert, wobei V0 = ∅ und Vn + 1 = ℘(Vn) für alle n ∈ Ω. Das Fundierungsschema wird nun wie üblich eingesetzt, um zu zeigen, dass V* = V ist (und aus V = V* folgt umgekehrt (FuS)). Hieraus ergibt sich:
Satz (Wohlordenbarkeit des Universums)
In FST existiert eine Wohlordnung von V: Es gibt eine bijektive funktionale Klasse F : Ω → V.
Beweis
Wir konstruieren F rekursiv: Haben wir ein bijektives F|kn : kn → Vn konstruiert, so ordnen wir Vn + 1 − Vn lexikographisch gemäß F an, d. h. x erscheint vor y, falls das F-kleinste z ∈ x Δ y ein Element von x ist. Die so erhaltene Aufzählung x0, …, xm von Vn + 1 − Vn fügen wir an F|kn an, d. h. wir setzen
F(kn + i) = xi für alle i ≤ m.
Dann ist F|kn + 1 : kn + 1 → Vn + 1 bijektiv, mit kn + 1 = kn + m.
Wir diskutieren schließlich noch die Wahl der Tarski-Endlichkeit als Endlichkeits-Axiom. Es zeigt sich, dass wir hier viele Alternativen haben:
Übung
Über FST− sind äquivalent:
(i) | (Fin) |
(ii) | Jede Menge ist Ω-endlich: Für alle x gibt es ein n ∈ Ω mit |x| = |n|. |
(iii) | Jede Menge ist Dedekind-endlich. |
Weiter können wir auch einfach die Negierung des Unendlichkeitsaxioms zu unserem Endlichkeits-Axiom erheben. Wir müssen dann aber das Ersetzungsschema in die Axiomatik mitaufnehmen:
Satz (Negierung des Unendlichkeitsaxioms)
FST− und FST− − (Fin) + (Ers) + ¬ (Un) sind äquivalente Theorien.
Beweis
FST− ⊢ ¬ (Un) :
Annahme, es gibt ein induktives x0. Sei ω = ⋂ { x ⊆ x0 | x ist induktiv }. Dann ist ω nicht Tarski-endlich, denn ω ⊆ ℘(ω) ist nichtleer und hat kein ⊆-maximales Element, im Widerspruch zu (Fin).
FST− − (Fin) + (Ers) + ¬ (Un) ⊢ (Fin):
Annahme, es gibt eine Tarski-unendliche Menge x. Sei also z ⊆ ℘(x) mit ∅ ∈ z derart, dass z kein ⊆-maximales Element besitzt. Wir definieren:
z* = { y | es gibt ein y′ ∈ z mit y ⊆ y′ und ein n ∈ Ω mit |y| = |n| },
F(y) = „das eindeutige n mit |y| = |n|“ für alle y ∈ z*.
Sei w = F″z* nach (Ers). Dann ist w induktiv, im Widerspruch zu ¬(Un).
Schließlich können wir das Fundierungsschema auch durch zwei einzelne Axiome ersetzen. Wir definieren hierzu:
Transitive Obermengen (Tr)
Für alle x existiert ein transitives y mit x ⊆ y.
Satz (Existenz ∈ -minimaler Elemente in Klassen)
Über FST− sind äquivalent:
(i) | Das Fundierungsschema (FuS) |
(ii) | Die Axiome (Fun) + (Tr) |
Genauer gilt in FST− + (Fun) die transitive ∈ -Induktion:
„Ist u transitiv und ist φ(v) eine Formel mit ∀x. ∀y ∈ x φ(y) → φ(x), so gilt φ(x) für alle x ∈ u.“
Beweis
FST− + (FuS) ⊢ (Fun):
Die Aussage ∀p. ∃x x ∈ p → ∃x. x ∈ p ∧ ∀y ∈ x y ∉ p ist die Instanz des Fundierungsschemas für die Formel φ(v) = „v ∈ p“ mit Parameter p.
FST− + (FuS) ⊢ (Tr):
Gilt (FuS), so existiert für alle x ein Vn mit x ⊆ Vn. (Alternativ definieren wir wie üblich für alle x rekursiv t. c.(x) = x ∪ ⋃y ∈ x t. c.(y).)
FST− + (Fun) + (Tr) ⊢ (FuS):
Es gelte ∀x. ∀y ∈ x φ(y) → φ(x). Sei u transitiv. Annahme,
p = { x ∈ u | ¬φ(x) } ≠ ∅.
Nach (Fun) gibt es ein x ∈ p mit x ∩ p = ∅. Wegen u transitiv ist x ⊆ u, und damit gilt φ(y) für alle y ∈ x. Also gilt φ(x), Widerspruch. Dies zeigt (FuS), falls (Tr) gilt (denn mit u ist auch ℘(u) transitiv).
Das Fundierungsaxiom bewirkt also, dass keine Gegenbeispiele zu induktiven Formeln in transitiven Mengen existieren. Auf der arithmetischen Seite entspricht ihm genau das folgende Prinzip:
Nullinduktion (0-Ind)
∀p. (∅ ∉ p ∧ ∀x, y. x ∉ p ∧ y ∉ p → x ∪ { y } ∉ p) → p = ∅.
Die Nullinduktion ist die Instanz des Induktionsschemas für die Formel v ∉ p (mit p als Parameter).
Satz (Fundierungsaxiom und Nullinduktion)
Die folgenden Theorien sind äquivalent:
(i) | FST− + (Fun) |
(ii) | AST− + (0-Ind) |
Beweis
FST− + (Fun) ⊢ (0-Ind):
Das Fundierungsaxiom ist die Instanz des Fundierungsschemas für die Formel v ∈ p. Damit ist (Fun) äquivalent zur ∈ -Induktion für die Formel v ∉ p, also nach dem obigen Satz zu (Ind) für die Formel v ∉ p.
AST− + (0-Ind) ⊢ (Fun):
Sei z eine Menge mit:
(+) Für alle y ∈ z ist y ∩ z ≠ ∅.
Wir zeigen z = ∅. Hierzu setzen wir:
p = { y ⊆ ⋃ z | y ∩ z ≠ ∅ }.
Nach (+) ist z ⊆ p. Es genügt also, p = ∅ durch Nullinduktion zu zeigen.
Offenbar ist 0 ∉ p. Seien also x ∉ p und y ∉ p. Annahme, x ∪ { y } ∈ p.
Dann gilt x ∪ { y } ⊆ ⋃ z und (x ∪ { y }) ∩ z ≠ ∅. Wegen x ⊆ ⋃ z und x ∉ p ist aber x ∩ z = ∅. Also ist y ∈ z ⊆ p, Widerspruch.
Schließlich halten wir fest, dass die folgenden schwachen Versionen von (Ind), ( ∈ -Ind) und (FuS) gleichwertig sind (ohne Involvierung eines Endlichkeitsaxioms):
| (Ind-2) | φ(∅) ∧ (∀x, y. φ(y) → φ(x ∪ { y })) → ∀x φ(x) |
| ( ∈ -Ind-2) | ∀x (x = ∅ ∨ ∃y ∈ x φ(y) → φ(x)) → ∀x φ(x) |
| (FuS-2) | ∃x φ(x) → ∃x. φ(x) ∧ (x = ∅ ∨ ∃y ∈ x ¬ φ(y)) |
Der Unterschied von (FuS-2) zu (FuS) wird besonders deutlich, wenn wir (FuS) in der folgenden äquivalenten Version schreiben:
| (FuS) | ∃x φ(x) → ∃x. φ(x) ∧ (x = ∅ ∨ ∀y ∈ x ¬ φ(y)) |
Gibt es ein x mit x = { x }, so ist die Formel v = { v } ein Gegenbeispiel zu (FuS-2) und damit auch zu (FuS). Gibt es ein x mit x = { x, ∅ }, so ist v = { v, ∅ } ein Gegenbeispiel zu (FuS), aber keines zu (FuS-2).
Wir notieren schließlich noch eine Axiomatisierung der endlichen Mengenlehre, in der man das Potenzmengenaxiom ableiten kann:
Übung
Zeigen Sie, dass die folgenden Theorien äquivalent sind:
(i) | FST−, also (Ext), (LM), (Pa), (Ver), (Aus), (Pot), (Fin) |
(ii) | (Ext), (LM), (Pa), (Ver), (Ers), „Jede Menge ist Ω-endlich.“ |
[ zur Gewinnung des Potenzmengenaxioms in (ii) ↷ (i): Wir zeigen durch Induktion nach n ∈ Ω, dass ℘(n) existiert. ]
Das Tarski-Fragment
Definition (Tarski-Fragment, TF)
Das Tarski-Fragment TF besteht aus den Axiomen (Ext), (LM) und (Erw).
Im Tarski-Fragment existieren geordnete Paare, und damit stehen uns alle Begriffe im Umfeld von Funktionen zur Verfügung. Es zeigt sich, dass wir den Satz von Cantor-Bernstein in der Klassenversion beweisen können. Wir müssen den im ersten Kapitel gegebenen Beweis nur geringfügig modifizieren:
Satz (Klassenversion des Satzes von Cantor-Bernstein im Tarski-Fragment)
Im Tarski-Fragment gilt:
(a) | Seien A, B, C paarweise disjunkte Klassen, und sei F : A ∪ B ∪ C → A bijektiv. Dann gibt es ein bijektives H : A ∪ B ∪ C → A ∪ B. |
(b) | Seien K, L Klassen, und seien G1 : K → L und G2 : L → K injektiv. Dann gibt es ein bijektives G : K → L. |
Beweis
Es genügt wieder, (a) zu zeigen. Wir setzen:
| B* = { x ∈ A ∪ B | | es gibt ein f ⊆ F, sodass für alle (y, F(y)) ∈ f ∪ { (x, F(x)) }: |
| y ∉ B impliziert y ∈ A und (F−1(y), y) ∈ f }. |
Dann ist B ⊆ B*, wie f = ∅ ⊆ F bezeugt. Weiter gilt:
(#) F″B* = B* − B.
Beweis von (#)
Sei x ∈ B*, und sei f ⊆ F ein Zeuge hierfür. Dann ist f ∪ { (x, F(x)) } ein Zeuge für F(x) ∈ B*. Zudem ist F(x) ∉ B. Also ist F(x) ∈ B* − B.
Sei umgekhert x ∈ B* − B, und sei f ⊆ F ein Zeuge für x ∈ B*. Dann ist f auch ein Zeuge für F−1(x) ∈ B*. Also ist x ∈ F″B*.
Sei C* = (A ∪ C) − B*. Nach (#) ist H = F|C* ∪ IdB* wie gewünscht.
Auf die Beweisbarkeit der Klassenversion von Cantor-Bernstein im Tarski-Fragment hat vermutlich zuerst Rautenberg 1987 hingewiesen.
Arbeiten wir wieder in einer stärkeren Theorie, so ist obige Klasse B* die Klasse derjenigen x, deren Rückwärtsorbit unter F entweder in B endet oder unendlich ist. Damit ist dann also C* und H wie früher definiert.
Den alten Beweis hätten wir gar nicht modifizieren müssen, denn im Tarski-Fragment können wir die natürlichen Zahlen definieren, und weiter sogar die Addition und die Multiplikation auf den natürlichen Zahlen. Wir skizzieren die Definition der natürlichen Zahlen im Tarski-Fragment, und verweisen den Leser auf [ Monk (1976), Kapitel 16 ] für die Konstruktion der Arithmetik.
Im Tarski-Fragment ist an vielen Stellen erhöhte Vorsicht geboten, da vertraute Dinge wie x ∩ y, x ∪ y oder x − y nicht zu existieren brauchen. Letztendlich ergibt sich aber, dass eine leicht verstärkte Version der Formel nat(x), die wir im ersten Kapitel betrachtet hatten, geeignet ist, die natürlichen Zahlen im Tarski-Fragment zu definieren.
An Konstanten, Operationen haben wir in TF zunächst zur Verfügung:
∅, { x }, { x, y }, (x, y), S(x) = x ∪ { x }.
Mengen, die gute Boolesche Operationen zulassen, sind nicht mehr selbstverständlich:
Definition (gute Mengen)
Ein x heißt ∩-gut, falls für alle y ⊆ x und alle z gilt, dass y ∩ z existiert. Analog heißt x −-gut, falls x − y für alle y existiert. Ein x heißt gut (im Booleschen Sinne), falls x ∩-gut und −-gut ist.
Im Falle, dass x ∩ y oder x − y nicht im üblichen Sinne existieren, setzen wir immer x ∩ y = ∅ bzw. x − y = ∅.
Die Güte einer Menge vererbt sich auf ihre Teilmengen und auf alle einelementigen Erweiterungen:
Übung
(i) | Ist x gut und y ⊆ x, so ist auch y gut. |
(ii) | Ist x gut und y beliebig, so ist auch x ∪ { y } gut. |
Wir definieren nun:
Definition (natürliche Zahlen im Tarski-Fragment)
Sei nat*(x) = „x ist gut ∧ nat(x)“, d. h. nat*(x) ist die Formel:
„x ist gut, transitiv, durch ∈ wohlgeordnet, und jedes nichtleere y ⊆ x besitzt ein ∈ -maximales Element“.
Die Klasse Ω* = { x | nat*(x) } heißt die (TF)-Klasse der natürlichen Zahlen.
In einer Mengenlehre, in der Schnitte und Differenzen immer existieren, sind nat(x) und nat*(x) äquivalente Aussagen. Insbesondere ist Ω = Ω* in FST.
Übung
(i) | 0 ∈ Ω* und für alle n gilt: n ∈ Ω* gdw S(n) ∈ Ω*. |
(ii) | Für alle n ∈ Ω* und alle x ∈ n ist x ∈ Ω*. |
Ein Induktionsschema steht nicht zur Verfügung, denn wir können nicht zeigen, dass jede nichtleere Teilklasse A von Ω* ein kleinstes Element hat. Im üblichen Beweis definieren wir für ein beliebiges n ∈ A die Teilmenge { m ∈ n | m ∈ A } = n ∩ A von n, und zeigen, dass das kleinste Element von n ∩ A auch das kleinste Element von a ist. Diese Argumentation scheitert in TF bei der Definition von n ∩ A, die das Aussonderungsschema benötigt.
Endliche Mengenlehre und Zahlentheorie
Zwei sehr wichtige arithmetische Theorien sind die Robinson-Arithmetik Q und die umfassendere Peano-Arithmetik PA. Sie werden in der Sprache
LAr = { +, ·, S, 0 }
formuliert, die aus den zweistelligen Funktionssymbolen + und · (Addition und Multiplikation), dem einstelligen Funktionssymbol S (Nachfolgerfunktion) und einer Konstanten 0 besteht.
Definition (Robinson-Arithmetik Q)
Die Robinson-Arithmetik Q besteht aus den folgenden sieben Axiomen:
| (Q1) | ∀x S(x) ≠ 0, | ||
| (Q2) | ∀x, y. S(x) = S(y) → x = y, | ||
| (Q3) | ∀x. x ≠ 0 → ∃y x = S(y), | ||
| (Q4) | ∀x x + 0 = x, | (Q5) | ∀x, y x + S(y) = S(x + y), |
| (Q6) | ∀x x · 0 = 0, | (Q7) | ∀x, y x · S(y) = (x · y) + x. |
Die Peano-Arithmetik PA erweitert die endliche Axiomatik Q um das Schema der Induktionsaxiome:
Definition (Peano-Arithmetik PA)
Die Peano-Arithmetik PA umfasst alle Axiome von Q. Weiter ist für jede Formel φ(v) (mit Parametern) der Sprache der Arithmetik die folgende Aussage ein Axiom von PA:
(Indφ(v)) φ(0) ∧ ∀x (φ(x) → φ(Sx)) → ∀x φ(x).
Es zeigt sich nun, dass die endliche Mengenlehre und die Peano-Arithmetik äquikonsistent sind: Ist FST widerspruchsfrei, so ist PA widerspruchsfrei und umgekehrt. Stärker sind die beiden Theorien sogar ineinander interpretierbar:
In FST können wir auf Ω die üblichen funktionalen Klassen +Ω, ·Ω, SΩ und die Konstante 0Ω = 0 ∈ Ω definieren. Dann gilt, wie man leicht zeigt:
Satz (Interpretierbarkeit von PA in FST)
In FST sind alle Axiome von PA beweisbar, wenn man die Quantoren auf die Klasse Ω beschränkt und die Zeichen +, ·, S, 0 durch +Ω, ·Ω, SΩ, 0Ω interpretiert.
Für (Q4) lautet die Behauptung des Satzes z. B. einfach, dass in FST die Aussage ∀x ∈ Ω. x +Ω 0Ω = x beweisbar ist.
Mit einer logischen Argumentation, die wir im nächsten Abschnitt diskutieren werden, können wir aus dem Satz folgern: Ein Beweis von 0 = 1 in PA lässt sich effektiv in einen Beweis von 0 = 1 in FST übersetzen.
Umgekehrt kann man in der Peano-Arithmetik via Kodierung über Mengen reden, und dies in einer erstaunlich einfachen Art und Weise, die von Ackermann bereits 1937 entdeckt wurde. Wir schreiben hierzu natürliche Zahlen n (die Objekte der Peano-Arithmetik) in ihrer eindeutigen Dualdarstellung:
n = ∑i ≥ 0 ai(n) 2i mit 0 ≤ ai(n) ≤ 1 für alle i.
Dies ist innerhalb unserer Sprache und Axiomatik möglich: In der Peano-Arithmetik lässt sich die Exponentiation definieren und es lässt sich zeigen, dass jede natürliche Zahl eine eindeutige Dualdarstellung besitzt. Weiter existiert eine „funktionale Klasse“ F mit F(n, i) = ai(n) für alle n, i.
All diese Dinge sind nicht trivial, aber es ist hier nicht der Ort, die Peano-Arithmetik zu entwickeln. Wir nehmen im Folgenden als nachgewiesen an, dass in der Peano-Arithmetik alle elementaren zahlentheoretischen Sätze bewiesen werden können. (De facto sind arithmetische Sätze, die in ZFC, nicht aber in PA beweisbar sind, schwer zu finden.)
Damit können wir nun eine Element-Relation definieren:
Definition (Ackermann-Interpretation der endlichen Mengenlehre in PA)
In PA definieren wir eine zweistellige Relation e durch:
i e n, falls ai(n) = 1 für alle i, n.
Diese Relation simuliert die ∈ -Relation in der durch die Peano-Arithmetik beschriebenen Welt der Zahlen. Alle Axiome der endlichen Mengenlehre sind erfüllt:
Satz (Interpretierbarkeit von AST in PA)
In PA sind alle Axiome von AST (und damit von FST) beweisbar, wenn die ∈ -Relation durch die Relation e interpretiert wird.
Eine Beschränkung der Quantoren wie oben ist hier nicht notwendig. Unter dieser Interpretation ist jede Zahl eine Menge.
Beweis
zu (Ext):
Seien n, m derart, dass für alle i gilt: i e n gdw i e m. Dann stimmen die Dualdarstellungen von n und m überein, also gilt n = m. Die andere Implikation in (Ext) gilt aus rein logischen Gründen.
zu (LM):
Es gilt non(i e 0) für alle i. Also ist die Null die leere Menge bzgl. ∈ .
zu (Erw):
Seien n, i gegeben. Wir setzen:
Dann gilt m = n ∪ { i } unter der e-Interpretation:
Dies ist klar für i e n, da dann m = n und n ∪ { i } = n. Andernfalls gilt für alle j nach Definition von e :
j e m gdw j e n oder j = i.
Also gilt m = n ∪ { i }.
zu (Ind):
Sei φ eine Formel derart, dass φ(0) gilt, und dass mit φ(n) und φ(i) auch stets φ(n ∪ { i }) gilt. (Nach oben ist n ∪ { i } gleich n oder gleich n + 2i.) Wir zeigen in der Peano-Arithmetik, dass für alle n gilt:
(+) Gilt φ(k) für alle k < n, so gilt φ(n).
In der Peano-Arithmetik lässt sich beweisen, dass φ(n) für alle n gelten muss. (Die Verlaufsform der Induktion mit Rückgriff auf alle kleineren Elemente folgt mit etwas Mühe aus dem Induktionsschema von PA.)
Beweis von (+)
φ(0) gilt nach Voraussetzung. Sei also n ≠ 0, und es gelte φ(k) für alle k < n. Sei n = ∑i ≥ 0 ai(n) 2i mit 0 ≤ ai(n) ≤ 1 für alle i. Wegen n ≠ 0 gibt es ein kleinstes i mit ai(n) = 1. Sei dann
m = ∑j ≥ 0, j ≠ i ai(n) 2i.
Dann gilt n = m + 2i. Nach Induktionsvoraussetzung gilt φ(m) und φ(i), da i, m < n. Also gilt φ(m ∪ { i }) nach Voraussetzung an die Formel φ. Aber m ∪ { i } = n, und damit haben wir φ(n) gezeigt.
Der Beweis zeigt, dass die mengentheoretischen natürlichen Zahlen unter der Ackermann-Interpretation die Zahlen
0, 1 = 0 + 21, 3 = 1 + 21, 11 = 3 + 23, 11 + 211, …
sind. Für alle m ist m ∪ { m } = m + 2m der mengentheoretische Nachfolger der Zahl m.
Aus dem Satz folgt wieder: Ein Beweis von 0 = 1 in FST lässt sich effektiv in einen Beweis von 0 = 1 in PA übersetzen. Damit sind FST und PA äquikonsistent.
Analoge Aussagen gelten für das Tarski-Fragment und die Robinson-Arithmetik: In TF können wir Q interpretieren und umgekehrt. Zur Interpretation von Q in TF definiert man die Klasse Ω* wie oben, und führt dann die arithmetischen Operationen ein. Umgekehrt kann man TF in Q durch Kodierung interpretieren. Das Resultat der gegenseitigen Interpretierbarkeit von TF und Q geht auf Tarski zurück. Explizit durchgeführt wurde die Interpretation von Q zuerst in [ Monk 1976 ].
Die endliche Mengenlehre und die Peano-Arithmetik sind also eng miteinander verwandte Theorien, so sehr sich ihre „Charakterzüge“ und ihre Universen
∅ ∪ ℘(∅) ∪ ℘(℘(∅)) ∪ …, und
0, S(0), S(S(0)), …
auch auf den ersten Blick unterscheiden. Wir können die endliche Mengenlehre als eine Version der Arithmetik ansehen, die uns die Kodierung von endlichen kombinatorischen Strukturen erspart und die uns den Komfort und die Eleganz der mengentheoretischen Sprache zur Verfügung stellt. Die Analyse wirft auch ein Licht darauf, „was man in PA alles machen kann“: Alles, was man in ZFC ohne Unendlichkeitsaxiom, aber verstärkt um das Fundierungsschema und das Endlichkeitsaxiom, definieren und beweisen kann.
Das Unendlichkeitsaxiom führt uns von der Welt der Zahlen in die Welt der Mengen. ZFC hat keine arithmetische Struktur mehr. Es gibt aber ein interessantes Axiom, unter dem die riesengroße Welt der unendlichen Mengen als eine arithmetische Welt erscheint: Das Axiom der Konstruierbarkeit. Dieses Axiom werden wir im nun folgenden zweiten Abschnitt ausführlich untersuchen.