Cantors erstes Diagonalargument

Cantors erstes Diagonalargument ist ein mathematisches Beweisverfahren, mit dem man gegebenenfalls zeigen kann, dass zwei unendliche Mengen gleichmächtig sind.

Entwickelt wurde dieses Verfahren von Georg Cantor.

Zum Verständnis der Problematik und des Beweises ist es notwendig, die unspezifizierte Größe einer Menge durch die in der Mengenlehre formal definierte Mächtigkeit zu ersetzen:

Zwei Mengen sind genau dann gleichmächtig, wenn jedem Element der einen Menge genau ein Element der anderen Menge zugeordnet werden kann, und umgekehrt ebenso, wenn also eine Bijektion zwischen den Mengen existiert.

Während dies bei Mengen mit endlich vielen Elementen klar ist ({1,2,3} und {6,8,10} sind gleichmächtig), wird bei Mengen mit unendlich vielen Elementen die Problematik offensichtlich.

Beispielsweise sind die Menge der natürlichen Zahlen und die Menge der positiven geraden Zahlen gleichmächtig, denn man kann umkehrbar eindeutig jeder natürlichen Zahl i ihr Doppeltes 2·i zuordnen, obwohl die positiven geraden Zahlen echt in den natürlichen Zahlen enthalten sind.

Vorgehen bei Cantors erstem Diagonalargument

Cantors Verfahren wird am besten mit der einfachsten unendlich großen Menge, der Menge der natürlichen Zahlen, und der Menge der positiven Brüche veranschaulicht. Die Aussage ist, dass die Menge $\mathbb {N}$ der natürlichen Zahlen und die Menge $\mathbb{Q^+}$ der positiven rationalen Zahlen gleichmächtig sind.

Dies lässt sich zeigen, indem man die Brüche folgendermaßen in einem zweidimensionalen Schema anordnet:

$\begin{array}{cccccccccc} \tfrac 11 & & \tfrac 12 & & \tfrac 13 & & \tfrac 14 & & \tfrac 15 & \cdots \\ & & & & & & & & & \\ \tfrac 21 & & \tfrac 22 & & \tfrac 23 & & \tfrac 24 & & \tfrac 25 & \cdots \\ & & & & & & & & & \\ \tfrac 31 & & \tfrac 32 & & \tfrac 33 & & \tfrac 34 & & \tfrac 35 & \cdots \\ & & & & & & & & & \\ \tfrac 41 & & \tfrac 42 & & \tfrac 43 & & \tfrac 44 & & \tfrac 45 & \cdots \\ & & & & & & & & & \\ \tfrac 51 & & \tfrac 52 & & \tfrac 53 & & \tfrac 54 & & \tfrac 55 & \cdots \\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \\ \end{array}$

Dieses Schema zählt man dann diagonal ab, wobei man nicht vollständig gekürzte Brüche überspringt:

$\begin{array}{lclclclclc} \tfrac 11\ _{\color{Blue} (1)} & {\color{MidnightBlue}\rightarrow} & \tfrac 12\ _{\color{Blue} (2)} & & \tfrac 13\ _{\color{Blue} (5)} & {\color{MidnightBlue}\rightarrow} & \tfrac 14\ _{\color{Blue} (6)} & & \tfrac 15\ _{\color{Blue} (11)} & {\color{MidnightBlue}\rightarrow} \\ & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & \\ \tfrac 21\ _{\color{Blue} (3)} & & \tfrac 22\ _{\color{Blue} (\cdot)} & & \tfrac 23\ _{\color{Blue} (7)} & & \tfrac 24\ _{\color{Blue} (\cdot)} & & \tfrac 25 & \cdots \\ {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\nearrow} & & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & & & \\ \tfrac 31\ _{\color{Blue} (4)} & & \tfrac 32\ _{\color{Blue} (8)} & & \tfrac 33\ _{\color{Blue} (\cdot)} & & \tfrac 34 & & \tfrac 35 & \cdots \\ & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & & & & & \\ \tfrac 41\ _{\color{Blue} (9)} & & \tfrac 42\ _{\color{Blue} (\cdot)} & & \tfrac 43 & & \tfrac 44 & & \tfrac 45 & \cdots \\ {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\nearrow} & & & & & & & & \\ \tfrac 51\ _{\color{Blue} (10)} & & \tfrac 52 & & \tfrac 53 & & \tfrac 54 & & \tfrac 55 & \cdots \\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \\ \end{array}$

Man erhält auf diese Weise eine Abzählung der positiven rationalen Zahlen:

$\begin{array}{cccccccccccccccc} {\color{Blue} 1} & {\color{Blue} 2} & {\color{Blue} 3} & {\color{Blue} 4} & {\color{Blue} 5} & {\color{Blue} 6} & {\color{Blue} 7} & {\color{Blue} 8} & {\color{Blue} 9} & {\color{Blue} 10} & {\color{Blue} 11} & {\color{Blue} \cdots} \\[3pt] {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} \\[3pt] 1 & \tfrac 12 & 2 & 3 & \tfrac 13 & \tfrac 14 & \tfrac 23 & \tfrac 32 & 4 & 5 & \tfrac 15 & \cdots \\ \end{array}$

Durch das Überspringen kürzbarer Brüche liegt für jede positive rationale Zahl genau ein Repräsentant (der nicht mehr kürzbare Bruch) in dieser Abzählung, wodurch die gewünschte Bijektion hergestellt ist.

Um die Gleichmächtigkeit aller rationalen Zahlen und der natürlichen Zahlen zu zeigen, erweitert man diese Abzählung. Vor die Eins fügt man eine Null ein und hinter jeder Zahl deren Negatives:

$\begin{array}{cccccccccccccccc} {\color{Blue} 1} & {\color{Blue} 2} & {\color{Blue} 3} & {\color{Blue} 4} & {\color{Blue} 5} & {\color{Blue} 6} & {\color{Blue} 7} & {\color{Blue} 8} & {\color{Blue} 9} & {\color{Blue} 10} & {\color{Blue} 11} & {\color{Blue} 12} & {\color{Blue} 13} & {\color{Blue} 14} & {\color{Blue} 15} & {\color{Blue} \cdots} \\[3pt] {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} \\[3pt] 0 & 1 & -1 & \tfrac 12 & -\tfrac 12 & 2 & -2 & 3 & -3 & \tfrac 13 & -\tfrac 13 & \tfrac 14 & -\tfrac 14 & \tfrac 23 & -\tfrac 23 & \cdots \\ \end{array}$

Man erhält damit eine Bijektion zwischen der Menge der natürlichen Zahlen und der Menge der rationalen Zahlen, was bedeutet, dass diese beiden Mengen gleichmächtig sind. Diese Aussage zählt zu den wichtigsten mathematischen Sätzen.

Mengen, welche gleichmächtig zur Menge der natürlichen Zahlen sind, heißen abzählbar (oder abzählbar unendlich). Mengen, welche gleichmächtig zu irgendeiner Teilmenge der natürlichen Zahlen sind, heißen höchstens abzählbar (manche bezeichnen das auch als abzählbar). Mengen, welche gleichmächtig zu einer beschränkten Teilmenge der natürlichen Zahlen sind, sind endlich. Die Menge der rationalen Zahlen ist also abzählbar.

Mächtigkeit der reellen Zahlen

Die Menge $\mathbb {R}$ der reellen Zahlen ist zur Menge der natürlichen Zahlen nicht gleichmächtig, deshalb ist die Menge $\mathbb {R}$ überabzählbar. Man sagt auch, die reellen Zahlen haben die Mächtigkeit des Kontinuums.

Der Beweis der Überabzählbarkeit von $\mathbb {R}$ ist Inhalt des zweiten Cantorschen Diagonalbeweises.

Verallgemeinerung des ersten Cantorschen Diagonalargumentes

Das erste Cantorsche Diagonalargument kann man verallgemeinern, um vergleichbare Aussagen über Mengen von Tupeln reeller Zahlen zu machen.

Die folgende Darstellung ist nicht das traditionelle ‚erste Cantor-Diagonalargument‘, sondern eher eine Vorschrift zum Erstellen eines ‚fraktalen‘ Objektes.

Georg Cantor hat gezeigt, dass es Kurven (1-dimensionale Objekte) gibt, die Flächen (2-dimensionale Objekte) füllen können, und zwar so:

Man nehme eine quadratische Fläche, die durch die Eckpunkte (0,0) und (3,3) aufgespannt ist. Man ziehe eine Strecke von (0,0) nach (3,3).

Visualisierung der Cantor-Diagonalisierung
Im Bild rechts ist der Kurvenverlauf durch Abstand in den Berührungspunkten verdeutlicht, wie in ausreichender Vergrößerung sichtbar wird

Diese Kurve innerhalb des Quadrates ändere man nun so ab: Man teile die quadratische Fläche in ein Raster von neun gleich großen Quadraten. Man ändere den Kurvenverlauf nun so ab, dass folgende Punkte die Endpunkte von Teilstrecken bilden:

(0,0) – (1,1) – (0,2) – (1,3) – (2,2) – (1,1) – (2,0) – (3,1) – (2,2) – (3,3)

Die abgeänderte Kurve hat die Eigenschaft, dass sie ebenfalls das Quadrat durchzieht und denselben Anfangs- und denselben Endpunkt hat.

Dieses Verfahren wiederhole man nun für jedes der kleinen Teil-Quadrate, und die daraus entstandenen Teil-Quadrate und so weiter. Der Grenzwert dieses Verfahrens ist eine Kurve, die das gesamte Quadrat ausfüllt.

Diese (unendlich lange) Grenzkurve ist Bild einer stetigen Abbildung φ des Intervalls [0, 1]. Dazu setzt man zunächst die Endpunkte φ(0) = (0,0), φ(1) = (3,3). Im zweiten Schritt setzt man die Eckpunkte der ersten Verfeinerung:

0	→	(0,0)
1/9	→	(1,1)
2/9	→	(0,2)
3/9	→	(1,3)
4/9	→	(2,2)
5/9	→	(1,1)
6/9	→	(2,0)
7/9	→	(3,1)
8/9	→	(2,2)
1	→	(3,3)

Dann setzt man in jedem Schritt die hinzukommenden Eckpunkte auf Werte zwischen den bisherigen Zahlen. Die Grenzkurve ist dann genau das Bild der so definierten Abbildung φ. Beachte, dass dies keine Bijektion von [0, 1] auf [0,3]×[0,3] ist, da die Abbildung zwar surjektiv, aber nicht injektiv ist; z.B. ist φ(1/9) = φ(5/9).

Während die Zahl eindimensional ist, sind die zugehörigen Koordinaten zweidimensional. Folglich kann man eindimensionale Zahlen in mehrdimensionale Zahlen überführen und umgekehrt. Mengen mehrdimensionaler Elemente sind somit nicht mächtiger als Mengen eindimensionaler Elemente.

Siehe auch

Cantorsche Paarungsfunktion

Basierend auf einem Artikel in:

Wikipedia.de