3.15 Mächtigkeit von Mengen *
Für endliche Mengen haben wir die Mächtigkeit in Abschnitt 3.13 definiert. Wir wollen hier die Erweiterung dieses Begriffs auf den Fall unendlicher Mengen skizzieren. (Für den Moment ohne Beweise.)
Achtung: Zwei unendliche Mengen sind nicht unbedingt gleichmächtig (siehe unten). Aus der unpräzisen Aussage \(\# M = \infty \), \(\# M^\prime =\infty \) lässt sich also nicht die Gleichheit \(\# M = \# M^\prime \) im Sinne dieser Definition folgern.
Wir drücken uns hier darum, genau zu sagen, was für ein Objekt \(\# M\) eigentlich ist. (Man nennt diese Ausdrücke Kardinalzahlen.) Es soll für uns genügen zu wissen, wie man Kardinalzahlen vergleicht.
(\(\aleph \), ausgesprochen Aleph, ist der erste Buchstabe des hebräischen Alphabets.)
Wenn man von einer Menge \(M\) sagt, sie sei höchstens abzählbar, so meint man, dass \(M\) endlich oder abzählbar unendlich sei. Eine unendliche Menge, die nicht abzählbar ist, heißt überabzählbar.
\(\mathbb Q\) ist abzählbar.
\(\mathbb R\) ist nicht abzählbar, also überabzählbar.
Siehe auch Ergänzung 3.65.
Wir können die Mächtigkeiten von Mengen folgendermaßen anordnen: Sind \(M\), \(M^\prime \) Mengen, so schreiben wir \(\# M \le \# M^\prime \), wenn es eine injektive Abbildung \(M\to M^\prime \) gibt. Wir schreiben \(\# M {\lt} \# M^\prime \), wenn \(\# M \le \# M^\prime \) und nicht \(\# M= \# M^\prime \) gilt, d.h. wenn es eine Injektion \(M\to M^\prime \), aber keine Bijektion zwischen \(M\) und \(M^\prime \) gibt. Diese Definition für \(\le \) erfüllt die Eigenschaften einer totalen Ordnung: Offenbar folgt aus \(\# M \le \# M^\prime \) und \(\# M^\prime \le \# M^{\prime \prime }\), dass \(\# M\le \# M^{\prime \prime }\), weil die Verkettung injektiver Abbildungen wieder injektiv ist. Es ist auch klar, dass \(\# M \le \# M\) für alle \(M\) gilt, da die Identität eine injektive Abbildung ist.
Etwas schwieriger sind die folgenden beiden Ergebnisse, die die Antisymmetrie und Totalität zeigen:
Seien \(M\), \(M^\prime \) Mengen. Dann gilt genau eine der folgenden drei Aussagen:
Sei \(M\) eine unendliche Menge. Dann gilt \(\# M \ge \# \mathbb N\).
Sei \(M\) eine Menge und \(P(M)\) ihre Potenzmenge, d.h. die Menge alle Teilmengen von \(M\). Dann gilt \(\# M {\lt} \# P(M)\).
Es ist klar, dass es eine Injektion \(M\to P(M)\) gibt, zum Beispiel die Abbildung \(m\mapsto \{ m\} \). Wir müssen daher zeigen, dass es keine Surjektion \(M\to P(M)\) gibt. Sei \(\varphi \colon M\to P(M)\) eine Abbildung. Wir behaupten, dass \(X:=\{ m\in M;\ m\not \in \varphi (m) \} \) nicht im Bild von \(\varphi \) liegt (insbesondere ist \(\varphi \) nicht surjektiv). In der Tat, nehmen wir an, dass \(X = \varphi (m)\) für ein \(m\in M\). Wenn \(m\in X\), dann folgt \(m\not \in \varphi (m)=X\), ein Widerspruch. Wenn \(m\not \in X\), dann folgt \(m\not \in \varphi (m)\), also \(m\in X\), auch ein Widerspruch. Weil weder \(m\in X\) noch \(m\not \in X\) richtig sein kann, kann die Teilmenge \(X\) von \(M\) nicht im Bild von \(\varphi \) liegen.
Es gilt \(\# P(\mathbb N) = \# \mathbb R\).
Unter der Kontinuumshypothese versteht man die Aussage, dass jede Menge \(M\) mit \(\# \mathbb N\le \# M \le \# P(\mathbb N)\) entweder abzählbar ist (also \(\# \mathbb N= \# M\) gilt), oder die Mächtigkeit von \(P(\mathbb N)\) hat, also \(\# M = \# P(\mathbb N) (=\# \mathbb R)\).
Es wurde von K. Gödel und P. Cohen bewiesen, dass die Kontinuumshypothese unabhängig von dem üblichen Axiomensystem ZFC ist – sie lässt sich weder widerlegen (Gödel, 1938), noch beweisen (Cohen, 1960). Man könnte also entweder die Kontinuumshypothese zu den anderen Axiomen hinzunehmen, oder ihre Negation.
Die verallgemeinerte Kontinuumshypothese ist die Aussage, dass für jede unendliche Menge \(M\) keine Mächtigkeit existiert, die strikt zwischen \(\# M\) und \(\# P(M)\) liegt. Sie ist ebenfalls unabhängig von ZFC.