Cantors Unendlichkeiten – Abzählbar oder überabzählbar unendlich?

Visits: 4844

Georg Cantor

 

 

Philipp Wehrli, 20. Juli 2006
Unsere Logik und unsere Sprache basiert auf Mengenlehre. Wenn wir den Informationsgehalt verschiedener Aussagen vergleichen wollen, so läuft dies oft darauf hinaus, die Grösse zweier Mengen zu vergleichen. Bei endlich grossen Mengen ist dies einfach: Man zählt die Elemente ab und vergleicht sie miteinander. Bei unendlich grossen Mengen ist dies schwieriger. Georg Cantor hat den Begriff ‚unendlich’ so definiert, dass solche Vergleiche widerspruchsfrei möglich sind. Damit wurde Cantor zum Begründer der modernen Mengenlehre und der höheren Mathematik.

Wenn zwei endlich grosse Mengen die gleiche Anzahl Elemente haben, sind sie gleich gross. Der Mathematiker sagt: „Die Mengen haben gleiche Kardinalität.“ oder: „Sie sind gleichmächtig.“ oder: „Ihre Mächtigkeit ist gleich.“

Unendlich grosse Mengen können nicht so leicht abgezählt werden. Die Frage, ob zwei unendliche Mengen gleich gross sind hat aber durchaus praktische Bedeutung. Mit unserem Alphabet könnten z. B. theoretisch unendlich viele verschiedene Texte geschrieben werden. Könnten wir die selbe Information auch speichern, wenn wir statt 26 Buchstaben nur die zwei Ziffern 0 und 1 benützen? – Wer sich mit Computer etwas auskennt, weiss, dass Computer dies tatsächlich tun. Warum sind mit 26 Buchstaben nicht mehr verschiedene Texte möglich als nur mit zwei? In beiden Fällen können unendlich viele verschiedene Texte geschrieben werden. Es ist deshalb wichtig zu untersuchen, wie wir mit Unendlichkeiten rechnen müssen. Was heisst unendlich?

Hilberts Hotel

Der grosse Mathematiker David Hilbert erklärte den Begriff ‚unendlich’ sehr anschaulich an einem Hotel mit unendlich vielen Zimmern. Angenommen, du arbeitest als Receptionist eines Hotels mit unendlich vielen Zimmern und alle sind ausgebucht. Leider kommt noch ein zusätzlicher Gast. Wie kannst du den unterbringen?
„Kein Problem“, sagt Hilbert: „Du gibst dem Gast das Zimmer 1.“
„Aber da ist ja bereits einer drin.“
„Ach ja? Den schickst du ins Zimmer 2.“
„Da ist auch schon einer. Das ganze Hotel ist ausgebucht!“
„Macht nichts, wir haben ja unendlich viele Zimmer. Schick alle Gäste in das Zimmer mit einer Nummer höher. Wer im Zimmer N war, kommt ins Zimmer N+1. Wenn unendlich viele Leute Platz haben, kommt es auf einen mehr nicht an.“

Denn in beiden Fällen sind einfach alle Zimmer des Hotels ausgebucht. Niemand kann feststellen, ob da noch ein Gast hinzugekommen ist oder nicht.

Mit diesem Trick bringst du die Nacht glücklich hinter dich. Doch am nächsten Tag sind immer noch alle Zimmer besetzt und kommt nicht nur eine einzelne Person neu an, sondern ein ganzer Bus mit unendlich vielen Gästen! Was tun? Hilbert sagt: „Ist doch auch kein Problem. Du schickst den aus Zimmer 1 ins Zimmer 2, den aus Zimmer 2 ins Zimmer 4, den von 3 ins 6 u. s. w. Der aus Zimmer N kommt ins Zimmer 2N. So kannst du alle unterbringen.“

Wenn du als Inspektor ins Hotel kommst, kannst du nicht feststellen, ob unendlich viele oder zweimal unendlich viele Leute in den Zimmern sind. Es ist einfach in jedem Zimmer eine Person drin.

Abzählbar oder überabzählbar unendlich

Unendlich plus 1 ist gleich viel wie unendlich. Zweimal unendlich ist das gleich viel wie unendlich. Gregor Cantor überlegte sich, ob es überhaupt verschiedene Arten von ‚unendlich’ geben könnte. Er sagte:

Wenn ich eine Menge A in ein Hotel mit unendlich vielen Zimmern so verstauen kann, dass in jedem Zimmer genau ein Element ist, dann nenne ich diese Menge abzählbar unendlich. Jedem A wird also genau eine Nummer zugeteilt (eine natürliche Zahl) und zu jeder natürlichen Zahl gibt es genau ein Element von A, das diese ‚Zimmernummer’ belegt. Ein Mathematiker würde sagen:

Definition:„Wenn es eine bijektive Abbildung von A auf die Menge der natürlichen Zahlen gibt, dann heisst A abzählbar unendlich.“

Cantor definierte: Alle abzählbar unendlichen Mengen sind gleich mächtig.

1. Beispiel:
   Die Menge natürlichen Zahlen sind abzählbar unendlich. Das ist trivial.
2. Beispiel: Die Menge der geraden Zahlen ist abzählbar unendlich.
   Die Menge geraden Zahlen sind abzählbar unendlich. Denn es gibt eine erste, eine zweite, eine dritte gerade Zahl u. s. w. Die Menge der geraden Zahlen und die Menge der natürlichen Zahlen sind also gleich mächtig. Wir würden zwar intuitiv sagen, es gebe viel mehr natürliche Zahlen als gerade. Aber wenn du Leute in einem Hilbert Hotel unterbringen musst, spielt es keine Rolle, ob du alle unendlich vielen Zimmer belegen darfst oder nur die mit den geraden Nummern.
3. Beispiel: Die Menge der Brüche ist abzählbar unendlich.
   Cantor wollte eine wirklich grosse Menge finden. Also untersuchte er die Menge der Brüche. Es scheint viel mehr Brüche zu geben als natürliche Zahlen. Zwischen je zwei verschiedenen natürlichen Zahlen liegen ja unendlich viele Brüche. In jedem noch so kleinen Abschnitt der Zahlengerade finde ich unendlich viele Brüche. Die Menge der Brüche ist riesig.

Cantor erkannte aber, dass selbst diese riesige Menge abzählbar ist und er zeigte sogar, wie man die Brüche abzählen könnte. Er schrieb alle Brüche in ein Zahlenfeld. Die x-Achse gibt jeweils den Zähler an, die y-Achse den Nennen. Die Brüche, die noch gekürzt werden können, strich er weg, weil sie sonst doppelt vorkommen würden. Dann nummerierte er die Brüche den schrägen Pfeilen entlang durch.

Abbildung 1. Cantors Diagonalverfahren

Er erhält also die folgende Zuordnung:

1	2	3	4	5	6	7	8	9	…
1/1	2/1	1/2	1/3	3/1	4/1	3/2	2/3	1/4	…

Jedem positiven Bruch wird eine natürliche Zahl zugeordnet und umgekehrt erhält jede natürliche Zahl genau einen Bruch. Selbstverständlich könnte das Verfahren leicht auch auf negative Brüche ausgedehnt werden. Mathematiker sagen: Es gibt eine Bijektion von der Menge der Brüche auf die natürlichen Zahlen. Die Zahl der Brüche ist abzählbar. Obwohl sie viel grösser erscheint als die Menge der natürlichen Zahlen, sind beide Mengen gleich mächtig.

4. Beispiel: Die Menge der reellen Zahlen ist nicht abzählbar.
   Nachdem sogar eine so grosse Menge wie die Menge Brüche abzählbar ist, würde man denken, alle Mengen seien abzählbar. Georg Cantor konnte aber beweisen, dass die Menge der reellen Zahlen nicht abzählbar ist. Für diesen Beweis erfand er das sogenannte Cantorsche Diagonalverfahren, das ich auch im Satz von Turing benütze.

Cantor führt den Beweis durch Widerspruch: Er nimmt zuerst das Gegenteil von dem an, was er zeigen will, und beweist dann das diese Annahme zu einem Widerspruch führen würde. Er nimmt an, er habe eine Liste mit allen reellen Zahlen, und konstruiert dann eine reelle Zahl, die nicht in der Liste enthalten ist. Zu jeder Liste mit reellen Zahlen findet er noch eine reelle Zahl, die fehlt. Daher kann es keine vollständige Liste von reellen Zahlen geben, und daher auch keine bijektive Abbildung von den reellen zu den natürlichen Zahlen.

Schon die reellen Zahlen zwischen 0 und 1 sind nicht abzählbar. Also schon für diese kann es keine vollständige Liste geben. Nehmen wir an, jemand habe so eine Liste aufgeschrieben und behauptet, in der Liste seien alle reellen Zahlen enthalten. Das sieht etwa so aus:

1. 0, a¹¹ a¹² a¹³ a¹⁴ a¹⁵ …
2. 0, a²¹ a²² a²³ a²⁴ a²⁵ …
3. 0, a³¹ a³² a³³ a³⁴ a³⁵ …
4. 0, a⁴¹ a⁴² a⁴³ a⁴⁴ a⁴⁵ …
5. 0, a⁵¹ a⁵² a⁵³ a⁵⁴ a⁵⁵ …
…

Die Ziffer a⁴² ist z. B. die zweite Kommastelle der vierten Zahl, also irgendeine Ziffer zwischen 0 und 9. Cantor konstruiert nun eine reelle Zahl x, die nicht in der Liste vorkommt, und widerlegt damit die Behauptung, die Liste sei vollständig. x soll so aussehen:
x = 0, x¹ x² x³ x⁴ … , wobei x¹ die erste Stelle nach dem Komma ist, x² die zweite u. s. w.
Die xⁱ werden so konstruiert: Die erste Ziffer der ersten Zahl (a¹¹) verändert er. Wenn a¹¹ eine 5 ist, dann nimmt er für seine Zahl x an der ersten Stelle eine 4, also x¹ = 4. Wenn a¹¹ keine 5 ist, dann nimmt er für seine Zahl x an der ersten Stelle eine 5, also x¹ = 5. Die Zahl x ist also sicher nicht gleich der ersten Zahl der Liste. Denn sie unterscheiden sich ja schon in der ersten Ziffer. Ebenso wählt er x² anders als a²², x³ anders als a³³ u. s. w. In jeder Zahl der Liste gibt es also mindestens eine Stelle, die anders ist als in x. D. h. x kommt nicht in der Liste vor. Weil x aber eine reelle Zahl ist, enthält die Liste nicht alle reellen Zahlen.

Könnte man x einfach zur Liste hinzufügen?

Ein schlauer Kerl könnte auf die Idee kommen, x zu seiner Liste hinzuzufügen, z. B. an erster Stelle, und alle anderen Zahlen eine Stelle nach hinten zu rücken. Damit wäre aber nichts gewonnen. Denn mit Cantors Verfahren finden wir leicht eine neue Zahl, die auch nicht in der Liste enthalten ist. Es kann daher keine vollständige Liste von reellen Zahlen geben. Die reellen Zahlen sind überabzählbar.

Weiterführende Artikel auf dieser Homepage:

Der Satz von Turing – eine Anwendung des Diagonalverfahrens führt zur Grenze des Erkennbaren.

Weiterführende Bücher:

Spektrum der Wissenschaft Spezial: ‘Das Unendliche’