Was beweist Cantors Diagonalargument?

Es beweist, dass die reellen Zahlen zwischen 0 und 1 überabzählbar sind: keine Liste, egal wie geschickt konstruiert, kann jede reelle Zahl in diesem Intervall enthalten. Es gibt schlicht mehr reelle Zahlen als Positionen auf irgendeiner Liste.

Was bedeutet abzählbar?

Eine Menge ist abzählbar, wenn man jedes ihrer Elemente mit einer natürlichen Zahl (1, 2, 3, ...) paaren kann, sodass nichts übrig bleibt. Die natürlichen Zahlen, ganzen Zahlen und sogar die rationalen Zahlen sind alle abzählbar. Die reellen Zahlen sind es nicht: sie sind zu zahlreich, um in eine solche Eins-zu-eins-Entsprechung gebracht zu werden.

Warum kann man die fehlende Zahl nicht einfach zur Liste hinzufügen?

Das kann man, aber dann wendet das Diagonalargument auf die neue, längere Liste an und produziert wieder eine fehlende Zahl. Das Argument funktioniert für jede Liste, wie lang oder geschickt auch immer arrangiert, es gibt also keine Möglichkeit, die Liste zur Vollständigkeit zu flicken.

Warum vermeidet man beim Umkehren die Ziffern 0 und 9?

Einige reelle Zahlen haben zwei Dezimaldarstellungen: 0,4999... und 0,5000... sind dieselbe Zahl. Wenn man eine Ziffer auf 0 oder 9 kippt, landet man möglicherweise versehentlich auf dem anderen Namen einer Zahl, die bereits auf der Liste steht. Das Vermeiden von 0 und 9 umgeht diese Feinheit und hält den Beweis sauber.

Sind die rationalen Zahlen auch überabzählbar?

Nein. Die rationalen Zahlen sind abzählbar: man kann systematisch jeden Bruch p/q auflisten und jedem einen natürlichen Zahlenindex zuweisen, ohne etwas auszulassen. Cantors Diagonalargument zielt auf die reellen Zahlen, nicht die rationalen.

Cantors Diagonalargument: Warum die reellen Zahlen nicht auflistbar sind

Stell dir vor, jemand gibt dir eine Liste. Es ist eine unendliche Liste, und diese Person behauptet, sie enthält jede reelle Zahl zwischen 0 und 1. Keine Auswahl, keine Selektion: jede einzelne, ordentlich als r1, r2, r3 und so weiter indiziert, endlos weitergehend.

Georg Cantors Antwort darauf, im Jahr 1891, war diese: welche Liste du mir auch gibst, ich kann eine Zahl ablesen, die nicht darauf steht. Die Konstruktion braucht etwa dreißig Sekunden, um sie zu beschreiben. Die Konsequenz hat Mathematiker jahrzehntelang beschäftigt, denn sie bedeutet, dass das Unendliche in mehr als einer Größe vorkommt.

Zählen und Auflisten

Bevor der Diagonalzug kommt, hilft es, genau zu sein, was "abzählbar" bedeutet. Eine Menge ist abzählbar, wenn du jedem Element ein eindeutiges natürliches Zahlen-Label zuweisen kannst: ein erstes Element, ein zweites, ein drittes, und so weiter, ohne Rest. Die natürlichen Zahlen selbst sind per Definition abzählbar. Die ganzen Zahlen auch (liste sie als 0, 1, -1, 2, -2, ...) und sogar die rationalen Zahlen, wobei das Auflisten jedes Bruchs ein cleveres Zickzack-Muster erfordert.

Cantors Argument zeigt, dass die reellen Zahlen zwischen 0 und 1 wirklich anders sind: keine Beschriftung existiert, egal wie du es versuchst. Das ist kein Versagen der Vorstellungskraft. Es ist ein Beweis, dass die Aufgabe unmöglich ist.

Nimm an, die Liste existiert

Das Argument ist ein Widerspruchsbeweis. Beginne damit, dem Gegenüber alles zu geben, was es will: nimm an, eine vollständige Liste jeder reellen Zahl in (0, 1) existiert tatsächlich. Schreibe jede Zahl als unendliche Dezimalentwicklung.

Die Liste könnte so beginnen:

r1 = 0,14159265...
r2 = 0,73205080...
r3 = 0,00000000...
r4 = 0,27182818...
r5 = 0,91415926...
...

Jeder Eintrag geht ewig weiter. Die Liste geht ewig weiter. Und per Annahme erscheint jede reelle Zahl zwischen 0 und 1 irgendwo auf ihr.

Beobachte nun, was passiert, wenn du die Diagonale entlangliest.

Die Diagonale lesen

Schau dir die erste Dezimalstelle von r1 an, die zweite von r2, die dritte von r3, und so weiter. In dem obigen Beispiel sind diese Diagonalziffern: 1, 3, 0, 2, 9, ...

Du baust nun eine neue Zahl, nennen wir sie d, eine Ziffer nach der anderen. Die Regel: ersetze für jede Diagonalziffer eine andere Ziffer, aber vermeide dabei absichtlich 0 und 9.

r₁	.	1	4	1	5	9
r₂	.	3	3	3	3	3
r₃	.	5	0	0	0	0
r₄	.	7	1	8	2	8
r₅	.	6	0	2	5	9
new	.	2	4	1	3	8	…

Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.

Die Diagonalziffern sind 1, 3, 0, 2, 9. Die Regel anwenden ergibt 2, 4, 1, 3, 8. Also ist d = 0,24138...

Das Vermeiden von 0 und 9 ist eine kleine, aber notwendige Vorsichtsmaßnahme. Einige reelle Zahlen haben zwei Dezimaldarstellungen: 0,4999... und 0,5000... bezeichnen denselben Punkt auf der Zahlengeraden. Eine Ziffer auf 0 oder 9 zu kippen könnte dich versehentlich auf den "anderen Namen" einer Zahl landen lassen, die bereits auf der Liste steht, was das Argument trüben würde. Indem du bei jedem umgekippten Wert im Bereich 1 bis 8 bleibst, garantierst du, dass d genau eine Dezimalentwicklung hat, und der folgende Vergleich ist sauber.

Die neue Zahl unterscheidet sich von jedem Eintrag

Hier ist der Gewinn.

d unterscheidet sich von r1 an der ersten Dezimalstelle

Die erste Ziffer von d wurde so gewählt, dass sie sich von der ersten Ziffer von r1 unterscheidet. Also ist d nicht gleich r1. Sie unterscheiden sich an Position 1.

d unterscheidet sich von r2 an der zweiten Dezimalstelle

Die zweite Ziffer von d wurde so gewählt, dass sie sich von der zweiten Ziffer von r2 unterscheidet. Also ist d nicht gleich r2. Sie unterscheiden sich an Position 2.

d unterscheidet sich von rn an der n-ten Dezimalstelle, für jedes n

Per Konstruktion unterscheidet sich die n-te Ziffer von d von der n-ten Ziffer von rn. Da zwei Zahlen mit einer unterschiedlichen Ziffer an irgendeiner Position ungleich sind, ist d nicht gleich rn, für keines der n, das du nennst.

Das ist der Diagonalzug: d wurde so konstruiert, dass es mit jedem Eintrag der Liste an genau der Stelle kollidiert, an der jeder Eintrag am meisten exponiert ist, seiner eigenen Diagonalposition.

d ist eine reelle Zahl zwischen 0 und 1, steht aber nicht auf der Liste

Die Zahl d = 0,24138... ist eindeutig eine reelle Zahl im Intervall (0, 1). Aber wir haben gerade gezeigt, dass sie sich von r1, von r2, von r3, von jedem Eintrag unterscheidet. Wäre die Liste vollständig, müsste d irgendwo auf ihr erscheinen. Das tut sie nicht. Also ist die Liste nicht vollständig.

Der Widerspruch ist scharf: wir haben angenommen, die Liste sei vollständig, und wir haben eine reelle Zahl produziert, die nicht darauf steht. Die Annahme muss falsch sein. Es kann keine vollständige Liste der reellen Zahlen zwischen 0 und 1 existieren.

Was das eigentlich bedeutet

Mathematiker sagen, die natürlichen Zahlen haben die Kardinalität Aleph-Null (geschrieben mit dem hebräischen Buchstaben Aleph: der erste transfinite Kardinal). Die reellen Zahlen haben eine strikt größere Kardinalität, manchmal geschrieben als c oder als 2 hoch Aleph-Null. Cantors Argument ist das, was beweist, dass diese beiden Unendlichkeiten nicht dieselbe Größe haben.

Das war höchst kontrovers, als Cantor es veröffentlichte. Einige Kollegen taten das Ergebnis als Kuriosität oder Fehler ab. Es ist keines von beidem. Es steht an der Grundlage dessen, wie Mathematiker über Mengen, Kardinalitäten und die Struktur der reellen Zahlengerade nachdenken, und es verbindet sich direkt mit Fragen darüber, was berechenbar ist und was nicht (siehe auch den Beweis in Goodsteins Satz für einen weiteren Fall, in dem etwas beweisbar Wahres an die Grenzen formaler Systeme stößt).

Warum die Diagonale funktioniert

Was das Argument elegant macht, ist seine Präzision. Du rätst nicht nach einer fehlenden Zahl und berufst dich nicht auf vage Intuition über die Größe der reellen Zahlen. Du liest genau ab, welche Positionen der Liste jeder Eintrag kontrolliert, und baust dann eine Zahl, die jedem Eintrag an exakt dieser Position ausweicht.

Die Liste selbst sagt dir, wo du schauen sollst. Jeder Eintrag auf der Liste übergibt dir eine Koordinate, seine eigene Diagonalziffer, und die Konstruktion verwandelt diese Koordinaten in eine Zahl, die die Liste nicht enthalten kann.

Die Einfachheit täuscht. Es ist hier nichts nötig, das irgendwelche Kenntnisse über die Einträge auf der Liste voraussetzt. Es spielt keine Rolle, welche Zahlen darauf stehen, in welcher Reihenfolge oder wie sie gewählt wurden. Das Argument ist universell: wähle irgendeine Liste reeller Zahlen, und die Diagonalkonstruktion produziert eine reelle Zahl, die nicht auf dieser Liste steht.

Das Zen davon

Cantors Diagonalargument steht in einer langen Tradition mathematischer Ergebnisse, die sich so anfühlen, als sollten sie nicht funktionieren. Du starrst auf den Beweis und wartest auf den Trick, die versteckte Annahme, die Stelle, an der die Logik rutscht. Sie ist nicht da. Der Beweis ist genau so einfach, wie er aussieht.

Was er dich akzeptieren lässt, ist seltsamer als der Beweis selbst: dass "unendlich" kein einziges Ziel ist. Die ganzen Zahlen und die reellen Zahlen sind beide unendlich, aber sie sind unendlich auf kategorial verschiedene Weisen. Das Diagonalargument ist die Trennlinie.

Für ein tieferes Gespür dafür, wie sich unendliche Sammlungen seltsam verhalten können, ist die Struktur von unendlichen Dezimalzahlen ein guter nächster Schritt, oder wie Grenzwerte funktionieren, wenn Folgen sich ewig einem Wert nähern, ohne ihn zu erreichen. Das Diagonalargument gehört zur selben Familie: ein präziser, geduldiger Blick darauf, was am Rand des Unendlichen passiert, wo Intuition einen Beweis braucht, um ehrlich zu bleiben.

Das Unendliche ist nicht eine Sache. Das ist die Nachricht. Das Argument, das sie überbringt, passt auf eine halbe Seite.