Cantors Diagonalargument

 Bislang haben wir nur abzählbare Mengen kennengelernt. Jetzt aber zeigt sich, dass die neben den natürlichen Zahlen wichtigste Struktur der Mathematik, die reellen Zahlen , nicht abzählbar ist. Cantor hat hierfür zwei Beweise gefunden, der erste benutzt die Vollständigkeit von , der zweite die Dezimaldarstellung einer reellen Zahl. Wir besprechen zunächst den berühmten zweiten Beweis. Das dabei auftauchende Argument einer Diagonalisierung wird in der Mengenlehre und in der Logik heute an verschiedenen Stellen benutzt.

 Cantor formuliert die Frage zum ersten Mal in einem Brief an Dedekind gegen Ende des Jahres 1873. Der Brief zeigt, dass Cantor die Abzählbarkeit der rationalen Zahlen und auch die der Menge der endlichen Folgen natürlicher Zahlen zu diesem Zeitpunkt bereits kannte.

Cantor an Dedekind am 29.11.1873:

„Hochgeehrter Herr Kollege!

Gestatten Sie mir, Ihnen eine Frage vorzulegen, die für mich ein gewisses theoretisches Interesse hat, die ich mir aber nicht beantworten kann; vielleicht können Sie es, und sind so gut, mir darüber zu schreiben, es handelt sich um folgendes.

 Man nehme den Inbegriff aller positiven ganzzahligen Individuen n und bezeichne ihn mit (n); ferner denke man sich etwa den Inbegriff aller positiven reellen Zahlgrößen x und bezeichne ihn mit (x); so ist die Frage einfach die, ob sich (n) dem (x) so zuordnen lasse, dass zu jedem Individuum des einen Inbegriffes ein und nur eines des andern gehört? Auf den ersten Anblick sagt man sich, nein es ist nicht möglich, denn (n) besteht aus diskreten Teilen, (x) aber bildet ein Kontinuum; nur ist mit diesem Einwande aber nichts gewonnen und so sehr ich mich auch zu der Ansicht neige, dass (n) und (x) keine eindeutige Zuordnung gestatten, so kann ich doch den Grund nicht finden und um den ist es mir zu tun, vielleicht ist es ein sehr einfacher. −

 Wäre man nicht auch auf den ersten Anblick geneigt zu behaupten, dass sich (n) nicht eindeutig zuordnen lasse dem Inbegriffe (p/q) aller positiven rationalen Zahlen p/q ? Und dennoch ist es nicht schwer zu zeigen, dass sich (n) nicht nur diesem Inbegriffe, sondern noch dem allgemeineren

(an1, n2, …, nν)

eindeutig zuordnen lässt, wo n1, n2, …, nν unbeschränkte positive ganzzahlige Indizes in beliebiger Zahl ν sind.

Mit bestem Gruße

Ihr ergebenster 

G. Cantor“     

 Den „Grund“ konnte Cantor Dedekind bereits etwa eine Woche nach der Formulierung des Problems mitteilen: Das Datum des entsprechenden Briefes an Dedekind, der 7. 12. 1873, wird häufig als der Geburtstag der Mengenlehre bezeichnet. Einen weiteren Beweis der Überabzählbarkeit von  fand Cantor später. Er trug ihn 1891 auf der ersten Jahresversammlung der von ihm mitbegründeten Deutschen Mathematiker-Vereinigung vor. Wir bringen hier zuerst diesen späteren Beweis, der zu einem Klassiker der Mathematik geworden ist.

Satz (Satz von Cantor über die Überabzählbarkeit der reellen Zahlen)

Die Menge  der reellen Zahlen ist überabzählbar.

Beweis

Es genügt zu zeigen: Es existiert kein f :    surjektiv.

Sei hierzu f :    beliebig.

Wir finden ein x  ∈   mit x  ∉  rng(f) wie folgt.

Für n  ∈   schreiben wir f (n) in kanonischer unendlicher Dezimaldarstellung [mit 0 = 0,000 … ].

Sei also:

f (0)  =  z0, a0,0 a0,1 a0,2 … 

f (1)  =  z1, a1,0 a1,1 a1,2 … 

f (2)  =  z2, a2,0 a2,1 a2,2 … 

f (3)  =  z3, a3,0 a3,1 a3,2 … 

f (n)  =  zn, an,0 an,1 an,2 … 

Wir definieren x = 0, b0 b1 b2 …  ∈   durch

bn=1,falls an,n=2,2,falls an,n2.

Dann ist x = 0, b0 b1 b2 … in kanonischer Dezimaldarstellung. Für jedes n  ∈   gilt nun aber x ≠ f (n), denn die n-ten Nachkommastellen der kanonischen Dezimaldarstellungen von x und f (n) sind verschieden, und die kanonische Dezimaldarstellung einer reellen Zahl ist eindeutig. Also x  ∉  rng(f), und damit ist f nicht surjektiv.

Übung

Warum ist es ungünstig, 0 und 1 in der Definition von bn zu verwenden an Stelle von 1 und 2?

[Wir setzenf (0) = 0,099999 … ,
f (1) = 0,011111 … ,
f (2) = 0,001111 … ,
f (3) = 0,000111 … ,  allgemein
f (n) = 1/9 · 1/10n für n ≥ 1.

Dann ist die mittels 0 und 1 definierte Diagonalisierung nicht in kanonischer Darstellung und gleich f (0), also im Wertebereich von f.]

 Ein Korollar zu diesem Satz betrifft die Existenz von transzendenten Zahlen.

Dies sind reelle Zahlen, die sich nicht als Nullstellen von Polynomen mit rationalen Koeffizienten darstellen lassen:

Definition (transzendente Zahlen)

Eine reelle Zahl x heißt transzendent, wenn x nicht algebraisch ist.

𝕋 sei die Menge der transzendenten Zahlen.

 Der Nachweis der Transzendenz einer bestimmten Zahl ist im Allgemeinen ein schwieriges Problem. 1851 konnte Joseph Liouville (1809 − 1882) zeigen, dass die Zahl

0,1100010000000000000000010 … 

transzendent ist, wobei die m-te Nachkommastelle dieser Zahl genau dann gleich 1 ist, wenn m = n! für ein n ≥ 1. Liouville wollte die Transzendenz der Eulerschen Zahl e = Σn ≥ 0 1/n!  beweisen, was dann erst Charles Hermite (1822 − 1902) 1872 gelang. Auf den Arbeiten von Hermite aufbauend bewies Lindemann 1882, dass die Kreiszahl π transzendent ist. (Cantor hat diese Arbeit referiert.) Der nächste große Schritt war die Lösung des siebenten Hilbertschen Problems durch Alexander Gelfond (1906 − 1968) und Theodor Schneider (1911 − 1988), die im Jahre 1934 unabhängig voneinander zeigten [siehe etwa  Siegel 1949]:

Ist a algebraisch, a > 0, a ≠ 1, und ist b irrational und algebraisch, so ist ab transzendent.

 Ist der Nachweis im Einzelfall schwierig, so zeigt der Satz von Cantor doch, dass „fast alle“ reellen Zahlen transzendent sind:

Korollar (die transzendenten Zahlen sind überabzählbar)

𝕋 ist überabzählbar. Genauer gilt:  − 𝕋 ist abzählbar.

Beweis

Es gilt  = 𝔸 ∪ 𝕋. Da die Menge 𝔸 der algebraischen Zahlen abzählbar ist, ist notwendig 𝕋 überabzählbar, denn die Vereinigung zweier abzählbarer Mengen ist abzählbar.

Übung

Seien Mn überabzählbare Mengen für n  ∈  . Für jedes n  ∈   sei die Menge Mn − Mn + 1 abzählbar. Dann ist ⋂n  ∈   Mn überabzählbar.