Abzählbar unendliche Mengen

Sei A eine unendliche Menge. Nach unseren Ergebnissen existiert eine Injektion von ℕ nach A. Eine natürliche Frage ist, ob es auch eine Bijektion zwischen ℕ und A gibt. Wir definieren hierzu:

Definition (abzählbar, abzählbar unendlich)

Sei A eine Menge. Dann heißt A abzählbar unendlich, falls es eine Bijektion f : ℕ → A gibt. Weiter heißt A abzählbar, falls A endlich oder abzählbar unendlich ist.

Schreiben wir eine Funktion f : ℕ → A als Folge (a_n)_{n  ∈  ℕ}, so bedeutet die abzählbare Unendlichkeit von A, dass wir alle Elemente von A in der Form

(+) a₀, a₁, a₂, …, a_n, …

ohne Wiederholungen aufzählen können. In dieser Form ist der Begriff der Abzählbarkeit besonders anschaulich. Die Elemente von A können mit Hilfe der natürlichen Zahlen nummeriert, durchgezählt oder aufgelistet werden. Wir präzisieren in diesem Kontext noch einige Sprechweisen:

Definition (Aufzählung)

Sei A eine Menge. Eine surjektive Funktion f : ℕ → A nennen wir auch eine (unendliche) Aufzählung von A. Für alle n  ∈  ℕ heißt f (n) das n-te Element und n eine Position von f (n) in der Aufzählung. Ist f bijektiv, so heißt f eine injektive Aufzählung oder eine Aufzählung ohne Wiederholungen.

Ist A nichtleer, so existiert eine Aufzählung von A genau dann, wenn A endlich oder abzählbar unendlich ist. Weiter können wir aus einer Aufzählung einer unendlichen Menge Wiederholungen streichen, wodurch eine injektive Aufzählung (also eine Bijektion zwischen ℕ und A) entsteht.

Beispiele

(1)	Die Menge ℕ ist abzählbar unendlich: Die Folge 0, 1, 2, …, n, … ist eine Aufzählung von ℕ.

(2)	Die Menge der Primzahlen ist abzählbar unendlich.

(3)	Eine Teilmenge einer abzählbaren Menge ist abzählbar. Eine unendliche Teilmenge einer abzählbar unendlichen Menge abzählbar unendlich.

Ist die Unendlichkeit einer Menge A klar, so sagen wir im Folgenden oft nur „A ist abzählbar“ statt „A ist abzählbar unendlich“.

Wir betrachten nun weitere Beispiele für abzählbare Mengen, die zum Teil auch den Rang von Sätzen beanspruchen können.

1. Die ganzen Zahlen

Die Menge ℤ ist abzählbar, denn

0, 1, −1, 2, −2, 3, −3, …, n, −n, …

ist eine Aufzählung von ℤ.

2. Paare natürlicher Zahlen

Die Menge ℕ² aller Paare natürlicher Zahlen ist abzählbar. Zum Beweis zählen wir das Gitter ℕ × ℕ auf, indem wir seine endlichen Diagonalen betrachten und aneinanderfügen:

(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), (1, 2), (2, 1), (3, 0), …

Diese injektive Aufzählung von ℕ² ist als Cantorsche Diagonalaufzählung bekannt. Sie entspricht der Cantorschen Paarung π : ℕ² → ℕ mit

π(n, m) = ^{(n + m)(n + m + 1)}₂ + n für alle (n, m)  ∈  ℕ².

Für alle (n, m)  ∈  ℕ² ist π(n, m) die eindeutige Position von (n, m) in der Diagonalaufzählung, d. h. die Diagonalaufzählung ist die Umkehrfunktion von π (Übung). Es ist bemerkenswert, dass sich die Positionen der Diagonalaufzählung durch ein einfaches Polynom zweiten Grades berechnen lassen.

Wir können die Diagonalaufzählung von ℕ² noch in einer etwas anderen Form beschreiben, die für das Folgende nützlich ist: Die Paare (n, m) auf einer Diagonalen von ℕ² haben ein konstantes „Gewicht“ k = n + m. Jedem Gewicht k entsprechen nur endlich viele Paare (genauer sind es k + 1 viele). In der Diagonalaufzählung zählen wir die Elemente von ℕ² nach ihrem Gewicht auf.

Die Cantorsche Diagonalaufzählung von ℕ × ℕ. Rechts sind die Werte der Paarungsfunktion π : ℕ² → ℕ eingetragen.

3. Die rationalen Zahlen

Die Menge ℚ ist abzählbar, denn für jedes k  ∈  ℕ gibt es nur endlich viele Brüche n/m  ∈  ℚ mit dem Gewicht k = |n| + |m|. Fügen wir die Brüche des Gewichts k für k = 0, 1, 2, … aneinander, so erhalten wir eine Aufzählung von ℚ. Diese Aufzählung besitzt Wiederholungen, die wir streichen können, um eine Bijektion zwischen ℕ und ℚ zu erhalten.

4. Die algebraischen Zahlen

Die Menge 𝔸 der algebraischen Zahlen ist abzählbar. Denn jede algebraische Gleichung hat höchstens endlich viele Nullstellen, und die algebraischen Gleichungen können wir wieder nach einem geeigneten Gewicht aufzählen. Geeignet ist zum Beispiel die Summe aus dem Grad und der Beträge aller (ohne Einschränkung ganzzahligen) Koeffizienten. Dieses Gewicht einer algebraischen Gleichung ist nach Dedekind auch als Höhe der Gleichung bekannt. So hat zum Beispiel die Gleichung

x⁴ − 2x³ + 3x − 4 = 0

die Dedekindsche Höhe 4 + 1 + 2 + 3 + 4 = 14 und höchstens vier reelle Nullstellen. Zu jeder Höhe h gibt es nur endlich viele Gleichungen der Höhe h. Hierzu ist es wichtig, den Grad in die Höhe mit aufzunehmen. Ansonsten hätten die unendlich vielen Gleichungen x = 0, x² = 0, x³ = 0, … alle die Höhe 1.

5. Endliche Folgen natürlicher Zahlen

Die Menge Seq = { (a₁, …, a_n) | n  ∈  ℕ, a_i  ∈  ℕ für alle i = 1, …, n } aller endlichen Folgen in ℕ ist abzählbar. Denn die Folgen (a₁, …, a_n) in Seq lassen sich erneut nach einem geeigneten Gewicht, etwa n + a₁ + … + a_n, aufzählen. Zu jedem Gewicht gibt es nur endlich viele Folgen mit diesem Gewicht.

Die Abzählbarkeit der Menge Seq verallgemeinert die Abzählbarkeit von ℕ² in einer sehr starken Weise. Speziell ist für jedes k ≥ 1 die Menge ℕ^k aller k-Tupel in ℕ abzählbar.

6. Die Universalbibliothek

Die ideelle Universalbibliothek, die alle in einem bestimmten endlichen oder abzählbar unendlichen Alphabet

a, b, c, …, A, B, C, …, 0, …, 9, ?, !, ;, (, ), …, α, β, γ, …, ‎א‎, ‎ב‎, ‎ג‎, …

geschriebenen Bücher enthält, ist abzählbar. Denn ein Buch ist eine endliche Folge in einem Alphabet, dessen Zeichen wir mit den natürlichen Zahlen durchnummerieren können. Damit ist dieses Beispiel lediglich eine eindrucksvolle Veranschaulichung der Abzählbarkeit aller endlichen Folgen in den natürlichen Zahlen.

Als allgemeinen Satz halten wir fest:

Satz (abzählbare Vereinigung von abzählbaren Mengen)

Sei (A_n)_{n  ∈  ℕ} eine Folge abzählbarer Mengen, und sei

A = ⋃_{n  ∈  ℕ} A_n.

Dann ist A abzählbar.

Beweis

Wir dürfen annehmen, dass alle A_n nichtleer sind. Für jedes n  ∈  ℕ wählen wir nun eine Aufzählung (a_{n, m})_{m  ∈  ℕ} der Menge A_n. Weiter sei σ : ℕ → ℕ² die Cantorsche Diagonalaufzählung von ℕ × ℕ, d. h. es gilt σ = π⁻¹ mit der Paarungsfunktion π. Dann ist (a_σ(n))_{n  ∈  ℕ} eine Aufzählung von A.

Die konstruierte Aufzählung von A erhalten wir, wenn wir für jedes n  ∈  ℕ die Elemente von A_n in die Spalte n des Gitters ℕ × ℕ eintragen und dann das Gitter diagonal aufzählen. Sind alle Mengen A_n abzählbar unendlich und paarweise disjunkt, so entsteht eine Bijektion zwischen ℕ und A, wenn wir die Spalten des Gitters ohne Wiederholungen füllen.

Im Beweis des Satzes taucht an versteckter Stelle wieder ein unendlicher Auswahlakt auf: Wir wählen unendlich oft eine unspezifizierte Aufzählung.