Abzählbare Mengen
Definition (abzählbar unendlich, abzählbar)
(a) | Eine Menge M heißt abzählbar unendlich, falls es eine Bijektion f : ℕ → M gibt. Wir schreiben dann |M| = |ℕ| und sagen, dass die Mächtigkeit von M gleich der Mächtigkeit von ℕ ist. |
(b) | Eine Menge heißt abzählbar, falls M endlich oder abzählbar unendlich ist. Wir schreiben dann |M| ≤ |ℕ| und sagen, dass die Mächtigkeit von M kleinergleich der Mächtigkeit von ℕ ist. |
Beispiele
|ℕ| = |ℕ|, |ℕ*| = |ℕ|, |ℤ| = |ℕ|,
|{ x0, …, xn }| ≤ |ℕ|, { x0, …, xn, … }| ≤ |ℕ|,
|{ x0, …, xn, … }| = |ℕ|, falls xn ≠ xm für alle n ≠ m gilt.
Eine Funktion f : ℕ → M lässt sich wie in obigen Beispielen darstellen:
0 | 1 | 2 | 3 | 4 | … |
f (0) | f (1) | f (2) | f (3) | f (4) | … |
Diese tabellarische Darstellung können wir zur „Folgenform“
f (0), f (1), f (2), …, f (n), …
verkürzen. Damit ist leicht einzusehen, dass eine Menge M genau dann abzählbar unendlich ist, wenn wir die Elemente von M ohne Wiederholungen in die Form f (0), f (1), f (2), … bringen können. Können wir M mit eventuellen Wiederholungen als g(0), g(1), g(2), … aufzählen, so ist M abzählbar. Denn das Streichen der Wiederholungen liefert eine endliche Aufzählung f (0), …, f (n) von M oder aber eine wiederholungsfreie unendliche Aufzählung f (0), f (1), f (2), … von M.
Obige Überlegung zeigt, dass die Menge ℤ der ganzen Zahlen abzählbar unendlich ist. Stärker gilt:
Satz (Abzählbarkeit der rationalen Zahlen)
Es gilt |ℚ| = |ℕ|.
Beweis
Wir zählen die rationalen Zahlen wie folgt auf:
0/1, (Gewicht 1)
1/1, −1/1, (Gewicht 2)
2/1, −2/1, 1/2, −1/2, (Gewicht 3)
3/1, −3/1, 1/3, −1/3, (Gewicht 4)
4/1, −4/1, 3/2, −3/2, 2/3, −2/3, 1/4, −1/4 (Gewicht 5)
…
Hierbei erhält ein gekürzter Bruch n/m mit n ∈ ℤ, m ∈ ℕ* das Gewicht
g = |n| + m.
Indem wir die jeweils endlich vielen gekürzten Brüche mit dem Gewicht g = 1, 2, 3, … aneinanderfügen, wird ℚ in eine wiederholungsfreie Form
f (0), f (1), f (2), f (3), …, f (n), …
gebracht. Also gilt |ℚ| = |ℕ|.
Ein ganz ähnliches Argument zeigt noch stärker:
Satz (Abzählbarkeit der algebraischen Zahlen)
Es gilt |𝔸| = |ℕ|.
Beweis
Jede algebraische Zahl ist eine Lösung einer algebraischen Gleichung mit ganzzahligen Koeffizienten. Da jede solche Gleichung nur endlich viele Lösungen besitzt, genügt es zu zeigen, dass wir alle diese Gleichungen aufzählen können. Hierzu ordnen wir einer Gleichung
anxn + … + a1x1 + a0 = 0 mit n ∈ ℕ, a0, …, an ∈ ℤ, an ≠ 0,
das Gewicht
g = n + |an| + … + |a0| ≥ 0
zu. Dann gibt es für jedes Gewicht g nur endlich viele Gleichungen mit dem Gewicht g. Damit erhalten wir eine Aufzählung aller algebraischen Gleichungen und folglich auch eine Aufzählung aller algebraischen Zahlen.