7.4 Mächtigkeit und Abzählbarkeit

Zählen durch Zuordnen

Bei endlichen Mengen vergleichen wir die Anzahl ihrer Elemente. Eine Bijektion beschreibt denselben Vergleich ohne Abzählen und funktioniert auch für unendliche Mengen.

Definition 7.7 (Gleichmächtigkeit und Vergleich von Mächtigkeiten). Zwei Mengen \(A,B\) heißen gleichmächtig, geschrieben \(|A|=|B|\), wenn eine Bijektion \(A\to B\) existiert.

Wir schreiben \(|A|\leq|B|\), wenn eine Injektion \(A\to B\) existiert.

Wir schreiben \(|A|<|B|\), wenn es eine Injektion \(A\to B\), aber keine Surjektion \(A\to B\) gibt.

Gleichmächtigkeit ist reflexiv, symmetrisch und transitiv: Dafür verwenden wir die Identität, die Umkehrfunktion und die Verkettung von Bijektionen. Gleichmächtigkeit von Mengen definiert also ein Äquivalenzrelation. Die Äquivalenzklassen bezüglich dieser Äquivalenzrelation heißen Kardianalzahlen.

Für unendliche Mengen ist Mächtigkeit etwas anderes als geometrische Länge: Die Bijektion \([0,1]\to[0,2]\), \(x\mapsto2x\), verbindet zwei unterschiedlich lange Intervalle und zeigt so, dass sie gleichmächtig sind. Ebenso ist \(n\mapsto2n\) eine Bijektion von \(\mathbb N\) auf die geraden positiven Zahlen. Daher sind die Mengen \(\mathbb N\) und \(2\mathbb N=\{2n \mid n\in\mathbb N\}\) gleichmächtig, obwohl die zweite Menge eine echte Teilmenge der ersten ist.

Unendlich und trotzdem abzählbar

Wir verwenden \(\mathbb N=\{1,2,3,\ldots\}\) und \(\mathbb N_0=\{0,1,2,\ldots\}\). Eine Abzählung erreicht jedes ihrer Elemente an einer endlichen Position.

Definition 7.8 (Abzählbarkeit). Eine Menge heißt abzählbar unendlich, wenn sie gleichmächtig zu \(\mathbb N\) ist. Sie heißt höchstens abzählbar, wenn sie endlich oder abzählbar unendlich ist. Eine Menge, die nicht höchstens abzählbar ist, heißt überabzählbar.

Dass eine Menge abzählbar ist, bedeutet also, dass wir ihre Elemente in einer Liste anordnen können, sodass jedes Element nach endlich vielen Schritten erreicht wird. Die Abzählung kann beliebig lang werden, solange kein Element fehlt und keines doppelt vorkommt.

Beispiel: Ganze Zahlen abzählen

Die Liste \(0,-1,1,-2,2,-3,3,\ldots\) enthält jede ganze Zahl genau einmal. Eine zugehörige Bijektion ist \[ z:\mathbb N\to\mathbb Z,\qquad z(n)=\begin{cases}\frac{n-1}{2},&n\text{ ungerade},\\-\frac n2,&n\text{ gerade}. \end{cases} \]

Die rationalen Zahlen lassen sich abzählen

Satz 7.3 (Abzählbarkeit der rationalen Zahlen). Die Mengen \(\mathbb Q_{>0}\) und \(\mathbb Q\) sind abzählbar unendlich.

\(\mathbb Q_{>0}=\{r\in\mathbb Q\mid r>0\}\) bezeichnet die Menge der positiven rationalen Zahlen.

Beweis. Die unendlich fortgesetzte Tabelle enthält alle Brüche \(\frac pq\) mit \(p,q\in\mathbb N\), also alle positiven rationalen Zahlen. Wir wollen jeden Wert nach endlich vielen Schritten genau einmal erreichen.

Orange Pfeile: eine Diagonale durchgehen. Gestrichen: bereits erfasste Werte.

Diagonalen durchgehen: Wir durchlaufen \(p+q=2,3,4,\ldots\), jeweils mit wachsendem \(p\).

Doppelte Werte überspringen: Zum Beispiel wird \(\frac22=\frac11\) ausgelassen. So beginnt die Abzählung: \[ 1,\quad\frac12,\quad2,\quad\frac13,\quad3,\quad\frac14,\quad\frac23,\quad\frac32,\quad4,\ldots \]

Jede Zahl wird erreicht: Bis zu jedem Bruch sind nur endlich viele Einträge zu durchlaufen. Ohne Wiederholungen entsteht eine bijektive Abzählung \(q_1,q_2,\ldots\) von \(\mathbb Q_{>0}\).

Alle rationalen Zahlen: \(0,q_1,-q_1,q_2,-q_2,\ldots\) zählt \(\mathbb Q\) ab. Damit sind beide Mengen abzählbar unendlich. \(\square\)

Die reellen Zahlen sind überabzählbar

Satz 7.4 (Überabzählbarkeit des Einheitsintervalls). Das Intervall \((0,1)\) ist überabzählbar. Damit ist auch \(\mathbb R\) überabzählbar.

Das Diagonalargument verändert die \(n\)-te Nachkommastelle des \(n\)-ten Eintrags.

Beweis

Beweis. Angenommen, \(x_1,x_2,\ldots\) wäre eine vollständige Abzählung des unendlichen Intervalls \((0,1)\). Wir wählen jeweils die Dezimaldarstellung ohne unendliche Neunerfolge.

\[ \begin{array}{rlccccc} x_1&=0,&\color{orange}{a_{11}}&a_{12}&a_{13}&a_{14}&\cdots\\ x_2&=0,&a_{21}&\color{orange}{a_{22}}&a_{23}&a_{24}&\cdots\\ x_3&=0,&a_{31}&a_{32}&\color{orange}{a_{33}}&a_{34}&\cdots\\ x_4&=0,&a_{41}&a_{42}&a_{43}&\color{orange}{a_{44}}&\cdots\\ \vdots&&\vdots&\vdots&\vdots&\vdots&\ddots \end{array} \]

\(a_{nk}\in\{0,1,\ldots,9\}\) ist die \(k\)-te Nachkommastelle von \(x_n\).

Eine neue Zahl konstruieren: Wir ändern jede Ziffer der markierten Diagonale: \[ b_n=\begin{cases}2,&a_{nn}=1,\\1,&a_{nn}\neq1,\end{cases} \qquad z=0,b_1b_2b_3\ldots. \] Da alle \(b_n\) gleich \(1\) oder \(2\) sind, liegt \(z\) in \((0,1)\) und besitzt keine zweite Dezimaldarstellung.

Abweichung von jedem Eintrag: Für jedes \(n\) gilt \(b_n\neq a_{nn}\). Die Zahlen \(z\) und \(x_n\) unterscheiden sich an der \(n\)-ten Nachkommastelle. Also ist \(z\neq x_n\) für alle \(n\).

Damit fehlt \(z\) in der angeblich vollständigen Abzählung: ein Widerspruch. Also ist \((0,1)\) überabzählbar. Wegen \((0,1)\subseteq\mathbb R\) ist auch \(\mathbb R\) überabzählbar. \(\square\)

Die Potenzmenge ist stets mächtiger

Satz 7.5 (Cantors Potenzmengensatz). Für jede Menge \(M\) gilt \(|M|<|\mathcal P(M)|\).

Für den Beweis zeigen wir zunächst, dass es eine Injektion \(M\to\mathcal P(M)\) gibt. Anschließend zeigen wir, dass es keine Surjektion \(M\to\mathcal P(M)\) geben kann. Damit folgt die strikte Ungleichung.

Beweis

Beweis. \(x\mapsto\{x\}\) ist eine Injektion \(M\to\mathcal P(M)\). Angenommen, es gäbe eine Surjektion \(g:M\to\mathcal P(M)\). Dann ist \(A=\{x\in M\mid x\notin g(x)\}\) eine Teilmenge von \(M\). Wegen der Surjektivität existiert \(a\in M\) mit \(g(a)=A\). Es folgt \[ a\in A\quad\Longleftrightarrow\quad a\notin g(a) \quad\Longleftrightarrow\quad a\notin A, \] ein Widerspruch. Daher gibt es keine Surjektion und insbesondere keine Bijektion. \(\square\)

Mehrere Größen des Unendlichen

Wir haben bisher zwei verschiedene Größen unendlicher Mengen kennengelernt: \(\mathbb N\), \(\mathbb Z\) und \(\mathbb Q\) sind gleichmächtig und abzählbar, während \((0,1)\) und \(\mathbb R\) überabzählbar sind. Der folgende Satz ordnet auch die Potenzmenge von \(\mathbb N\) in diesen Vergleich ein.

Satz 7.6 (Mächtigkeit des Kontinuums). Es gilt \[ |\mathbb N|=|\mathbb Z|=|\mathbb Q| <|(0,1)|=|\mathbb R|=|\mathcal P(\mathbb N)|. \] Die Gleichheiten mit \(\mathcal P(\mathbb N)\) verwenden wir ohne Beweis.

Dass \((0,1)\) und \(\mathbb R\) gleichmächtig sind, zeigt erneut: Die geometrische Ausdehnung einer Menge bestimmt nicht ihre Mächtigkeit. Eine Bijektion ist \(x\mapsto\tan(\pi(x-\frac12))\); warum diese Abbildung funktioniert, werden wir bei den trigonometrischen Funktionen verstehen. Die gemeinsame Mächtigkeit dieser Mengen heißt Mächtigkeit des Kontinuums.

Für die Einordnung von \(\mathcal P(\mathbb N)\) beschreiben wir Teilmengen zunächst durch Bitfolgen und vergleichen diese anschließend mit Zahlendarstellungen.

Teilmengen als unendliche Bitfolgen

Eine Teilmenge \(A\subseteq\mathbb N\) ist dadurch bestimmt, welche natürlichen Zahlen zu ihr gehören. Diese Information speichern wir in einer unendlichen Bitfolge: \[ A\longmapsto(b_1,b_2,b_3,\ldots),\qquad b_n=\begin{cases}1,&n\in A,\\0,&n\notin A.\end{cases} \] Zum Beispiel entspricht \(A=\{1,3,4\}\) der Folge \((1,0,1,1,0,0,\ldots)\).

Umgekehrt erhalten wir aus jeder Bitfolge genau eine Teilmenge: \(A=\{n\in\mathbb N\mid b_n=1\}\). Die Zuordnung ist also eine Bijektion.

Mit \(\{0,1\}^{\mathbb N}\) bezeichnen wir die Menge aller unendlichen Bitfolgen. Damit gilt \[ |\{0,1\}^{\mathbb N}|=|\mathcal P(\mathbb N)|>|\mathbb N|. \] Alle endlichen Binärwörter lassen sich abzählen; die Menge aller unendlichen Bitfolgen ist dagegen überabzählbar.

Von Bitfolgen zu reellen Zahlen

Eine unendliche Bitfolge erinnert an die Nachkommastellen einer Binärzahl. Es liegt daher nahe, \((b_1,b_2,\ldots)\) als \(0{,}b_1b_2\ldots_2\) zu lesen. So erhält man eine reelle Zahl in \([0,1]\).

Diese Zuordnung ist jedoch nicht injektiv, denn zum Beispiel gilt \[ 0{,}1000\ldots_2=0{,}0111\ldots_2. \] Zwei verschiedene Bitfolgen stellen hier dieselbe Zahl dar. Das bloße Lesen als Binärzahl liefert deshalb noch keine Bijektion.

Die Gleichmächtigkeit von \(\{0,1\}^{\mathbb N}\) und \([0,1]\) gilt dennoch; den Beweis führen wir hier nicht aus. Wir erhalten damit die Gleichheit der Mächtigkeiten \[ |\{0,1\}^{\mathbb N}|=|[0,1]|=|\mathcal P(\mathbb N)|=|\mathbb R|. \] Teilmengen von \(\mathbb N\), unendliche Bitfolgen und reelle Zahlen haben also dieselbe Mächtigkeit, die Mächtigkeit des Kontinuums.

Es geht hier um zwei unterschiedliche Fragen: Die angegebene Zuordnung ist keine Bijektion; trotzdem existiert eine Bijektion zwischen den betreffenden Mengen. Deshalb müssen wir beim Vergleich von Mächtigkeiten die Eigenschaften der verwendeten Abbildung genau prüfen. Aus einer anschaulichen Darstellung allein folgt noch keine Gleichmächtigkeit.

Es gibt keine größte Mächtigkeit

Cantors Potenzmengensatz gilt für jede Menge, also auch für eine Menge, die selbst schon eine Potenzmenge ist. Wir können ihn deshalb wiederholt anwenden: \[ |\mathbb N|<|\mathcal P(\mathbb N)|<|\mathcal P(\mathcal P(\mathbb N))|<\cdots. \]

Der erste Schritt führt von der abzählbaren Menge \(\mathbb N\) zur Mächtigkeit von \(\mathbb R\). Schon der nächste Schritt liefert eine Menge, die mächtiger als \(\mathbb R\) ist. Überabzählbare Mengen können somit unterschiedliche Mächtigkeiten besitzen.

Das Verfahren lässt sich immer weiter fortsetzen. Es gibt also keine größte Mächtigkeit: Zu jeder Menge \(M\) besitzt \(\mathcal P(M)\) eine strikt größere Mächtigkeit.

Damit ist auch klar, dass „überabzählbar“ keine einzelne Mächtigkeit bezeichnet. Sowohl \(\mathcal P(\mathbb N)\) als auch \(\mathcal P(\mathcal P(\mathbb N))\) sind überabzählbar, aber sie sind nicht gleichmächtig.

Anmerkung. Lassen sich beliebige Mächtigkeiten vergleichen?

Für die Mengen in unserer Übersicht ist die Reihenfolge durch die genannten Bijektionen und Cantors Potenzmengensatz begründet. Allgemeiner gilt in der üblichen Mengenlehre mit Auswahlaxiom: Für je zwei Mengen \(A,B\) gibt es eine Injektion \(A\to B\) oder eine Injektion \(B\to A\). Ihre Mächtigkeiten sind also stets vergleichbar. Diese allgemeine Aussage beweisen wir hier nicht; für die oben dargestellte Kette benötigen wir sie nicht.

Zusammenfassung

• Bijektionen definieren Gleichmächtigkeit; Injektionen ermöglichen Größenvergleiche.
• \(\mathbb N\), \(\mathbb Z\) und \(\mathbb Q\) sind abzählbar unendlich.
• Alle endlichen Binärwörter lassen sich abzählen, alle unendlichen Bitfolgen nicht.
• Cantors Diagonalverfahren zeigt die Überabzählbarkeit von \((0,1)\).
• Reelle Zahlen, Teilmengen von \(\mathbb N\) und unendliche Bitfolgen haben dieselbe Mächtigkeit.
• Jede Potenzmenge ist strikt mächtiger als ihre Ausgangsmenge; deshalb gibt es keine größte Mächtigkeit.