Vielleicht war es überraschend zu sehen, dass $\N = \Q$ gilt, dass also das "diskrete" $\N$ und das "dichte" $\Q$ sicht hinsichtlich ihrer Größe (Fachsprache: Kardinalität) nicht unterscheiden. Könnte es denn sein, dass jede unendliche Menge $A$ abzählbar ist, also $A \approx \N$? Die Antwort ist ein klares Nein.

Theorem (Überabzählbarkeit der reellen Zahlen). $\N \not \approx \R$.

Beweis. Da wir bereits $\R \approx \{0,1\}^{\N}$ gesehen haben, reicht es, $\N \not \approx \{0,1\}^{\N}$ zu zeigen. Wir müssen also zeigen, dass es keine Bijektion $f : \N \rightarrow \{0,1\}^{\N}$ gibt. Wie gehen wir vor? Wir nehmen an, man hätte uns eine Funktion $f : \N \rightarrow \cuben$ gegeben, und müssen nun zeigen, dass $f$ nicht bijektiv ist. Nicht bijektiv kann zwei Ding heißen: nicht injektiv und nicht surjekiv. Injektiv kann eine solche Funktion natürlich sein, beispielsweise die Funktion $n \mapsto 0^n 111111\dots$. Also ist unsere einzige Chance, zu zeigen, dass $f$ nicht surjektiv ist. Wir müssen also eine 0/1-Folge $\mathbf{b} = b_0 b_1 b_2 b_3 \dots \in \{0,1\}^{\N}$ finden, die nicht im Wertebereich (Englisch: image) von $f$ liegt: $\mathbf{b} \not \in {\rm img}(f)$. Was wiederum bedeutet, dass für jedes $n \in \N$ sich die unendliche 0/1-Folge $f(n)$ von $\mathbf{b}$ unterscheidet, also an mindestens einer Stelle.

Wie können wir die Funktion $f$ darstellen? Jedes $f(n)$ ist eine unendliche $0/1$-Folge. Also können wir uns $f$ als nach rechts und nach unten unendliche Tabelle vorstellen. Hierbei schreiben wir $f_i$ für $f(i)$ und $f_{i,j}$ für das $j$-te Glied der unendlichen Folge $f_i$.

Für ein Bit $b \in \{0,1\}$ bezeichnen wir mit $\bar{b}$ seine Negation: $\bar{b} = 1 - b$. Wir betrachten jetzt die Diagonale der Tabelle und negieren sie:

und erhalten eine Folge: $\mathbf{d} := \overline{f_{0,0}}\ \overline{f_{1,1}}\ \overline{f_{2,2}} \ \overline{f_{3,3}}\dots$. Vergleichen wir nun $\mathbf{d}$ mit einer Zeile $f_n$ der obigen Tabelle. Insbesondere, die $n$-ten Stellen der beiden Folgen. Die $n$-te Stelle von $\mathbf{d}$ ist $\overline{f_{n,n}}$; die $n$-te Stelle von $f_n$ ist $f_{n,n}$. Wir sehen also: $\mathbf{d}$ und $f_n$ unterscheiden sich an der $n$-ten Stelle (und womöglich auch noch anderswo), und daher gilt: $\mathbf{d} \ne f_n$. Da dies für jedes $n$ gilt, folgern wir: die Folge $\mathbf{d}$ kommt nicht als Zeile der Tabelle vor, und damit $\mathbf{d} \not \in {\rm img}(f)$. Die Funktion $f$ ist nicht surjektiv.$\square$

Weil in dem Beweis die Diagonale der Tabelle eine entscheidende Rolle spielt, nennt man diese Beweistechnik auch das Cantorsche Diagonalisierungsverfahren. Dies wird später, in Kapitel 7 über Turingmaschinen und in Kapitel ? über Komplexitätstheorie eine Rolle spielen, wenn wir z.B. zeigen wollen, dass es Probleme gibt, an denen jedes Computerprogram versagt.

Übungsaufgabe Zeigen Sie, dass es zu der Funktion $f: \N \rightarrow \cuben$ eine Folge $\mathbf{d}$ gibt, die nicht nur nicht in ${\rm img}(f)$ ist, sondern noch mehr: jede Folge $f_n$ unterscheidet sich von $\mathbf{d}$ in unendlich vielen Stellen.

Übungsaufgabe Zeigen Sie ganz allgemein: für jede Menge $A$ gilt $A \not \approx 2^A$. Erinnerin Sie sich: $2^A$ ist die Potenzmenge von $A$, also die Menge aller Untermengen.

Tipp: Sie müssen den obigen Beweis auf die richtige Weise abstrahieren, dann geht es ganz einfach.

Die letzte Übung zeigt also: es gibt immer größere Mengen, ein oberes Ende wird nie erreicht.

Übungsaufgabe Erinnern Sie sich an die Partialordnung $(2^\N, \subseteq)$. Zeigen Sie, dass es in dieser Ordnung eine Antikette $X$ mit $X \approx \R$ gibt.

Übungsaufgabe Zeigen Sie, dass es in $(2^\N, \subseteq)$ eine Kette $X$ mit $X \approx \R$ gibt.