Das Diagonalverfahren

Man wird nun vielleicht einwenden, dass diese Überlegungen nur zeigen, dass im Reich des Unendlichen eben alle Größenunterschiede verschwinden. Die Begriffsbildung „abzählbar unendlich“ scheint überflüssig, da sich scheinbar jede noch so umfassende unendliche Menge mit Hilfe der natürlichen Zahlen durchzählen lässt. Dass dies nicht so ist, folgt aus dem folgenden fundamentalen Satz von Georg Cantor aus dem Jahre 1874:

Satz (Überabzählbarkeit der reellen Zahlen)

Es gilt |ℝ| ≠ |ℕ|, d. h., die Menge ℝ der reellen Zahlen ist nicht abzählbar.

Beweis

Seien x₀, x₁, x₂, …, x_n, … reelle Zahlen. Wir konstruieren ein x*  ∈  ℝ, das von allen x_n verschieden ist. Hierzu schreiben wir in Dezimaldarstellung:

x₀ = z₀, a_0,0 a_0,1 a_0,2 …,

x₁ = z₁, a_1,0 a_1,1 a_1,2 …,

x₂ = z₂, a_2,0 a_2,1 a_2,2 …,

…

x_n = z_n, a_n,0 a_n,1 a_n,2 …,

…

Wir definieren nun für alle n  ∈  ℕ

$d_{n} = { \begin{matrix} 1 & falls a_{n,n} = 2, \\ 2 & falls a_{n,n} \neq 2, \end{matrix}$

und setzen

x* = 0, d₀ d₁ d₂ …

Dann ist x* eine reelle Zahl in eindeutiger Dezimaldarstellung, und für jedes n ist x* ≠ x_n, denn die n-ten Nachkommastellen von x* und x_n sind verschieden voneinander. Damit kommt die reelle Zahl x* in der Aufzählung x₀, x₁, …, x_n, … nicht vor.

Wir lesen also die Nachkommastellen der Zahlen x₀, x₁, …, x_n, … „diagonal“ und konstruieren mit Hilfe der Diagonalziffern a_{0, 0} a_{1, 1} a_{2, 2} … eine reelle Zahl x*, die für jedes n spätestens ab der n-ten Nachkommastelle von x_n abweicht. Dieses Vorgehen ist als Diagonalargument in die Geschichte der Mathematik eingegangen. Es gehört heute ebenso zur Allgemeinbildung eines Mathematikers wie der Beweis der Irrationalität der Quadratwurzel aus 2. Varianten des Arguments tauchen an verschiedenen Stellen in der Mengenlehre, Logik, Informatik und höheren Analysis auf.

Erster Einwand

Gegen das Argument wird oft vorgebracht, dass man ja die konstruierte Zahl x* noch zu den Zahlen x₀, x₁, x₂, …, hinzufügen könne und im Sinne des Hilbertschen Hotels dann die Zahlen x*, x₀, x₁, … vorliegen hätte. Hierzu bemerken wir, dass aus der Annahme der Abzählbarkeit von ℝ folgt, dass es eine Folge x₀, x₁, … gibt, die alle reellen Zahlen durchläuft. Unser Beweis findet eine Zahl x*, die nicht in der Folge vorkommt. Damit ist die Annahme falsch, d. h., die reellen Zahlen sind nicht abzählbar. Selbstverständlich kann man für jede Folge x₀, x₁, … die Folge x*, x₀, x₁, … bilden und dann weiter x**, x*, x₀, x₁, … Das Ergebnis, dass keine Folge reeller Zahlen alle reellen Zahlen durchläuft, bleibt dadurch unangetastet.

Zweiter Einwand

Oft wird auch behauptet, dass die Überabzählbarkeit von ℝ unhaltbar sei, weil man ja zeigen kann, dass sich zwischen je zwei reellen Zahlen eine rationale Zahl befindet und es deswegen doch offensichtlich nicht mehr reelle Zahlen als rationale Zahlen geben könne. Hierzu ist zu sagen, dass ein kontraintuitives Ergebnis noch keinen Widerspruch bedeutet. Wer einen Widerspruch anmeldet, muss genau zeigen, welche Ergebnisse warum nicht miteinander vereinbar sind. Ordnet man nun jedem Paar (x, y) von reellen Zahlen x < y eine rationale Zahl q zwischen x und y zu, so verwendet man dabei notwendig rationale Zahlen mehrfach. Die so entstehende Abbildung ist nicht injektiv und ein Widerspruch ist nicht zu sehen.

Es gibt also, im Sinne einer unmöglichen 1-1-Korrespondenz, mehr reelle Zahlen als natürliche oder ganze oder rationale Zahlen und damit existieren Größenunterschiede im Unendlichen. Und der Unterschied zwischen ℚ und ℝ ist gewaltig. Die durch die alten Griechen entdeckten Lücken von ℚ sind so zahlreich, dass wir sie nicht aufzählen können. ℝ entsteht nicht aus ℚ durch Hinzufügen von abzählbar vielen Zahlen x₀, x₁, x₂, …, denn die entstehende Menge ℚ ∪ { x₀, x₁, x₂, … } wäre als Vereinigung zweier abzählbarer Mengen immer noch abzählbar, wie eine Aufzählung der Form q₀, x₀, q₁, x₁, q₂, x₂, … zeigt. Es gibt also überabzählbar viele irrationale Zahlen. Das Gleiche gilt für die algebraischen Zahlen. Wir notieren explizit:

Korollar (Existenz transzendenter Zahlen)

Es gibt überabzählbar viele transzendente Zahlen.

Beweis

Wäre die Menge ℝ − 𝔸 der transzendenten Zahlen abzählbar, so wäre aufgrund der Abzählbarkeit von 𝔸 die Menge ℝ = 𝔸 ∪ (ℝ − 𝔸) eine Vereinigung zweier abzählbarer Mengen und damit abzählbar.

Wir haben keine neue Erkenntnis über π oder e gewonnen, aber wir haben gezeigt, dass „fast alle“ reellen Zahlen transzendent sind. Die Vorstellung

„ℝ besteht im Wesentlichen aus ℚ und den Wurzeln und π und e“,

die wir aus der Schule oft mehr oder weniger bewusst mitnehmen, ist mit der Vorstellung, dass jede Folge von Nachkommastellen eine reelle Zahl definiert, unvereinbar. Das Meer aller Nachkommafolgen ist gewaltig, die zu rationalen oder algebraischen Zahlen gehörigen Folgen sind dagegen nur ein paar Tropfen. Die reellen Zahlen sind also weitaus komplizierter, als man meinen möchte, und die vertraute Dezimaldarstellung reeller Zahlen beginnt Fragen aufzuwerfen:

Was heißt eigentlich „beliebige Folge von Nachkommastellen“?

Welche derartigen Folgen existieren eigentlich?

Diese Fragen führen zum Wunsch nach einer präzisen Konstruktion der reellen Zahlen, und es ist kein Zufall, dass die ersten Konstruktionen von ℝ historisch mit der Entdeckung der Überabzählbarkeit von ℝ zusammenfallen. Weiter wird man vielleicht auch noch die mengentheoretischen Grundannahmen erfahren wollen, auf denen eine solche Konstruktion beruht. Wir wollen diesen Dingen an dieser Stelle nicht nachgehen, sondern uns im folgenden Kapitel den Struktureigenschaften zuwenden, die für die Zwecke der Analysis gebraucht werden. Dabei werden wir eine algebraische Charakterisierung angeben, die klar zeigt, welches Ziel man bei einer Konstruktion eines mathematischen Kontinuums anstrebt. Unsere hier gewonnenen Ergebnisse zeigen dann, dass man dieses Ziel mit einer abzählbar unendlichen Menge notwendig verfehlt. Die Analysis beruht auf einer überabzählbaren Struktur, wenn bestimmte Eigenschaften für diese Struktur gelten sollen.