B.1 Kardinalzahlen
Wir stellen hier einige Tatsachen über Mächtigkeiten unendlicher Mengen zusammen (siehe auch Abschnitt LA1.3.15).
Der entscheidende Punkt an dieser Definition ist, dass zwei unendliche Mengen nicht unbedingt gleichmächtig sind, zum Beispiel sind \(\mathbb Q\) und \(\mathbb R\) nicht gleichmächtig (siehe unten). Es ist klar, dass Gleichmächtigkeit eine Äquivalenzrelation ist.
(\(\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.
Es gelten dann die folgenden Aussagen:
Ist \(X\) eine Menge, so dass eine injektive Abbildung von \(X\) in eine abzählbar unendliche Menge existiert, dann ist \(X\) selbst höchstens abzählbar.
Jedes kartesische Produkt von abzählbar unendlichen Mengen über eine endliche Indexmenge ist abzählbar.
Jede Vereinigung von abzählbar unendlichen Mengen über eine endliche oder abzählbar unendliche Indexmenge ist abzählbar.
zu (1). Wir können annehmen, dass \(X\) unendlich ist und dass eine Injektion \(f\colon X\to \mathbb N\) existiert. Wir konstruieren eine Bijektion \(g\colon \mathbb N\to X\) indem wir induktiv \(g(n)\) folgendermaßen definieren: Es sei \(g(0)\) das Element \(x\), für das \(f(x)\) minimal ist. Für \(n {\gt} 0\) sei \(g(n)\) das eindeutig bestimmte \(x\), für das \(f(x)\) minimal ist unter allen Werten \(f(y)\), \(y \in X\setminus \{ g(0), \dots , g(n-1) \} \). Man zeigt dann, dass \(g\) bijektiv ist. (Dies ist auch ein Spezialfall des Satzes von Schröder-Bernstein, Theorem 3.85.)
zu (2). Per Induktion können wir uns auf den Fall eines Produkts mit \(2\) Faktoren zurückziehen. Es genügt dann, die Abzählbarkeit von \(\mathbb N\times \mathbb N\) zu beweisen. Dafür denken wir uns die Elemente von \(\mathbb N\times \mathbb N\) als die Punkte mit nicht-negativen ganzzahligen Koordinaten in \(\mathbb R^2\), und »schreiben diese in eine Liste« (stellen also eine Bijektion mit \(\mathbb N\)) her, indem wir sie nach dem folgenden Schema anordnen:
![\begin{tikzpicture}
\clip (-0.5,-0.5) rectangle + (5,5);
\draw[->, gray, thick] (-0.8*\scaleunit, 0) -- (8.8*\scaleunit, 0);
\draw[->, gray, thick] (0, -0.8*\scaleunit) -- (0, 8.8*\scaleunit);
\foreach \x in {1, 2, 3, 4}{
\draw[gray] (2*\x*\scaleunit, -0.1) -- (2*\x*\scaleunit, 0.1) node[black, below, yshift=-.1cm] {\x};
};
\foreach \x in {1, 2, 3, 4}{
\draw[gray] (-0.1, 2*\x*\scaleunit) -- (0.1, 2*\x*\scaleunit) node[black, left, xshift=-.1cm] {\x};
};
\foreach \x in {0,...,4}{%
\foreach \y in {0,...,4}{%
\fill (\x, \y) circle[radius=1mm];
};
};
\draw[->, ultra thick, blue] (0, 0) -- (1, 0);
\draw[->, ultra thick, blue] (1, 0) -- (0, 1);
\draw[->, ultra thick, blue] (0, 1) -- (0, 2);
\draw[->, ultra thick, blue] (0, 2) -- (1, 1);
\draw[->, ultra thick, blue] (1, 1) -- (2, 0);
\draw[->, ultra thick, blue] (2, 0) -- (3, 0);
\draw[->, ultra thick, blue] (3, 0) -- (2, 1);
\draw[->, ultra thick, blue] (2, 1) -- (1, 2);
\draw[->, ultra thick, blue] (1, 2) -- (0, 3);
\draw[->, ultra thick, blue] (0, 3) -- (0, 4);
\draw[->, ultra thick, blue] (0, 4) -- (1, 3);
\draw[->, ultra thick, blue] (1, 3) -- (2, 2);
\end{tikzpicture}](images/img-0007.svg)
Wir definieren also \(\mathbb N\to \mathbb N\times \mathbb N\) durch
Jedenfalls von der Zeichnung her ist klar, dass es sich um eine Bijektion handelt, und mit etwas mehr Mühe kann man das auch formal hinschreiben.
zu (3). Wir betrachten eine Vereinigung \(X= \bigcup _{i\in I} X_i\), wo alle \(X_i\) und die Indexmenge höchstens abzählbar seien. Wegen Teil (1) können wir diese Menge ohne Einschränkung vergrößern, wir können daher die Vereinigung durch eine disjunkte Vereinigung ersetzen und annehmen, dass sowohl \(I\) als auch alle \(X_i\) abzählbar unendlich sind. Durch Wahl geeigneter Bijektionen können wir diese Vereinigung mit \(\bigcup _{i\in \mathbb N} \{ i\} \times \mathbb N= \mathbb N\times \mathbb N\) identifizieren und die Frage so auf Teil (2) zurückführen.
Siehe auch Ergänzung LA1.3.65 (das »Hilbertsche Hotel«).
Die Menge \(\mathbb Q\) der rationalen Zahlen ist abzählbar.
Jeder endlichdimensionale \(\mathbb Q\)-Vektorraum ist höchstens abzählbar.
Der Polynomring \(\mathbb Q[X]\) ist abzählbar.
Andererseits gilt:
Die Menge \(\mathbb R\) der reellen Zahlen ist überabzählbar.
Die Menge \(\{ 0, 1\} ^\mathbb N= \prod _{i\in \mathbb N} \{ 0,1\} \) ist überabzählbar.
Dies folgt aus dem sogenannten Diagonalargument von Georg Cantor. Wir erklären den Beweis von Teil (1), für Teil (2) kann man ähnlich vorgehen.
Wir zeigen, dass sogar das Einheitsintervall \([0, 1]\) nicht abzählbar ist. Sei \(f\colon \mathbb N\to [0, 1]\) eine Abbildung. Wir zeigen, dass \(f\) nicht surjektiv ist. Insbesondere kann es keine Bijektion zwischen \(\mathbb N\) und \([0, 1]\) geben. Jedes Element von \([0, 1]\) hat eine Darstellung als Dezimalzahl (zum Beispiel \(0,1234\dots \)). Diese Darstellung ist im allgemeinen nicht eindeutig (zum Beispiel ist \(1 = 0,999\dots \)), sie ist aber eindeutig, wenn wir zusätzlich verlangen, dass die Darstellung nicht mit »Periode \(9\)« endet, also nicht irgendwann nur noch Neunen folgen. (Alternativ könnte man die Eindeutigkeit auch erreichen, indem man verlangt, dass nicht irgendwann nur noch Nullen folgen.)
Wir schreiben nun die eindeutigen Dezimalzahldarstellungen von \(f(0)\), \(f(1)\), \(f(2)\), …untereinander und konstruieren die Dezimalzahldarstellung einer Zahl in \(x\in [0, 1]\setminus \operatorname{Im}(f)\) wie folgt: Die \(n\)-te Nachkommastelle von \(x\) sei
Dann ist \(x\not\in \operatorname{Im}(f)\), denn \(x\) und \(f(n-1)\) unterscheiden sich (mindestens) an der \(n\)-ten Stelle hinter dem Komma. Wegen der Eindeutigkeit der Darstellung impliziert das \(x\ne f(n-1)\).
Weil der Körper \(\mathbb C\) der komplexen Zahlen die Menge \(\mathbb R\) als Teilmenge enthält, folgt insbesondere, dass \(\mathbb C\) nicht abzählbar ist.
Auf den Kardinalzahlen lässt sich folgendermaßen eine totale Ordnung definieren: Für Mengen \(M\), \(M'\) schreiben wir \(\# M \le \# M'\), wenn es eine injektive Abbildung \(M\to M'\) gibt. Wir schreiben \(\# M {\lt} \# M'\), wenn \(\# M \le \# M'\) und nicht \(\# M= \# M'\) gilt, d.h. wenn es eine Injektion \(M\to M'\), aber keine Bijektion zwischen \(M\) und \(M'\) gibt. Diese Definition für \(\le \) erfüllt die Eigenschaften einer totalen Ordnung: Offenbar folgt aus \(\# M \le \# M'\) und \(\# M' \le \# M''\), dass \(\# M\le \# M''\), 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'\) Mengen. Dann gilt genau eine der folgenden drei Aussagen:
Für die Beweise der Theoreme und des folgenden Satzes siehe zum Beispiel [ Hu ] Kapitel 0, Abschnitt 8.
Die Kardinalzahl \(\aleph _0\) ist die kleinste unendliche Kardinalzahl:
Sei \(M\) eine unendliche Menge. Dann gilt \(\# M \ge \# \mathbb N\).
Mit dem Auswahlaxiom kann man aus der Existenz einer surjektiven Abbildung eine Abschätzung über die Kardinalitäten herleiten:
Seien \(M\), \(M'\) Mengen, so dass eine surjektive Abbildung \(f\colon M\to M'\) existiert. Dann gilt \(\# M' \le \# M\).
Wir wählen für jedes Element \(m'\in M'\) ein Element \(g(m')\) aus der (nicht-leeren) Menge \(f^{-1}(\{ m'\} )\) aus. Dies definiert eine Abbildung \(g\colon M'\to M\) mit der Eigenschaft \(f\circ g = \operatorname{id}_{M'}\). Insbesondere ist \(g\) injektiv.
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) = \# \{ 0,1 \} ^{\mathbb N}\). In der Tat können wir eine Bijektion zwischen \(P(\mathbb N)\) und \(\{ 0,1 \} ^{\mathbb N} = \operatorname{Abb}(\mathbb N, \{ 0, 1\} )\) definieren, indem wir einer Teilmenge \(M\subseteq \mathbb N\) ihre charakteristische Funktion
\[ \chi _M \colon \mathbb N\to \{ 0, 1\} ,\quad n\mapsto \begin{cases} 1 & n\in M,\\ 0 & n\not\in M, \end{cases} \]zuordnen, und umgekehrt einer Abbildung \(\chi \colon \mathbb N\to \{ 0, 1\} \) die Menge \(\chi ^{-1}(1)\).
Es gilt \(\# P(\mathbb N) = \# \mathbb R\). (Skizze: Nach Teil (1) genügt es zu zeigen, dass \(\mathbb R\) und \(\{ 0,1 \} ^{\mathbb N}\) dieselbe Mächtigkeit haben. Es ist nicht schwer, eine Bijektion zwischen \(\mathbb R\) und dem offenen Einheitsintervall \((0, 1)\) anzugeben. Also genügt es, \(\# (0,1) = \# \{ 0,1 \} ^{\mathbb N}\) zu beweisen.
Eine Idee dafür ist, Elemente von \(\{ 0,1 \} ^{\mathbb N}\), also abzählbar unendliche Tupel von Nullen und Einsen als Binärdarstellung (»nach dem Komma«) einer reellen Zahl zwischen \(0\) und \(1\) zu betrachten. Mit anderen Worten betrachten wir die Abbildung
\[ \{ 0,1 \} ^{\mathbb N}\to [0, 1],\quad (a_i)_{i\in \mathbb N} \mapsto \sum _{i=0}^\infty \frac{a_i}{2^{i+1}}. \]Diese Abbildung ist surjektiv, allerdings auf das abgeschlossene Einheitsintervall. Sie ist außerdem nicht injektiv (vergleiche die Diskussion im Zusammenhang mit Cantors Diagonalargument oben). Immerhin sehen wir so aber \(\# \{ 0,1\} ^{\mathbb N} \ge \# [0, 1] \ge \# (0,1) = \# \mathbb R\).
Statt diese Abbildung zu einer Bijektion \(\{ 0,1 \} ^{\mathbb N}\to (0, 1)\) abzuändern (was ziemlich lästig wäre), benutzen wir, dass es nach dem Satz von Schröder-Bernstein genügt, nun noch die andere Abschätzung, also \(\# \{ 0,1\} ^{\mathbb N} \le \# \mathbb R\) zu zeigen. Eine Möglichkeit dafür ist, die injektive (warum?) Abbildung
\[ \{ 0,1 \} ^{\mathbb N}\to \mathbb R,\quad (a_i)_{i\in \mathbb N} \mapsto \sum _{i=0}^\infty \frac{a_i}{3^{i+1}} \]herzunehmen.
Wenn man Satz B.10 (für dessen Beweis wir das Auswahlaxiom benutzt haben) nicht einsetzen möchte, kann man die Abschätzung \(\mathbb R\le \# \{ 0,1\} ^{\mathbb N} = \# P(\mathbb N)\) auch folgendermaßen zeigen. Aus einer Bijektion \(\mathbb N\cong \mathbb Q\) erhalten wir eine Bijektion \(P(\mathbb N)\cong P(\mathbb Q)\). Die Abbildung \(\mathbb R\to P(\mathbb Q)\), \(x\mapsto \{ r\in \mathbb Q;\ r {\lt} x \} \), ist injektiv (denn \(x\) ist das Supremum in \(\mathbb R\) seines Bildes unter dieser Abbildung). Also gilt \(\# \mathbb R\le \# P(\mathbb Q) = \# P(\mathbb N)\).
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)\). Mit anderen Worten: Jede überabzählbare Teilmenge von \(\mathbb R\) hat dieselbe Mächtigkeit wie \(\mathbb R\).
Es wurde von Kurt Gödel und Paul 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. Cohen erhielt für seine Arbeiten 1966 die Fields-Medaille.