Überabzählbare Menge

Eine Menge heißt überabzählbar, wenn ihre Mächtigkeit echt größer als die der natürlichen Zahlen ist. Eine überabzählbare Menge ist nicht endlich oder abzählbar, es gibt also keine bijektive Abbildung von der Menge auf irgendeine Teilmenge der natürlichen Zahlen.

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 eine unendlich lange Folge sein, z. B. wenn man die geraden Zahlen einfach der Reihe nach aufschreibt.

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.

Beweis der Überabzählbarkeit der reellen Zahlen

Cantors hier präsentierter Beweis der Überabzählbarkeit der reellen Zahlen wird auch Cantors zweites Diagonalargument genannt. Das erste Diagonalargument ist der Beweis der Abzählbarkeit der rationalen Zahlen.

Im Gegensatz zur allgemeinen Meinung ist dieser Beweis nicht Cantors erster Beweis der Überabzählbarkeit der reellen Zahlen, sondern wurde drei Jahre nach seinen ersten Beweis veröffentlicht. Der erste Beweis arbeitet mit anderen Eigenschaften der reellen Zahlen, und kommt ganz ohne ein Zahlensystem aus.

Der Beweis:

Wir nehmen zuerst einmal an, es gäbe eine Folge, die alle reellen Zahlen im Intervall [0, 1] enthält. Dann werden wir zeigen, dass es mindestens eine Zahl zwischen 0 und 1 gibt, die nicht in der Folge vorkommt. Dies ist ein Widerspruch zur Annahme. Deshalb kann es keine solche Folge geben.

Die Zahlen in dieser als gegeben vorausgesetzten Folge sehen in ihrer Dezimalbruch-Entwicklung so aus:

z₁ = 0, a₁₁ a₁₂ a₁₃ ...

z₂ = 0, a₂₁ a₂₂ a₂₃ ...

z₃ = 0, a₃₁ a₃₂ a₃₃ ...

z₄ = ...

...

Hier sind die z_i reelle Zahlen und die $a_{ij}$ Dezimalstellen dieser reellen Zahlen. Die Diagonalelemente sind hervorgehoben, aus diesen konstruieren wir eine neue Zahl.

Nun konstruieren wir eine reelle Zahl x zwischen 0 und 1, die nicht in der Folge vorkommt. Dazu gehen wir von oben nach unten alle Zahlen durch.

Jede Zahl $z_{i}$ der Folge definiert auf folgende Weise eine Dezimalstelle $x_{i}$ von x.
Wenn $a_{11}$ = 5 ist, setzen wir $x_{1}$ = 0, sonst $x_{1}$ = 5. Mit dieser Definition ist sichergestellt, dass x eine andere Zahl ist als $z_{1}$.
Wenn $a_{22}$ = 5 ist, setzen wir $x_{2}$ = 0, sonst $x_{2}$ = 5. Mit dieser Definition ist sichergestellt, dass x eine andere Zahl ist als $z_{2}$.
So gehen wir durch die ganze Folge und erhalten eine Zahl x, die sich von allen Zahlen in der Folge unterscheidet.

Die Folge enthält also nicht alle reellen Zahlen zwischen 0 und 1. Da aber vorausgesetzt wurde, dass die gegebene Folge alle reellen Zahlen zwischen 0 und 1 enthält, haben wir einen Widerspruch erzeugt. Es kann also keine Folge alle reellen Zahlen zwischen 0 und 1 enthalten. Das Intervall [0, 1] ist deshalb überabzählbar. Damit ist auch ganz R überabzählbar.

Andere Sprachen: English

Vergleich der Mächtigkeit einer Menge und ihrer Potenzmenge

Auf ähnliche Weise kann gezeigt werden, dass auch die Menge aller Teilmengen einer Menge M, die so genannte Potenzmenge P(M) von M überabzählbar ist, wenn M unendlich viele Elemente hat. Genauer: Man kann zeigen, dass P(M) echt mächtiger ist als M. Siehe dazu den Artikel Mächtigkeit.

Mit Hilfe der Potenzmenge der Potenzmenge lassen sich unendlich viele verschiedene Klassen von Unendlichkeit konstruieren, die Kardinalzahlen genannt werden.