Cantors zweites Diagonalargument

Das folgende Beispiel verwendet zwei der einfachsten unendlichen Mengen, die der natürlichen Zahlen und die der positiven Brüche. Die Idee ist, zu zeigen, dass diese beiden Mengen, N {\darstellungsstil \mathbb {N} } und Q + {\displaystyle \mathbb {Q^{+}} } haben die gleiche Kardinalität.

Zunächst werden die Brüche wie folgt in einem Array ausgerichtet:

1 1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 2 2 3 2 4 2 5 ⋯ 3 1 3 2 3 3 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 5 5 ⋯ 5 1 5 2 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccccccc}{\tfrac {1}{1}}}&{\tfrac {1}{2}}&&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\&&&&&&&&\\{\tfrac {\tfrac {2}{1}}}&&{\tfrac {2}{2}}&&&{\frac {2}{3}}&&{\frac {2}{4}}&&{\frac {2}{5}}&\cdots \\\&&&&&&&&\\\{\frac {\3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\\&&&&&&&&&\\\{\tfrac {4}{1}}&&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&&{\tfrac {4}{4}}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}\cdots \\&&&&&&&&\\\{\tfrac {5}{1}}&&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&&{\tfrac {5}{4}&&{\tfrac {5}{\5}&\cdots \\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\\end{array}}

Als nächstes werden die Zahlen gezählt, wie gezeigt. Bruchteile, die vereinfacht werden können, werden weggelassen:

1 1   ( 1 ) → 1 2   ( 2 ) 1 3   ( 5 ) → 1 4   ( 6 ) 1 5   ( 11 ) → ↙  ↙  2 1   ( 3 ) 2 2   ( ⋅ ) 2 3   ( 7 ) 2 4   ( ⋅ ) 2 5 ⋯ ↓  ↙  3 1   ( 4 ) 3 2   ( 8 ) 3 3   ( ⋅ ) 3 4 3 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 4 5 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 3 5 4 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\Anzeigestil {\Begin{Array}{lclclclc}{\tfrac {1}{1}}}\ _{\Farbe {Blau}(1)}&{\Farbe {MidnightBlue}\rechterPfeil }&{\tfrac {1}{2}}\ _{\Farbe {Blau}(2)}&&{\tfrac {1}{3}}\ _{\Farbe {Blau}(5)}&{\farbig {MidnightBlue}\rechter Pfeil }&{\tfrac {1}{4}}\ _{\farbig {Blue}(6)}&&{\tfrac {1}{5}}\ _{\farbig {Blue}(11)}&{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\schwarzer Pfeil }&&&{\color {MidnightBlue}\naher Pfeil }&&\\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\farbe {Blau}(\cdot )}&&&{\tfrac {2}{3}}\ _{\farbe {Blau}(7)}&&{\tfrac {2}{4}}}\ _{\farbe {Blau}(\cdot )}&{\tfrac {2}{5}&\cdots \\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&{\color {MidnightBlue}\pfeil }&&{\color {MidnightBlue}\nearrow }&&&&\\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}{3}}}\ _{\color {Blue}(\cdot )}&&{\tfrac {3}{4}}&&&{\tfrac {3}{5}&\cdots \\&{\color {MidnightBlue}\schwarzer Pfeil }&&{\color {MidnightBlue}\naher Pfeil }&&&&&&\\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {4}{3}}&&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\{\frac {5}{1}}\ _{\farbe {Blau}(10)}&&{\frac {5}{2}}&&{\frac {5}{3}}}&&&{\frac {5}{4}}&{\tfrac {5}{5}&\cdots {\\\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\\end{array}}}

Auf diese Weise werden die Fraktionen gezählt:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 4 2 3 3 3 2 4 5 1 5 ⋯ {\Anzeigestil {\Beginn{Anordnung}{cccccccccccccccccccccccc}{\Farbe {Blau}1}&{\Farbe {Blau}2}&{\Farbe {Blau}3}&{\Farbe {Blau}4}&{\Farbe {Blau}5}&{\Farbe {Blau}6&{\Farbe {Blau}7&{\Farbe {Blau}8&{\Farbe {Blau}9&{\Farbe {Blau}9&{\Farbe {Blau}10&{\Farbe {Blau}11&&}{\Farbe {Blau}Punkte {3pt]{\Farbe {MidnightBlue}\downarrow }&{\Farbe {MidnightBlue}\downarrow }&{\Farbe {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 {1}{2}}}&2&3&{\frac {1}{3}&{\frac {1}{4}}&{\frac {2}{3}}&{\frac {\frac {3}{2}}&4&5&{\frac {1}{5}}&\cdots {\\\\\}end{array}}

Durch das Weglassen von Brüchen, die noch vereinfacht werden können, entsteht eine Bijektion, die jedes Element der natürlichen Zahlen einem Element der Brüche zuordnet:

Um zu zeigen, dass alle natürlichen Zahlen und die Brüche die gleiche Kardinalität haben, muss das Element 0 addiert werden; nach jedem Bruch wird sein Negativ addiert;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 1 2 - 1 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\Anzeigestil {\Beginn{Anordnung}{cccccccccccccccccccccccccc}{\Farbe {Blau}1}&{\farbig {Blau}2}&{\farbig {Blau}3}&{\farbig {Blau}4}&{\farbig {Blau}5}&{\farbig {Blau}6}&{\farbig {Blau}7}&{\Farbe {Blau}8&{\Farbe {Blau}9&{\Farbe {Blau}10&{\Farbe {Blau}11&{\Farbe {Blau}11}&{\Farbe {Blau}12&{\Farbe {Blau}13&{\Farbe {Blau}14&{\Farbe {Blau}15}&{\Farbe {Blau}Punkte {3pt]{\Farbe {MidnightBlue}\Pfeil nach unten }&{\Farbe {MidnightBlue}\Pfeil nach unten }&{\Farbe {MidnightBlue}\Pfeil nach unten }&{\Farbe {MidnightBlue}\Pfeil nach unten }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\Farbe {MidnightBlue}\Pfeil abwärts }&&{\Farbe {MidnightBlue}\Pfeil abwärts }&{\Farbe {MidnightBlue}\Pfeil abwärts }&&{\Farbe {MidnightBlue}\Pfeil abwärts }&&{\Farbe {MidnightBlue}\Pfeil abwärts }&{\Farbe {MidnightBlue}\Pfeil nach unten }&{\Farbe {MidnightBlue}\Pfeil nach unten }&{\Farbe {MidnightBlue}\Pfeil nach unten }\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&2&-2&3&-3&{\frac {1}{3}}&-{\frac {1}{3}}&{\frac {1}{4}}&-{\frac {1}{4}}&{\frac {2}{3}}&-{\frac {2}{3}}&\ccdots \\\\\end{array}}}

Auf diese Weise gibt es eine vollständige Bijektion, die jeder natürlichen Zahl einen Bruchteil zuordnet. Mit anderen Worten: beide Mengen haben die gleiche Kardinalität. Heute nennt man Mengen, die die gleiche Anzahl von Elementen haben wie die Menge der natürlichen Zahlen, abzählbar. Mengen, die weniger Elemente haben als die Menge der Natürlichen Zahlen, werden höchstens als abzählbar bezeichnet. Mit dieser Definition ist die Menge der rationalen Zahlen/Bruchteile abzählbar.

Unendliche Mengen haben oft Eigenschaften, die gegen die Intuition verstoßen: David Hilbert zeigte dies in einem Experiment, das Hilberts Paradoxon des Grand Hotels genannt wird.

Die Menge der reellen Zahlen hat nicht die gleiche Kardinalität wie die der natürlichen Zahlen; es gibt mehr reelle Zahlen als natürliche Zahlen. Die oben skizzierte Idee beeinflusste seinen Beweis. In seinem Artikel von 1891 betrachtete Cantor die Menge T aller unendlichen Folgen von Binärziffern (d.h. jede Ziffer ist null oder eins).

Er beginnt mit einem konstruktiven Beweis für das folgende Theorem:

Wenn s1, s2, ... , _sn, ... eine beliebige Aufzählung von Elementen aus T ist, dann gibt es immer ein Element s von T, das keinem _sn in der Aufzählung entspricht.

Um dies zu beweisen, gibt es eine Aufzählung von Elementen aus T, wie z.B.

Die Sequenz s wird konstruiert, indem die erste Ziffer als komplementär zur ersten Ziffer von s1 gewählt wird (Vertauschung von 0s für 1s und umgekehrt), die zweite Ziffer als komplementär zur zweiten Ziffer von s2, die dritte Ziffer als komplementär zur dritten Ziffer von s3 und generell für jedes n die n-te Ziffer als komplementär zur n-ten Ziffer von _sn. Im Beispiel ergibt dies:

Durch die Konstruktion unterscheidet sich s von jedem _sn, da ihre n-ten Stellen unterschiedlich sind (im Beispiel hervorgehoben). Daher kann s in der Aufzählung nicht vorkommen.

Basierend auf diesem Satz verwendet Cantor dann einen Beweis durch Widerspruch, um dies zu zeigen:

Die Menge T ist nicht abzählbar.

Er geht im Widerspruch dazu davon aus, dass T zählbar war. In diesem Fall könnten alle seine Elemente als eine Aufzählung s1, s2, ... , _sn, ... geschrieben werden. Die Anwendung des vorhergehenden Satzes auf diese Aufzählung würde eine Sequenz s ergeben, die nicht zu dieser Aufzählung gehört. s war jedoch ein Element von T und sollte daher in der Aufzählung enthalten sein. Dies widerspricht der ursprünglichen Annahme, so dass T nicht abzählbar sein muss.