Im letzten Kapitel haben wir viele Mengen kennengelernt, die abzählbar unendlich sind, also gleichmächtig mit $\N$. Hier werden wir nun erkunden, welche Mengen gleichmächtig mit $\R$ sind. In der mathematischen Fachsprache sagt man: sie haben die Kardinalität des Kontinuums. Das Wort Kardinalität steht hier für Anzahl der Elemente (bzw. den Größenbegriff bei unendlichen Mengen), und Kontinuum steht für die reellen Zahlen. Im nächsten Kapitel werden wir zeigen, dass es "echt mehr" reelle Zahlen gibt als natürliche; dass also $\R$ nicht abzählbar ist. Aber eins nach dem anderen.

Wir führen nun eine neue Notation ein: $\{0,1\}^{\N}$ ist die Menge aller unendlichen Folgen von $0$ und $1$. Formal gesehen bezeichnet man für zwei Mengen $A$ und $B$ mit der Notation $A^B$ die Menge aller Funktionen $\phi : B \rightarrow A$. Ein Element aus $\{0,1\}^{\N}$ wäre demnach eien Funktion $\phi : \N \rightarrow \{0,1\}$. Diese Objekte entsprechen genau den unendlichen $0/1$-Folgen, nämlich $\phi(0)\phi(1)\phi(2)\phi(3)\dots$. Der Unterschied ist rein syntaktisch. Es ist allerdings bequemer, sich ein $\phi \in \{0,1\}^{\N}$ als unendliche $0/1$-Folge vorzustellen.

Beweis. Die Beweisidee ist einfach, allerdings gehen erst einmal ein paar Dinge schief, die man wieder flicken muss. Da laut $\R \approx [0,1)$ gilt, reicht es, eine Bijektion $f : [0,1) \rightarrow \{0,1\}^{\N}$ zu konstruieren. So geht's:

Jede Zahl $0 \leq x \lt 1$ lässt sich als (unendliche) Binärzahl $(x)_2$ schreiben, beispielsweise

$$ \begin{align*} \pfrac{1}{3}_2 = 0.01010101\dots \end{align*} $$

Wir erhalten nun unsere unendliche $0/1$-Folge, indem wir die führende Null und den Punkt abschneiden: $f(1/3) = 010101\dots$. Das geht für jede Zahl in $[0,1)$: $f(1/2) = 100000\dots$, $f(1/4) = 010000\dots$.

Die konstruierte Funktion $f$ ist injektiv: zwei verschiedene $0 \leq x \lt y \lt 1$ haben verschiedene Binärdarstellung und werden somit zu zwie verschiedenen $0/1$-Folgen. Leider ist sie nicht surjektiv: die Binärdarstellung einer reellen Zahl hört nie mit $11111\dots$ auf. Statt $0.001111111\dots$ würden wir einfach $0.0100000\dots$ schreiben. Das entspricht dem Phänomen in der Dezimalschreibweise, dass $0.99999999\dots$ und $1.000000\dots$ die gleiche Zahl repräsentieren. Die "kanonische" Repräsentierung ist allerdings immer die mit einem unendlichen Schweif an Nullen, nie mit Neunen (oder in Binär: Einsen). Definieren wir also $X$, die Menge aller $0/1$-Folgen mit einem unendlichen Schweif an Einsen:

$$ \begin{align*} X := \{ a_1 a_2 a_3 \dots \in \{0,1\}^{\N} \ | \ \exists\ n \geq 1: a_i = 1 \ \forall i \geq n\} \end{align*} $$

Unsere Funktion $f$ ist eine Bijektion von $[0,1)$ nach $\{0,1\}^{\N} \setminus X$. Um daraus eine Bijektion $g : [0,1) \rightarrow \{0,1\}^{\N}$ zu bauen, müssen wir die Lücken füllen, die $f$ lässt - also $X$.

Übungsaufgabe 3.3.4 Sei $Y := \{ a_1 a_2 a_3 \dots \in \{0,1\}^{\N} \ | \ \exists\ n \geq 1: a_i = 0 \ \forall i \geq n\}$ die Menge aller $0/1$-Folgen mit einem unendlichen Schweif von Nullen. Offensichtlich gilt $X \approx Y$.

Zeigen Sie, dass $Y \approx X \cup Y$ gilt.

Übungsaufgabe 3.3.5 Verwenden Sie die vorherige Übungsaufgabe, um $Y$ zu verdoppeln und somit eine Bijektion von $[0,1) \rightarrow \{0,1\}^{\N}$ zu konstruieren. Vielleicht hilft Ihnen folgendes Bild:

\(\square\)

Als nächstes zeigen wir, dass $\R \approx \R^2$ gilt. Dies ist schon erstaunlich: der Zahlenstrahl und die zweidimensionale Ebene sollen also gleichviele Elemente haben!

Aus der Funktion $f: \{0,1\}^{\N} \times \{0,1\}^{\N} \mapsto \{0,1\}^{\N}$ aus können wir eine (fast) bijektive Funktion $[0,1) \times [0,1) \rightarrow [0,1)$ bauen. Wir nehmen zwei Zahlen $0 \leq x,y \lt 1$, schreiben sie in Binärdarstellung und vereinigen sie dann per Reißverschlussverfahren zu einer Zahl, z.B.

Um herauszufinden, um welche Zahl es sich bei $z$ handelt, multiplizieren wir sie mit 64:

Sie erreicht alle Zahlen bis auf diejenigen mit einem unendlichen Schweif von Einsen. Sie ist hochgradig nichtstetig. Dennoch können wir versuchen, sie zu plotten:

Plot der (Fast-) Bijektion $f : [0,1) \times [0,1) \rightarrow [0,1)$. Ausgabewerte sind mit Farbwerten / Helligkeitswerten codiert. Grün/blass steht für niedrige Werte (nahe der 0), rot/kräftig für hohe (nahe der 1).

Als nächstes versuche ich, die Umkehrfunktion $f^{-1} : [0,1) \mapsto [0,1) \times [0,1)$ zu skizzieren. Das ist etwas schwierig, weil $f^{-1}$ nicht stetig ist. Was macht $f^{-1}(z)$? Sie betrachtet $z \in [0,1)$ in Binärdarstellung und dröselt dann die unendlich vielen Nachkommastellen auf. Die ungeraden bilden $x$, die geraden bilden $y$. Beispielsweise für $z = 1/7$ gilt

also $f^{-1}(1/7) = (2/7, 1/7)$.

Wenn wir also $z$ von $0$ nach $1$ wandern lassen, dann bewegt sich $f^{-1}(z)$ von links unten nach links oben, springt dann nach rechts unten und bewegt sich nach rechts oben. Grafisch stelle ich das wie folgt (und etwas unbeholfen) dar:

Beachten Sie, dass die Verbindungslinien zwischen den Kreisen Sprünge sind, also Unstetigkeitsstellen von $f^{-1}$. Innerhalb der Viertelintervalle (also z.B. innerhalb von $\left[\frac{1}{4}, \frac{1}{2}\right)$) sieht der Graph wieder ganz ähnlich aus. Hier sehen Sie die ersten paar Schritte dieser "Verfeinerung".

Wir wissen nun, dass $\R \approx \R^2$ gilt. Ebenso können wir $\R \approx \R^{k}$ für jedes $k \in \N^+$ zeigen. Wie sieht es aber mit $\R^{\N}$ aus? Das ist die Menge aller Funktionen $\phi: \N \rightarrow \R$ oder, etwas freundlicher formuliert, die Menge aller unendlichen Folgen reeller Zahlen: $r_1, r_2, r_3, \dots$.

Beweis. Da $\R \approx \cuben$ gilt, reicht es, zu zeigen, dass

$$ \begin{align*} \cuben \approx \left(\cuben\right)^{\N} \end{align*} $$

gilt. Interpretieren wir die rechte Seite: das sind unendliche Folgen von "Dingern", und jedes Ding ist wiederum eine unendliche Folge von 0/1. Wir können uns jedes Ding als (unendliche) Zeile vorstellen und erhalten somit eine in beiden Richtungen unendliche Tabelle. Wenn also $r_i$ eine unendliche $0/1$-Folge ist und und $r_{i,j}$ das $j$-te Bit der $i$-ten Folge, dann sieht unsere Tabelle so aus:

Wir wollen jetzt eine Bijektion $f : \cuben \times \cuben \rightarrow \cuben$ definieren. Dafür wenden wir den gleichen Trick an wie in dem Beweis, dass $\N \approx \N \times \N$ ist: wir zerlegen die Tabelle in Diagonalen und arbeiten jede separat ab:

Schließlich definieren wir unsere Folge $s_1 s_2 s_3 \dots \in \cuben$:

\(\square\)

Wir haben also die Beweisidee von $\N \times \N \approx \N$ recycelt. Diese Beobachtung motiviert den folgenden, etwas kurz angebundenen Beweis:

Dürfen wir das? Dürfen wir Rechenregeln wie $\left(x^{b}\right)^c = x^{b \cdot c}$ so einfach anwenden? Noch grundlegender, und das ist auch ein Punkt im ersten Beweis, den ich unter den Teppich gekehrt habe: Zwar wissen wir bereits, dass $\R \approx \cuben$. Folgt aber daraus bereits, dass $\R^\N \approx \left(\cuben\right)^\N$? Erstens also: dürfen wir mit Plus, Mal und Hoch wie gewohnt rechnen? Und dürfen wir in den resultierenden Ausdrücken equipotente Mengen austauschen?

Bevor wir das als Theorem formulieren, überlegen wir uns kurz, was denn die Analoga zu den arithmetischen Operationen sind. Am klarsten ist die Multiplikation: die Zahlenmultiplikation $a \cdot b$ hat als mengentheoretisches Analog das Cartesische Produkt $A \times B$, die Menge aller Paare $(x,y)$ mit $x \in A, y \in B$. Die Exponentiation $a^b$ hat als Analog $A^B$, die Menge aller Funktionen $\phi: B \rightarrow A$. Was ist das Analog zur Addition? Die Vereinigung $A \cup B$ wäre zu kurz gegriffen, weil ja zum Beispiel $\{1,2,3\} \cup \{4,5\}$ fünf Elemente hat, $\{1,2,3\} \cup \{1,2\}$ aber nur drei. Das "richtige" Analog ist die disjunkte Vereinigung $A \uplus B$, die die Elemente von $B$ erst einmal "markiert", um sie von denen von $A$ unterscheidbar zu machen. Somit wäre also $\{1,2,3\} \uplus \{1,2\} = \{1,2,3,1',2'\}$ eine Menge der Kardinalität 5. Formal kann man $A \uplus B$ so definieren;

Als zweites gilt, dass wir in so einem "mengentheoretisch-arithmetischen" Ausdruck eine Menge $A$ durch eine äquipotente Menge $A'$ ersetzen können:

Beachten Sie, dass ich Punkt 3 und 4 nicht zu einem Punkt zusammengefasst habe. Punkt 4 folgt nämlich nicht unmittelbar aus Punkt 3 sondern erfordert einen separaten Beweis.

Die Partialordnung $2^{\N}$.

Wir betrachten $2^{\N}$, die Potenzmenge von $\N$, also die Menge aller Teilmengen.

Die Elemente von $2^\N$, also Teilmengen $A \subseteq \N$, sind nach Inklusion geordnet: $A \subseteq B$. Somit ist $\left(2^{\N}, \subseteq\right)$ eine Partialordnung. Eine Kette in einer Partialordnung $(X, \preceq)$ ist eine Menge $Z$, in der alle Elemente paarweise vergleichbar sind. In diesem konkreten Beispiel heißt das: $Z \subseteq 2^{\N}$ und für alle $A, B \in Z$ gilt $A \subseteq B$ oder $B \subseteq A$. Erinnern Sie sich: $A$ und $B$ sind hier Mengen natürlicher Zahlen, und $Z$ ist eine Menge von Mengen natürlicher Zahlen. Eine Antikette in einer Partialordnung $(X,\preceq)$ ist eine Teilmenge $Z \subseteq X$, in der je zwei Elemente unvergleichbar sind. In diesem Beispiel heißt das: $Z \subseteq 2^N$, und für alle $A, B \in Z$ mit $A \ne B$ gilt $A \not \subseteq B$ und $B \not \subseteq A$. Hier ist ein Beispiel für eine unendliche Kette:

Diese Kette hat zufälligerweise die Form $A_0 \subseteq A_1 \subseteq A_2 \subseteq \dots$, d.h., die Elemente der Kette sind schön sortiert, von klein nach groß. Dies muss nicht so sein: sei $k \N := \{ k\cdot i \ | \ i \in \N\}$ die Menge der Vielfachen von $k$. Dann gilt $1 \N \supseteq 2 \N \supseteq 4\N \supseteq 8\N \supseteq \dots$, die Elemente sind also in "absteigender" Reihenfolge sortiert. Beide Beispiele haben einen "Anfangspunkt". Das muss aber nicht so sein: sei $[k] := \{1,2,\dots,k\}$.

Wenn wir ganz links noch $\{0\}$ hinschreiben und ganz rechts noch $\N$, dann haben wir ein weiteres, eventuell ungewohntes Phänomen: das Element $\{0\}$ in der Kette hat keinen eindeutigen Nachfolger. Egal, welches $A$ mit $\{0\} \subsetneq A$ Sie wählen, sie finden immer noch ein $B$ dazwischen: $\{0\} \subsetneq B \subsetneq A$.

Ein klassisches Beispiel für eine dichte Ordnung ist $(\Q, \lt)$. Wenn $x \lt z$, dann ist $x \lt \frac{x+z}{2} \lt z$. Sie finden also immer etwas dazwischen. Die Ordnung $(\Z, \lt)$ ist nicht dicht: zwischen $7$ und $8$ finden Sie nichts. Die Partialordnung $(2^\N, \subseteq)$ ist nicht dicht: es gilt $\{2\} \subsetneq \{2,3\}$, aber es gibt keine Menge zwischen den beiden.