Kapitel 8

INHALTSVERZEICHNIS
i
Inhaltsverzeichnis
I
Collegium Logicum
1
Die Aussagenlogik
1.1 Syntax der Aussagenlogik . . . . . . . . . . . . . . . . . . .
1.1.1 Definition der aussagenlogischen Formeln . . . . . . .
1.1.2 Induktion und Rekursion . . . . . . . . . . . . . . . .
1.1.3 Beweis durch Induktion über den Formelaufbau . . . .
1.1.4 Definition durch Rekursion über den Formelaufbau . .
1.2 Semantik der Aussagenlogik . . . . . . . . . . . . . . . . . .
1.2.1 Wahrheitsfunktionen . . . . . . . . . . . . . . . . . .
1.2.2 Interpretation von aussagenlogischen Formeln . . . . .
1.2.3 Definition der wichtigsten semantischen Begriffe . . .
1.2.4 Einige wichtige allgemeingültige Formeln . . . . . . .
1.2.5 Einige wichtige Äquivalenzen . . . . . . . . . . . . .
1.2.6 Boolesche Gesetze . . . . . . . . . . . . . . . . . . .
1.2.7 Einsetzungsregel . . . . . . . . . . . . . . . . . . . .
1.2.8 Ersetzungsregel . . . . . . . . . . . . . . . . . . . . .
1.3 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Entscheidungsverfahren für Boolesche Normalformen
1.3.2 Boolescher Repräsentationssatz . . . . . . . . . . . .
1.3.3 Das Dualitätsprinzip . . . . . . . . . . . . . . . . . .
1.4 Der semantische Folgerungsbegriff: Erfüllbarkeit . . . . . . .
1.4.1 Zusammenhang zwischen Folgerung und Erfüllbarkeit
1.5 Der syntaktische Folgerungsbegriff: Beweisbarkeit . . . . . .
1.5.1 Axiomensysteme und Beweise . . . . . . . . . . . . .
1.5.2 Korrektheit und Vollständigkeit . . . . . . . . . . . .
1.5.3 Einige Axiomensysteme der Aussagenlogik . . . . . .
1.6 Vollständigkeit und Kompaktheit . . . . . . . . . . . . . . . .
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
5
5
6
8
9
10
10
11
12
14
14
15
15
16
17
19
20
21
23
24
25
25
26
27
29
INHALTSVERZEICHNIS
1.6.1
1.6.2
1.6.3
1.6.4
1.6.5
1.6.6
1.6.7
1.6.8
1.6.9
2
3
ii
Verallgemeinerte Expansion . . . . . . . . . . . . . .
Lemma über die Negation . . . . . . . . . . . . . . .
Tautologiesatz . . . . . . . . . . . . . . . . . . . . .
Deduktionstheorem . . . . . . . . . . . . . . . . . . .
Widerspruchsfreiheit und Vollständigkeit von Theorien
Lemma über Beweisbarkeit und Konsistenz . . . . . .
Vervollständigung . . . . . . . . . . . . . . . . . . .
Verallgemeinerter Vollständigkeitssatz . . . . . . . . .
Kompaktheitssatz der Aussagenlogik . . . . . . . . .
Strukturen und formale Sprachen
2.1 Strukturen . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Beispiele . . . . . . . . . . . . . . . . . . . .
2.1.2 Mehrsortige Strukturen . . . . . . . . . . . . .
2.1.3 Symbole für formale Sprachen . . . . . . . . .
2.2 Unterstrukturen und Morphismen . . . . . . . . . . . .
2.2.1 Beispiele . . . . . . . . . . . . . . . . . . . .
2.2.2 Satz über Unterstrukturen . . . . . . . . . . .
2.2.3 Homomorphes Bild, Identifizierung . . . . . .
2.3 Terme einer Sprache . . . . . . . . . . . . . . . . . .
2.3.1 Interpretation von Termen . . . . . . . . . . .
2.3.2 Spracherweiterung durch Namen . . . . . . . .
2.3.3 Erzeugte Unterstrukturen . . . . . . . . . . . .
2.4 Formeln einer Sprache . . . . . . . . . . . . . . . . .
2.4.1 Beweis durch Induktion über den Formelaufbau
2.4.2 Freie und gebundene Variable . . . . . . . . .
2.4.3 Substitution . . . . . . . . . . . . . . . . . . .
Modelle und Theorien
3.1 Das Wahrheitsprädikat: Modelle . . . . . . . . . .
3.1.1 Satz über neue Konstanten . . . . . . . . .
3.2 Axiome und Theorien . . . . . . . . . . . . . . . .
3.3 Der Kompaktheitssatz und einige Folgerungen . . .
3.3.1 Kompaktheitssatz . . . . . . . . . . . . . .
3.3.2 Satz über die Existenz unendlicher Modelle
3.4 Diagramme . . . . . . . . . . . . . . . . . . . . .
3.4.1 Diagrammlemma . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
32
32
33
33
34
35
35
36
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
38
38
39
40
41
43
44
44
45
45
46
47
48
49
50
51
.
.
.
.
.
.
.
.
53
53
55
56
57
57
58
59
59
INHALTSVERZEICHNIS
3.5
4
3.4.2 Universelle Theorien . . . . . . . . . . .
3.4.3 Modellerweiterungssatz von Keisler . . .
3.4.4 Erhaltungssatz für universelle Formeln .
3.4.5 Satz von Łoś-Tarski . . . . . . . . . . .
Einige mathematische Theorien . . . . . . . . .
3.5.1 Ordnungen . . . . . . . . . . . . . . . .
3.5.2 Gruppen- und Körpertheorie . . . . . . .
3.5.3 Axiomatisierbarkeit: Elementare Klassen
3.5.4 Zahlentheorie . . . . . . . . . . . . . . .
3.5.5 Mengenlehre . . . . . . . . . . . . . . .
iii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Gesetze der Prädikatenlogik
4.1 Ein Axiomensystem für die Prädikatenlogik . . . . . . . . . .
4.1.1 Axiomensystem von Shoenfield . . . . . . . . . . . .
4.1.2 Definition eines Beweises . . . . . . . . . . . . . . .
4.2 Der Tautologiesatz . . . . . . . . . . . . . . . . . . . . . . .
4.3 Substitution und universeller Abschluß . . . . . . . . . . . . .
4.3.1 Hintere Generalisierung . . . . . . . . . . . . . . . .
4.3.2 Satz über die Generalisierung . . . . . . . . . . . . .
4.3.3 Substitutionsregel . . . . . . . . . . . . . . . . . . . .
4.3.4 Substitutionssatz . . . . . . . . . . . . . . . . . . . .
4.3.5 Abschlußsatz . . . . . . . . . . . . . . . . . . . . . .
4.4 Ersetzung und Umbenennung, Gleichheit . . . . . . . . . . .
4.4.1 Ersetzungstheorem . . . . . . . . . . . . . . . . . . .
4.4.2 Eigenschaften des Gleichheitsprädikates . . . . . . . .
4.5 Pränexe Normalformen . . . . . . . . . . . . . . . . . . . . .
4.5.1 Umformungen mit der Negation . . . . . . . . . . . .
4.5.2 Umformungen mit Konjunktion und Disjunktion . . .
4.5.3 Umformungen mit der Implikation . . . . . . . . . . .
4.5.4 Das Dualitätsprinzip für die Prädikatenlogik . . . . . .
4.6 Das Deduktionstheorem . . . . . . . . . . . . . . . . . . . . .
4.7 Erweiterungen von Theorien, Widerspruchsfreiheit . . . . . .
4.7.1 Erweiterungen und Expansionen . . . . . . . . . . . .
4.7.2 Satz über rein sprachliche Erweiterungen von Theorien
4.7.3 Widerspruchsfrei/widerspruchsvoll . . . . . . . . . .
4.7.4 Beweisbarkeit und Widerspruchsfreiheit . . . . . . . .
4.8 Termmodelle . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
60
61
62
62
63
63
64
65
66
69
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
70
70
71
72
73
75
76
76
77
77
79
79
79
80
82
82
82
83
85
87
89
89
91
93
94
95
INHALTSVERZEICHNIS
iv
4.8.1 Kanonische Struktur einer Theorie, Termstruktur . . . . .
4.8.2 Satz über Termmodelle . . . . . . . . . . . . . . . . . . .
4.9 Vervollständigung von Theorien . . . . . . . . . . . . . . . . . .
4.9.1 Satz von Lindenbaum . . . . . . . . . . . . . . . . . . .
4.10 Henkin-Theorien . . . . . . . . . . . . . . . . . . . . . . . . . .
4.11 Der Gödelsche Vollständigkeitssatz . . . . . . . . . . . . . . . . .
4.11.1 Vollständigkeit der Prädikatenlogik / Modellexistenz-Satz
4.11.2 Satz von Löwenheim . . . . . . . . . . . . . . . . . . . .
4.11.3 Kompaktheitssatz . . . . . . . . . . . . . . . . . . . . . .
95
96
97
98
99
102
102
104
105
II Mengenlehre
106
5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
107
107
108
111
112
112
114
115
116
117
120
122
124
127
127
130
133
.
.
.
.
.
.
135
135
135
136
137
138
138
6
Grundlagen der Mengenlehre
5.1 Ordinalzahlen . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Ordnungen . . . . . . . . . . . . . . . . . . . . . .
5.1.2 Definition der Ordinalzahlen . . . . . . . . . . . . .
5.1.3 Satz: Charakterisierung von Ordinalzahlen . . . . .
5.1.4 Die Ordnung der Ordinalzahlen . . . . . . . . . . .
5.2 Mengen und Klassen . . . . . . . . . . . . . . . . . . . . .
5.2.1 Komprehensionsaxiom . . . . . . . . . . . . . . . .
5.2.2 Auswege aus den Antinomien . . . . . . . . . . . .
5.2.3 Die mengentheoretische Sprache mit Klassentermen
5.2.4 Überblick über verschiedene Axiomensysteme . . .
5.3 Extensionalität und Aussonderung . . . . . . . . . . . . . .
5.4 Relationen und Funktionen . . . . . . . . . . . . . . . . . .
5.5 Vereinigung und Produkt . . . . . . . . . . . . . . . . . . .
5.5.1 Vereinigung . . . . . . . . . . . . . . . . . . . . . .
5.5.2 Potenzmenge und allgemeines Produkt . . . . . . .
5.6 Überblick über die ZF-Axiome . . . . . . . . . . . . . . . .
Mengen von Mengen von . . .
6.1 Induktion und Rekursion . . . . . . . . . . .
6.1.1 Ordnungen auf Klassen . . . . . . . .
6.1.2 Minimumsprinzip . . . . . . . . . . .
6.1.3 Induktionsprinzip für Wohlordnungen
6.1.4 Segmente . . . . . . . . . . . . . . .
6.1.5 Rekursionssatz für Wohlordnungen .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
INHALTSVERZEICHNIS
6.2
6.3
7
8
III
9
v
6.1.6 Repräsentationssatz für Wohlordnungen . .
6.1.7 Transfinite Rekursion . . . . . . . . . . . .
Die von-Neumannsche Hierarchie . . . . . . . . .
Die Rolle des Unendlichkeitsaxioms . . . . . . . .
6.3.1 PA in mengentheoretischer Sprache . . . .
6.3.2 Die Theorie der endlichen Mengen . . . . .
6.3.3 Anwendungen der numerischen Rekursion
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Das Auswahlaxiom
7.1 Zermelos Axiom . . . . . . . . . . . . . . . . . . . . .
7.1.1 Mengentheoretisch äquivalente Formen . . . . .
7.1.2 Der Zermelosche Wohlordnungssatz . . . . . . .
7.1.3 Maximumsprinzipien von Zorn und Hausdorff .
7.2 Anwendungen des Auswahlaxioms . . . . . . . . . . . .
7.2.1 Jeder Vektorraum besitzt eine Basis. . . . . . . .
7.2.2 Der Satz von Hahn-Banach . . . . . . . . . . . .
7.2.3 Nicht-meßbare Mengen . . . . . . . . . . . . .
7.2.4 Äquivalenz verschiedener Stetigkeitsdefinitionen
7.2.5 Satz von Tychonoff . . . . . . . . . . . . . . . .
7.2.6 Boolesches Primidealtheorem . . . . . . . . . .
Mächtigkeiten und Kardinalzahlen
8.1 Endliche und abzählbare Mengen . . . . . .
8.2 Abzählbare Mengen . . . . . . . . . . . . .
8.3 Überabzählbare Mengen . . . . . . . . . .
8.4 Mächtigkeiten . . . . . . . . . . . . . . . .
8.4.1 Satz von Cantor-Schröder-Bernstein
8.4.2 Vergleichbarkeitssatz von Hartogs .
8.4.3 Satz von Cantor . . . . . . . . . . .
8.5 Kardinalzahlen . . . . . . . . . . . . . . .
8.5.1 Operationen auf den Kardinalzahlen
8.5.2 Satz von Hessenberg . . . . . . . .
8.5.3 Satz von Bernstein . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Grundlagen der Modelltheorie
Hin und her: Vollständigkeit und elementare Äquivalenz
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
141
143
144
145
146
148
148
.
.
.
.
.
.
.
.
.
.
.
151
151
151
152
153
156
156
156
156
158
158
158
.
.
.
.
.
.
.
.
.
.
.
161
161
163
165
165
166
167
167
168
169
170
171
172
173
INHALTSVERZEICHNIS
9.1
9.2
9.3
vi
Elementare Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . 173
Die Theorie der dichten linearen Ordnung . . . . . . . . . . . . . 175
Kategorizität . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
10 Auf und ab: Elementare Substrukturen
10.1 Elementare Substrukturen . . . . . . . . . . . .
10.2 Diagrammlemma (Fortsetzung) . . . . . . . . .
10.3 Kriterium von Tarski . . . . . . . . . . . . . .
10.4 Satz von Löwenheim-Skolem-Tarski (abwärts) .
10.5 Satz von Löwenheim-Skolem-Tarski (aufwärts)
10.6 Test von Vaught . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
180
180
181
181
182
183
184
11 Vereinigungen, Durchschnitte und Ketten
185
11.1 Satz über Ketten von Strukturen . . . . . . . . . . . . . . . . . . 186
11.2 Satz von Chang- Łoś-Szusko . . . . . . . . . . . . . . . . . . . . 188
12 Produkte und Ultraprodukte
12.1 Direktes Produkt . . . . . . . . . . . . . . .
12.2 Filter und Ultrafilter . . . . . . . . . . . . . .
12.3 Ultrafiltersatz, Boolesches Primidealtheorem
12.4 Reduziertes Produkt . . . . . . . . . . . . . .
12.5 Satz von Łoś . . . . . . . . . . . . . . . . .
12.6 Kompaktheitssatz . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
189
190
191
192
192
193
196
13 Modellvollständigkeit
198
13.1 Robinsonscher Test . . . . . . . . . . . . . . . . . . . . . . . . . 200
IV
Unvollständigkeit und Unentscheidbarkeit
14 Berechenbare Funktionen
14.1 Turing-Maschinen . . . . . . . . . . . . . .
14.2 URM-berechenbare Funktionen . . . . . .
14.3 Churchsche These . . . . . . . . . . . . . .
14.4 Aufzählbarkeitssätze . . . . . . . . . . . .
14.5 Primitiv-rekursive Funktionen . . . . . . .
14.6 Rekursive und partiell-rekursive Funktionen
14.7 Partielle Entscheidbarkeit . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
202
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
205
205
207
208
209
209
212
214
INHALTSVERZEICHNIS
vii
15 Definierbarkeit berechenbarer Funktionen
15.1 Eine endlich-axiomatisierbare Teiltheorie von PA
15.2 Arithmetische Formeln . . . . . . . . . . . . . .
15.3 Enderweiterungen . . . . . . . . . . . . . . . . .
15.4 Erhaltungseigenschaften unter Enderweiterungen
15.5 Lemma . . . . . . . . . . . . . . . . . . . . . .
15.6 Gödels Lemma . . . . . . . . . . . . . . . . . .
15.7 Definierbarkeitssatz für rekursive Funktionen . .
15.8 Repräsentierbarkeit . . . . . . . . . . . . . . . .
16 Die Gödelschen Sätze
16.1 Gödel-Nummern . . . . . . . . . . . . . .
16.2 Diagonalisierungslemma . . . . . . . . . .
16.3 Satz von Gödel-Rosser . . . . . . . . . . .
16.4 Erster Gödelscher Unvollständigkeitssatz .
16.5 Kombinatorische Prinzipien . . . . . . . .
16.6 Zweiter Gödelscher Unvollständigkeitssatz
16.7 Wahrheit ist nicht arithmetisch definierbar .
16.8 Unentscheidbarkeit . . . . . . . . . . . . .
17 Literatur
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
215
215
217
218
220
220
222
223
224
.
.
.
.
.
.
.
.
227
227
228
229
230
231
233
234
235
238
161
Kapitel 8
Mächtigkeiten und Kardinalzahlen
8.1 Endliche und abzählbare Mengen
Der Grundbegriff der Theorie der Kardinalzahlen ist die Mächtigkeit einer Menge.
Zunächst definieren wir, wann zwei Mengen gleichmächtig sind:
a ∼ b :↔ ∃ f ( f : a ←→ b)
gleichmächtig
Es gibt verschiedene Möglichkeiten, den Begriff des Endlichen zu erfassen;
da man hierbei auch das Unendliche definiert, ist der Begriff keineswegs trivial,
was sich auch darin zeigt, dass die verschiedenen Definitionen oft erst mit Hilfe des Auswahlaxioms als äquivalent nachgewiesen werden können (s. (iv) des
folgenden Satzes).
1. Der übliche Begriff der endlichen Menge greift auf die natürlichen Zahlen
zurück:
Eine Menge a ist endlich gdw sie mit Hilfe von natürlichen Zahlen bis zu einer
Zahl n abgezählt werden kann. Da nach unserer Festlegung n = {0, 1, . . . , n − 1}
ist, so haben wir eine besonders einfache Definition:
a
a
endlich : ↔ ∃n < ω (a ∼ n),
unendlich : ↔ ¬ a endlich.
Ist a endlich, so ist die natürliche Zahl n mit a ∼ n (die man durch Abzählen
bestimmt) eindeutig festgelegt und gibt die Anzahl der Elemente von a an - für
unendliche Mengen braucht dies aber nicht mehr zu gelten (siehe (i) des folgenden
Satzes)!
8.1. E NDLICHE UND ABZ ÄHLBARE M ENGEN
162
2. Von W HITEHEAD -RUSSELL stammt die folgende Definition, die den Zahlbegriff vermeidet:
Eine Menge u ⊆ P(a) heißt induktive Familie von Teilmengen von a gdw
0/ ∈ u ∧ ∀x ∈ u ∀y ∈ a x ∪ {y} ∈ u,
d.h. u enthält die leere Menge und mit jeder Menge x auch die um ein Element
aus a erweiterte Menge. Definiere:
a endlich :↔ ∀u ⊆ P(a)(u induktive Familie von Teilmengen von a → a ∈ u).
Dieser Begriff ist äquivalent zu obiger Definition.
3. Die natürlichen Zahlen sind gleichmächtig mit einer echten Teilmenge (z. B.
den geraden Zahlen). Diese paradoxe Eigenschaft wählt D EDEKIND gerade zur
Charakterisierung unendlicher Mengen:
a D-unendlich :↔ ∃x ⊂ a (a ∼ x)
Satz
(i) n ∼ m ∧ n, m ∈ ω → n = m, allgemeiner:
α ∼ m ∧ m ∈ ω → α = m, (jedoch: ω ∼ ω + 1 ∼ ω + ω)
(ii) α endlich ↔ α ∈ ω, insbesondere:
∀n ∈ ω (n endlich) ∧ ω unendlich
∀n ∈ ω ¬(n D-unendlich) ∧ ω D-unendlich
(iii) a D-unendlich ↔ ∃x ⊆ a(x ∼ ω)
(iv) a D-unendlich → a unendlich,
a D-unendlich ↔ a unendlich (mit DC !)
Beweis von (iii) (D EDEKIND 1888): Sei a D-unendlich, also
f : a ←→ b ⊂ a für ein f und ein b. Wähle a0 ∈ a − b und setze an+1 = f (an )
(rekursive Definition!).
Es ist dann an 6= am für n 6= m und somit {an | n < ω} eine abzählbar-unendliche
Teilmenge von a.
Ist umgekehrt {an | n < ω} eine abzählbar-unendliche Teilmenge von a, wobei
an 6= am für n 6= m, so definieren wir eine Funktion g : a −→ a durch
163
8.2. A BZ ÄHLBARE M ENGEN
g(x) =
(
an+1 , falls x = an
x,
sonst
Es ist dann g : a ←→ a − {a0 } ⊂ a.
Eine D-unendliche Menge besitzt also eine abzählbar-unendliche Teilmenge;
falls man das Auswahlaxiom (bzw. das Axiom DC) nicht voraussetzt, kann es
unendliche Mengen geben, die keine abzählbar-unendliche Teilmenge enthalten!
Eigenschaften endlicher Mengen
(i) 0/ und {a} sind endlich.
(ii) Sind a und b endlich, so auch a ∪ b, a ∩ b, a − b, a × b, P(a), F[a], a b.
(iii) a endlich ∧ ∀x ∈ a (x endlich) →
S
a endlich,
(iv) a endlich ∧ b ⊆ a → b endlich.
(v) Induktionsprinzip für endliche Mengen:
ϕ(0)
/ ∧ ∀x[x endlich ∧ ϕ(x) → ∀y(ϕ(x ∪ {y}))] → ∀x(x endlich → ϕ(x)).
Diese Eigenschaften beweist man am einfachsten mit Hilfe des Endlichkeitsbegriffes von W HITEHEAD -RUSSELL, zeigt dann, dass unter diesem Begriff alle
natürlichen Zahlen endlich sind und somit beide Endlichkeitsdefinitionen zusammenfallen.
8.2 Abzählbare Mengen
Abzählbare Mengen lassen sich mit Hilfe der natürlichen Zahlen abzählen:
a abzählbar: ←→ a = 0/ ∨ a = {an | n < ω} für eine Folge (an | n < ω).
Damit sind dann auch die endlichen Mengen einbegriffen, da in der Abzählung
Elemente mehrfach aufgezählt werden können. Wir unterscheiden:
1. f : ω a heißt Aufzählung von a (es ist dann a = { f (n) | n < ω}),
2. f : ω ↔ a heißt Aufzählung von a ohne Wiederholungen.
164
8.2. A BZ ÄHLBARE M ENGEN
Eine Aufzählung ohne Wiederholungen (also eine bijektive Abbildung auf die
natürlichen Zahlen) liefert eine abzählbar-unendliche Menge:
a abzählbar-unendlich: ←→ a ∼ ω.
Eigenschaften abzählbarer Mengen
(i) a abzählbar ↔ a endlich ∨ a abzählbar-unendlich ↔ ∃α ≤ ω (a ∼ α),
(ii) Sind a und b abzählbar, so auch
a ∪ b, a ∩ b, a − b, a × b, F[a],
P<ω (a) := {x | x ⊆ a ∧ x endlich},
a<ω := { f | ∃n < ω f : n −→ a}.
(iii) Unter der Voraussetzung des Auswahlaxioms (ACω genügt):
S
a abzählbar ∧ ∀x ∈ a (x abzählbar) → a abzählbar,
(iv) a abzählbar ∧ b ⊆ a → b abzählbar.
Beweis von (i): Sei zunächst a abzählbar, also f : ω a für ein f , wobei wir a
als unendlich voraussetzen können. Zu zeigen ist: a ∼ ω, d. h. a ist auch ohne
Wiederholungen aufzählbar:
Setze a0 = f (0) und definiere (durch Rekursion) an+1 = f (k), wobei k minimal ist
mit f (k) 6= ai für alle i < n + 1. (Da a unendlich ist, muß ein solches k existieren.)
Es ist dann n 7→ an eine Bijektion von ω auf a.
Umgekehrt sind offenbar endliche wie auch abzählbar-unendliche Mengen
abzählbar.
Wir zeigen wir nun (iii), wobei wir annehmen können, daß die betrachteten
Mengen nicht-leer sind: Dazu geben wir zunächst eine Paarfunktion an:
f : ω × ω ←→ ω,
f (n, m) = 2n · (2m + 1) − 1.
Sei nun a = {an | n < ω} abzählbar und ∀n ∈ ω (an abzählbar), also
∀n ∈ ω ∃g(g : ω an ).
Nach ACω existiert eine Folge (gn )n∈ω mit ∀n ∈ ω an = {gn (m) |∈ ω}, und somit
[
a=
[
an = {gn (m) | m, n ∈ ω} = {g(n, m) | m, n ∈ ω},
n∈ω
wobei g : ω × ω S
n∈ω an
definiert ist durch g(n, m) = gn (m).
165
8.3. Ü BERABZ ÄHLBARE M ENGEN
S
Die gewünschte Abbildung h : ω n∈ω an erhält man nun aus g durch Vorschalten der Inversen f −1 der oben definierten Paarfunktion f .
(ii) beweist man ähnlich, wobei man sich leicht überzeugt, daß man in diesem
Fall das abzählbare Auswahlaxiom nicht benötigt.
8.3 Überabzählbare Mengen
Während die Potenzmenge einer endlichen Menge auch wieder endlich ist, ist die
Potenzmenge einer abzählbar-unendlichenen Menge nicht mehr abzählbar, also
überabzählbar: Wäre
P(ω) = {an | n ∈ ω},
so wäre auch
a := {m ∈ ω | m 6∈ am } = an für ein n, dann aber
n ∈ an ↔ n 6∈ an
Widerspruch!
Wir erhalten also einen Widerspruch wie im Falle der RUSSELLschen Antinomie! In ähnlicher Weise kann man zeigen, daß die Menge aller zahlentheoretischen Funktionen und auch die Menge aller reellen Zahlen R überabzählbar sind.
8.4 Mächtigkeiten
Obwohl wir die Mächtigkeit einer Menge noch nicht erklärt haben, konnten wir
Mengen als gleichmächtig definieren, wenn sie sich eineindeutig aufeinander abbilden lassen. Ebenso lassen sich Mengen hinsichtlich ihrer Größe vergleichen,
ohne sie vorher aufzählen zu müssen:
a ∼ b: ↔ ∃ f ( f : a ←→ b)
a 4 b: ↔ ∃ f ( f : a b)
↔ ∃x ⊆ b (a ∼ x)
a ≺ b: ↔ a 4 b ∧ a 6∼ b
a ist gleichmächtig mit b
a ist kleiner oder gleichmächtig mit b
(a ist schmächtiger als b)
a ist kleiner als b
(Genauer sollte man für a 4 b sagen: a ist von Mächtigkeit kleiner oder gleich b.)
So ist z.B.
n 4 ω, n ≺ ω, ω 4 ω + 1, ω + 1 4 ω, ω ≺ P(ω), aber ω + 1 6≺ ω, ω 6≺ ω + 1.
166
8.4. M ÄCHTIGKEITEN
Lemma
(i)
a4a
reflexiv
(ii) a 4 b ∧ b 4 c → a 4 c
(iii)
transitiv
a⊆b→a4b
aber i. a. nicht umgekehrt!
(iv) a ∼ c ∧ a 4 b → c 4 b
ebenso für ≺
(v) b ∼ d ∧ a 4 b → a 4 d
ebenso für ≺
Somit ist die Gleichmächtigkeit (Äquivalenz) von Mengen eine Äquivalenzrelation und eine Kongruenzrelation bezüglich 4 und ≺; die Relation 4 ist reflexiv
und transitiv. Der folgende Satz besagt, daß 4 antisymmetrisch (bis auf ∼) ist, was
trivial ist, wenn man das Auswahlaxiom benutzt. Als eines der wenigen Ergebnisse der Theorie der Mächtigkeiten läßt er sich aber auch ohne diese Voraussetzung
beweisen:
8.4.1 Satz von Cantor-Schröder-Bernstein
a4b ∧ b4a →a∼b
Beweis: Wir führen die Behauptung zunächst auf den einfacheren Fall
(∗) a 4 b ∧ b ⊆ a → a ∼ b
zurück: Nach Voraussetzung existieren Abbildungen
h : a ←→ a0 ⊆ b, g : b ←→ b0 ⊆ a, also
f := g ◦ h : a ←→ a1 ⊆ b0
mit
a1 ⊆ b0 ⊆ a ∧ a1 ∼ a ∧ b ∼ b0 ,
somit
a1 := g[a0 ] ∼ a0 ∼ a, d. h.
a 4 b0 ∧ b0 ⊆ a ∧ b0 ∼ b.
Nach (*) gilt dann a ∼ b0 , also auch a ∼ b, wie zu zeigen war.
Zum Beweis von (*) gehen wir von einer injektiven Abbildung
f :ab⊆a
aus und konstruieren daraus eine Abbildung
g:a↔b
167
8.4. M ÄCHTIGKEITEN
wie folgt:
(
g(x) =
f (x), falls x ∈
x
S
n∈ω
f n [a − b]
sonst.
Dabei ist f 0 (y) = y, f n+1 (y) = f ( f n (y)) (numerische Rekursion). Es gilt nun:
(i) g ist surjektiv, d. h. W (g) = b:
S
Sei d ∈ b. Falls d ∈ n∈ω f n [a − b], so ist d ∈ f n [a − b] für ein n, und zwar
n > 0 wegen d ∈ b. Dann ist aber d = f ( f n−1 (y)) für ein y und damit d ∈ W (g).
Im anderen Fall ist aber d = g(d) und damit auch d ∈ W (g).
(ii) g ist injektiv:
S
Da f injektiv ist, so auch g auf n∈ω f n [a − b], und als identische Abbildung
S
ist sie auch auf dem Komplement injektiv. Ist aber einerseits x ∈ n∈ω f n [a − b]
S
und andererseits y ∈ a − n∈ω f n [a − b], so muß auch g(x) 6= g(y) sein, da g(x) ∈
S
n
n∈ω f [a − b], während g(y) = y im Komplement liegt. Somit ist g eine Bijektion
von a auf b.
Der folgende Satz benötigt zum Beweis notwendig das Auswahlaxiom, da er
hierzu äquivalent ist:
8.4.2 Vergleichbarkeitssatz von Hartogs
a4b ∨b4a
Beweis: Nach dem Wohlordnungssatz gibt es Ordinalzahlen α, β mit a ∼ α und
b ∼ β . Da Ordinalzahlen vergleichbar sind (und zwar α ⊆ β ∨ β ⊆ α), überträgt
sich diese Beziehung in der Form a 4 b ∨ b 4 a auf die entsprechenden Mengen.
Folgerung
Jede unendliche Menge enthält eine abzählbar-unendliche Teilmenge (und ist damit D-unendlich).
Daß es zu jeder Menge eine mit größerer Mächtigkeit gibt, zeigt der
8.4.3 Satz von Cantor
a ≺ P(a)
168
8.5. K ARDINALZAHLEN
Beweis: Da durch x 7→ {x} eine injektive Funktion definiert wird, ist a 4 P(a). Die
Annahme a ∼ P(a) widerlegt man wie im Fall a = ω durch ein Diagonalargument:
Falls f : a P(a), so setze man d := {x ∈ a | x 6∈ f (x)}. Dann erhält man wegen
der Surjektivität von f ein b ∈ a mit d = f (b), was aber mit
b ∈ f (b) = d ↔ b 6∈ b zum Widerspruch führt!
Alternative zum Größenvergleich
Da bei einer Abbildung Mengen möglicherweise auf dasselbe Element abgebildet
werden können, wird man das Bild einer Menge a als höchstens so groß wie a
selbst ansehen. Man findet daher auch folgende Definition:
a 4∗ b :↔ a = 0/ ∨ ∃ f ( f : b a).
Für die Definition der Abzählbarkeit haben wir z. B.:
a abzählbar ↔ a 4∗ ω ↔ a 4 ω,
und der obige Satz von C ANTOR besagt gerade: a 64∗ P(a). Da eine injektive
Funktion eine Umkehrfunktion besitzt, so gilt stets
a 4 b → a 4∗ b,
aber für die Umkehrung benötigt man das Auswahlaxiom (oder zumindest eine
Wohlordnung von b)! Ebenso gilt zwar stets F[a] 4∗ a, aber F[a] 4 a allgemein
nur, wenn das Auswahlaxiom vorausgesetzt ist.
8.5 Kardinalzahlen
Für die Mächtigkeit einer Menge a, bezeichnet mit a, soll gelten:
a ∼ b ↔ a = b.
Diese Eigenschaft kann man natürlich leicht erfüllen, indem man (nach F REGE RUSSELL ) a als zugehörige Äquivalenzklasse {x | x ∼ a} definiert, allerdings ist
diese dann stets eine echte Klasse (außer für a = 0).
/ Die Anzahl einer endlichen
Menge kann man aber auch dadurch bestimmen, daß man sie abzählt: Ist
a = {a0 , . . . , an−1 } mit ai 6= a j für i 6= j,
so ist n die Anzahl der Elemente von a.
Ist jedoch a eine unendliche Menge, so können folgende Probleme auftauchen:
169
8.5. K ARDINALZAHLEN
1. a besitzt keine Aufzählung,
2. a besitzt Aufzählungen verschiedener Länge.
Das erste Problem läßt sich vermeiden, indem man das Auswahlaxiom voraussetzt: Dann läßt sich jede Menge wohlordnen:
a = {aξ | ξ < α} für ein α,
aber das zweite Problem bleibt bestehen: Selbst bei injektiven Aufzählungen ist
die ”Länge” α nicht eindeutig bestimmt. Als Kardinalzahl von a wählt man daher
das kleinstmögliche derartige α:
|a| := a := µα(a ∼ α)
Kardinalzahl von a
Bemerkung
Auch ohne Voraussetzung des Auswahlaxioms kann man (etwa mit Hilfe der
VON -N EUMANNschen Hierarchie) Mächtigkeiten definieren, die Mengen sind.
In diesem Fall nennt man Kardinalzahlen die Mächtigkeiten von wohlgeordneten
Mengen. Allerdings läßt sich (wie wir schon bei obigen Sätzen gesehen haben)
ohne Auswahlaxiom keine befriedigende Theorie der Mächtigkeiten aufbauen.
Daher werden wir im folgenden das Auswahlaxiom stets voraussetzen und nicht
zwischen Kardinalzahlen und Mächtigkeiten unterscheiden.
Beispiele
|n| = n
für jede natürliche Zahl n,
|N| = |ω| = |ω + 1| = |ω + 2| = . . . = |ω + ω| = ω.
Tatsächlich ist jede unendliche Kardinalzahl eine Limeszahl (aber nicht umgekehrt), die Kardinalzahlen bilden somit eine echte Teilklasse Cn der Ordinalzahlen. Cn ist trotzdem immer noch sehr groß: Das Supremum einer Menge von Kardinalzahlen ist wieder eine Kardinalzahl, und nach dem Satz von C ANTOR gibt es
keine größte Kardinalzahl.
8.5.1 Operationen auf den Kardinalzahlen
Die arithmetischen Operationen auf den Kardinalzahlen definiert man analog zum
endlichen Fall, wobei im Falle der Addition zu beachten ist, daß man als Sum-
170
8.5. K ARDINALZAHLEN
me zweier Kardinalzahlen die Vereinigung disjunkter Mengen der entsprechenden
Kardinalzahl wählt:
κ ⊕ λ = |(κ × {0}) ∪ (λ × {1})|
κ λ = |κ × λ |
κ λ = |λ κ| = |{ f | f : λ → κ}|
Endliche Ordinal- und Kardinalzahlen stimmen überein (es sind gerade die
natürlichen Zahlen), und für diese Fälle stimmen diese Operationen mit den entsprechenden Operationen auf den Ordinalzahlen ebenfalls überein. Für unendliche Kardinalzahlen ergeben sich aber wesentliche Unterschiede. So sind die Operationen der Addition und Multiplikation auf den Kardinalzahlen (wie im Falle
der natürlichen Zahlen, aber im Gegensatz zu den ordinalen Operationen) kommutativ, assoziativ und distributiv - wenngleich diese Gesetze trivial sind; es gilt
nämlich der
8.5.2 Satz von Hessenberg
Es seien κ, λ unendliche Kardinalzahlen. Dann gilt:
κ ⊕ λ = κ λ = max{κ, λ }.
(Tatsächlich braucht nur eine der beiden Zahlen unendlich zu sein, im Falle der
Multiplikation darf aber natürlich keine = 0 sein.) Dieses Ergebnis läßt sich (mit
einfachen Monotoniegesetzen) zurückführen auf
Satz
Für unendliche Kardinalzahlen gilt:
κ κ = κ.
Damit vereinfacht sich die Bestimmung der Kardinalzahl unendlicher Mengen
in vielen Fällen, insbesondere für die Mengen:
a<ω : = { f | ∃n < ω f : n → a}
P<ω (a) : = {x ⊆ a | x endlich}
171
8.5. K ARDINALZAHLEN
Satz
Für 0/ 6= b 4 a, a unendlich, gilt:
(i) |a ∪ b| = |a × b| = |a|,
(ii) |a<ω | = |P<ω (a)| = |a|.
Zur Aufzählung der unendlichen Kardinalzahlen benutzt man seit C ANTOR
den hebräischen Buchstaben ℵ (aleph):
ω = ℵ0 < ℵ1 < . . . ℵω < . . .
ℵ0 ist also die Kardinalzahl abzählbar-unendlicher Mengen, ℵ1 die erste überabzählbare Kardinalzahl. Während Addition und Multiplikation unendlicher Kardinalzahlen trivial sind, ist schon der Wert der einfachsten Potenz unbekannt:
Die Mächtigkeit der Menge R der reellen Zahlen ist 2ℵ0 (kardinale Potenz!),
und da R überabzählbar ist, so gilt ℵ1 ≤ 2ℵ0 . Die
Cantorsche Kontinuumshypthese CH
ℵ1 = 2ℵ0
ist aus den Axiomen von ZF + AC weder beweisbar (C OHEN 1963) noch widerlegbar (G ÖDEL 1938). Trotzdem gibt es einige einfache Abschätzungen:
8.5.3 Satz von Bernstein
α
2 ≤ κ ≤ ℵα → 2ℵα = κ ℵα = ℵℵ
α
ℵα
α
β ≤ α → ℵα < 2ℵα = ℵℵ
β = ℵα
Wir definieren eingeschränkte Potenzmengenoperationen:
P<λ (a) : = {x | x ⊆ a ∧ |x| < λ },
P≤λ (a) : = {x | x ⊆ a ∧ |x| ≤ λ },
Pλ (a) : = {x | x ⊆ a ∧ |x| = λ }.
Korollar
Für unendliches a, κ, λ :
(i) |P<ω (a)| = |a|,
(ii) |{ f | Fkt( f ) ∧ D( f ) ⊆ κ ∧ D( f ) endlich ∧W ( f ) ⊆ λ }| = max(κ, λ ).
(iii) |Pλ (κ)| = |P≤λ (κ)| = κ λ für λ ≤ κ , insbesondere:
(iv) |Pκ (κ)| = |P(κ)| = κ κ = 2κ .