2.3 Abzählbarkeit und Überabzählbarkeit
Definition (endlich, abzählbar, überabzählbar)
Eine Menge M heißt
(a) | endlich, falls es eine Bijektion f : { 0, … n − 1 } → M für ein n ∈ ℕ gibt, |
(b) | abzählbar unendlich, falls es eine Bijektion f : ℕ → M gibt, |
(c) | abzählbar, falls M endlich oder abzählbar unendlich ist, |
(d) | überabzählbar, falls M nicht abzählbar ist. |
Eine abzählbar unendliche Menge M (links) kann in eine 1-1-Korrespondenz mit ℕ gebracht werden. Bei einer überabzählbaren Menge M (oben) existieren für jede Funktion f : ℕ → M Elemente von M, die nicht im Bild von f liegen.
Endliche Mengen lassen also eine Darstellung M = { x0, …, xn − 1 } zu, abzählbaren Mengen eine Darstellung M = { x0, …, xn, … } (vgl. 1. 6). Die Elemente einer abzählbaren Menge können also mit den natürlichen Zahlen „vollständig durchgezählt“ werden.
Beispiele
(1) | ℤ ist abzählbar: 0, 1, −1, 2, −2, 3, −3, … |
(2) | ℚ ist abzählbar: 0/1, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 1/3, −1/3, 4/1, −4/1, 3/2, −3/2, 2/3, −2/3, 1/4, −1/4, … Hier zählen wir alle gekürzten Brüche nach der Summe der Beträge von Zähler und Nenner auf. |
(3) | Die Menge aller algebraischen Gleichungen mit ganzzahligen Koeffizienten ist abzählbar: x = 0, x + 1 = 0, x − 1 = 0, x + 2 = 0, x − 2 = 0, 2 x + 1 = 0, −2 x + 1 = 0, x2 = 0, −x2 = 0, 2 x − 1 = 0, −2 x − 2 = 0, x2 + 1 = 0, … Wir ordnen hier die Gleichungen nach der Summe k + |a0| + … |ak| ihres Grades und der Beträge ihrer Koeffizienten. |
(4) | 𝔸 ist abzählbar: Wir ersetzen in der Abzählung in (3) jede Gleichung durch ihre endlich vielen Nullstellen und streichen Wiederholungen. |
Nun würde man vielleicht vermuten, dass auch die Menge der reellen Zahlen abzählbar ist. Unendlich ist scheinbar gleich unendlich, und damit gibt es scheinbar ebenso viele natürliche Zahlen wie rationale wie algebraische wie reelle Zahlen. Durch das sog. Cantorsche Diagonalverfahren lässt sich aber überraschend einfach zeigen, dass die reellen Zahlen nicht abzählbar sind. Hierzu betrachten wir eine beliebige Folge reeller Zahlen x0, x1, …, xn, … und schreiben in Dezimaldarstellung:
Nun betrachten wir die Diagonale der Nachkommastellen des Diagramms und definieren für alle n:
Nun setzen wir in Dezimaldarstellung
x* = 0, b0 b1 b2 …
Die Zahl x* ist nach Konstruktion von allen x0, x1, x2, … verschieden.
Damit ist es also unmöglich, die reellen Zahlen abzuzählen. Wir haben bewiesen:
Satz (Überabzählbarkeit der reellen Zahlen)
Sind x0, x1, …, xn, … reelle Zahlen, so gibt es eine reelle Zahl x*, die von allen xn verschieden ist. Die reellen Zahlen sind also überabzählbar.
Die reellen Zahlen nehmen eine höhere Unendlichkeitsstufe ein als die Mengen ℕ, ℚ und 𝔸, die sich alle auf der Stufe der abzählbaren Unendlichkeit befinden. Weiter gilt:
ℝ entsteht nicht aus 𝔸 durch Hinzunahme von abzählbar vielen Zahlen.
Denn ist 𝔸 = { a0, a1, a2, … } und X = { x0, x1, x2, … } eine Menge von „neuen“ Zahlen, so ist die Menge
A ∪ X = { a0, x0, a1, x1, a2, x2, … }
abzählbar und damit von ℝ verschieden. ℝ wird also nicht dadurch erzeugt, indem wir zu 𝔸 eine Handvoll transzendenter Zahlen wie e, π, e2, π2, eπ, … hinzunehmen. Die Menge ℝ − 𝔸 der transzendenten Zahlen ist überabzählbar und damit sind „alle bis auf abzählbar viele“ reelle Zahlen transzendent − so schwer es auch ist, einzelne Zahlen als transzendent zu erkennen. Das Kontinuum ist umfassender, komplizierter und geheimnisvoller, als man meinen möchte.