Überabzählbar

Unendliche Mengen, die nicht abzählbar sind, heißen überabzählbar. Georg Cantor bewies 1873, dass die Menge R der reellen Zahlen überabzählbar ist. 1877 gab er einen weiteren Beweis hierfür an, der als "Cantors zweites Diagonalargument" bekannt ist und der die Dezimalbruchdarstellung der reellen Zahlen verwendet. (Cantors erstes Diagonalargument bezieht sich auf die Abzählbarkeit von Q.)

Jede reelle Zahl zwischen 0 und 1 hat eine eindeutige Darstellung als unendlicher Dezimalbruch der Form 0,... (statt der endlichen Dezimalbrüche verwende man die äquivalente unendliche Darstellung mit Periode 9, also zum Beispiel 0,4999... statt 0,5). 

Vor diesem Hintergrund verläuft Cantors Beweis so: Man nimmt an, die Menge I aller reellen Zahlen zwischen 0 und 1 wäre durch eine Abzählung gegeben und konstruiert aus den Dezimalbrüchen der Zahlen in dieser Abzählung eine neue reelle Zahl, die zwar ebenfalls zwischen 0 und 1 liegt, die aber unmöglich in der Abzählung vorkommen kann. Also muss die Annahme falsch sein. Also kann die Menge der reellen Zahlen zwischen 0 und 1 und damit erst recht die Menge aller reellen Zahlen nicht abzählbar sein.

Etwas genauer ist das Argument in der folgenden Abbildung dargestellt:

Die eindeutige Dezimalbruchentwicklung von r unterscheidet sich von jedem der aufgeführten Dezimalbrüche an mindestens einer Stelle (der jeweiligen "Diagonalstelle"). Daher kommt r in der Abzählung nicht vor – im Widerspruch zur Annahme. Also ist I überabzählbar.