3.4 Die Cantorsche Diagonalisation: $N ≉ R$

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 3.4.1 (Überabzählbarkeit der reellen Zahlen). $N ≉ R$ .

Beweis. Da wir bereits $R \approx {0, 1}^{N}$ gesehen haben, reicht es, $N ≉ {0, 1}^{N}$ zu zeigen. Wir müssen also zeigen, dass es keine Bijektion $f : N \to {0, 1}^{N}$ gibt. Wie gehen wir vor? Wir nehmen an, man hätte uns eine Funktion $f : N \to {0, 1}^{N}$ 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 $b = b_{0} b_{1} b_{2} b_{3} \dots \in {0, 1}^{N}$ finden, die nicht im Wertebereich (Englisch: image) von $f$ liegt: $b \notin i m g (f)$ . Was wiederum bedeutet, dass für jedes $n \in N$ sich die unendliche 0/1-Folge $f (n)$ von $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: $d := \overset{―}{f_{0, 0}} \overset{―}{f_{1, 1}} \overset{―}{f_{2, 2}} \overset{―}{f_{3, 3}} \dots$ . Vergleichen wir nun $d$ mit einer Zeile $f_{n}$ der obigen Tabelle. Insbesondere, die $n$ -ten Stellen der beiden Folgen. Die $n$ -te Stelle von $d$ ist $\overset{―}{f_{n, n}}$ ; die $n$ -te Stelle von $f_{n}$ ist $f_{n, n}$ . Wir sehen also: $d$ und $f_{n}$ unterscheiden sich an der $n$ -ten Stelle (und womöglich auch noch anderswo), und daher gilt: $d \neq f_{n}$ . Da dies für jedes $n$ gilt, folgern wir: die Folge $d$ kommt nicht als Zeile der Tabelle vor, und damit $d \notin i m g (f)$ . Die Funktion $f$ ist nicht surjektiv. $◻$

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 3.4.1 Zeigen Sie, dass es zu der Funktion $f : N \to {0, 1}^{N}$ eine Folge $d$ gibt, die nicht nur nicht in $i m g (f)$ ist, sondern noch mehr: jede Folge $f_{n}$ unterscheidet sich von $d$ in unendlich vielen Stellen.

Übungsaufgabe 3.4.2 Zeigen Sie ganz allgemein: für jede Menge $A$ gilt $A ≉ 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 3.4.3 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 3.4.4 Zeigen Sie, dass es in $(2^{N}, \subseteq)$ eine Kette $X$ mit $X \approx R$ gibt.

3.4 Die Cantorsche Diagonalisation: N≉R

3.4 Die Cantorsche Diagonalisation: $N ≉ R$