Überabzählbare Menge

Eine Menge heisst überabzählbar, wenn sie nicht abzählbar ist, wenn es also keine bijektive_Abbildung von der Menge auf die Menge der natürlichen Zahlen gibt. Um zu zeigen, dass eine Menge abzählbar ist, reicht es, eine Liste anzugeben, welche alle Elemente der Menge enthält. Diese Liste kann auch unendlich lang sein, z. B. wenn ich die geraden Zahlen einfach der Reihe nach aufschreibe.

Georg_Cantor hat mit der Cantor-Diagonalisierung gezeigt, wie man solch eine Liste für die Menge der Brüche erstellt. Durch Widerspruch zeigte er, dass es für die reellen Zahlen keine solche Liste gibt.

Cantor nimmt zuerst einmal an, er habe eine Liste, die alle reellen Zahlen zwischen 0 und 1 enthält. Er zeigt dann, dass es mindestens eine Zahl gibt, die nicht in der Liste vorkommt. Dies ist ein Widerspruch zur Annahme. Deshalb kann es keine Liste solche geben.

Cantors Liste sieht so aus:

$z_{1}$ = 0, $a_{11}$ $a_{12}$ $a_{13}$...

$z_{2}$ = 0, $a_{21}$ $a_{22}$ $a_{23}$...

$z_{3}$ = 0, $a_{31}$ $a_{32}$ $a_{33}$...

$z_{4}$ = ...

...

Hier sind die $z_{x}$ reelle Zahlen und die $a_{ij}$ Dezimalstellen dieser reellen Zahlen.

Nun konstruiert Cantor eine reelle Zahl x zwischen 0 und 1, die nicht in der Liste vorkommt. Dazu geht er von oben nach unten alle Zahlen durch. Jede Zahl der Liste definiert eine Dezimalstelle von x. Wenn $a_{11}$ = 5 ist, setzt Cantor $x_{1}$ = 0, sonst ist $x_{1}$ = 5. Mit dieser Definition ist sichergestellt, dass sich x eine andere Zahl ist als $z_{1}$. Wenn $a_{22}$ = 5 ist, setzt Cantor $x_{2}$ = 0, sonst ist $x_{2}$ = 5. Mit dieser Definition ist sichergestellt, dass sich x eine andere Zahl ist als $z_{2}$.

So geht Cantor diagonal durch die ganze Liste und erhält eine Zahl, die sich von allen Zahlen in der Liste unterscheidet. Die Liste enthält also nicht alle reellen Zahlen zwischen 0 und 1. Da man dies für jede Liste machen könnte, ist bewiesen, dass sich reelle Zahlen nicht vollständig auflisten lassen. Sie sind also überabzählbar.

Auf ähnliche Weise kann auch gezeigt werden, dass auch die Menge aller Teilmengen einer Menge M, die so genannte Potenzmenge von M überabzählbar ist, wenn M unendlich viele Elemente hat. Es gibt also verschiedene Klassen von Unendlichkeit.