Abzählbare Vereinigungen
Mit Hilfe einer Paarungsfunktion auf ℕ2 können wir jetzt leicht einen sehr starken Satz beweisen.
Satz (eine abzählbare Vereinigung abzählbarer Mengen ist abzählbar)
Seien An abzählbare Mengen für n ∈ ℕ, und sei
A = ⋃n ∈ ℕ An.
Dann ist A abzählbar.
Beweis
Für jedes n ∈ ℕ sei
fn = „ein injektives fn : An → ℕ“.
Sei π : ℕ × ℕ → ℕ bijektiv (etwa die Cantorsche Paarungsfunktion). Wir definieren g : A → ℕ durch:
g(x) = π(fn(x), n), wobei
n = „das kleinste n ∈ ℕ mit x ∈ An“.
Dann ist g : A → ℕ injektiv, also |A| ≤ |ℕ|.
Die Definition der Funktionen fn geschieht wieder durch Auswahl. Für alle natürlichen Zahlen n ist die Menge
Mn = { g | g : An → ℕ injektiv }
nichtleer, denn An ist abzählbar. Für jedes n wählen wir im Beweis ein fn ∈ Mn.
Übung
Sei A eine Menge. Eine endliche Folge in A ist ein f : n → A mit n ∈ ℕ.
Sei F(A) die Menge aller endlichen Folgen in A.
(i) | Ist A abzählbar, so ist auch F(A) abzählbar. (Insbesondere ist also die „Menge aller Bücher“ abzählbar, selbst bei einem abzählbar unendlichen Zeichenvorrat A.) |
(ii) | Ist A abzählbar, so ist auch die Menge aller endlichen Teilmengen von A abzählbar. |
(iii) | Geben Sie eine bijektive Funktion g : F(ℕ) → ℕ direkt an. [ Wir verwenden Primzahlen. ] |
Der Autor erinnert sich gut, dass bei ihm selber die „Abzählbarkeit aller Bücher“ einen großen Eindruck hinterließ, als er ihr zum ersten Mal begegnete, und möchte deshalb bei dieser Idee noch ein wenig verweilen, und dem Leser hierzu noch etwas anbieten. Der Gedanke wird in vielen frühen Büchern ausgeführt, am schönsten aber vielleicht bei Hausdorff:
Hausdorff (1914):
„… Auch auf außermathematische Dinge ist diese Betrachtung häufig übertragen worden. Aus einem ‚Alphabet‘, d. h. einer endlichen Menge von ‚Buchstaben‘, kann man eine abzählbare Menge endlicher Buchstabenkomplexe, d. h. ‚Worte‘ bilden, unter denen sich natürlich auch sinnlose wie abracadabra befinden. Nimmt man zu den Buchstaben weitere Elemente wie Interpunktionszeichen, Druckspatien, Ziffern, Noten usw. hinzu, so sieht man, dass auch die Menge aller Bücher, Kataloge, Symphonien, Opern abzählbar ist und abzählbar bleiben würde, wenn man selbst abzählbar viele Zeichen (aber für jeden Komplex nur endlich viele) verwenden wollte. Beschränkt man dagegen, bei endlicher Zeichenzahl, die Komplexe auf eine Maximalzahl von Elementen, indem man etwa Worte von mehr als hundert Buchstaben und Bücher von mehr als einer Million Worten für unstatthaft erklärt, so werden diese Mengen endlich, und wenn man mit Giordano Bruno eine unendliche Menge von Weltkörpern annimmt, mit sprechenden, schreibenden und musizierenden Bewohnern, so folgt mit mathematischer Gewißheit, dass auf unendlich vielen dieser Weltkörper dieselbe Oper mit demselben Libretto, denselben Namen des Komponisten, des Textdichters, der Orchestermitglieder und Sänger aufgeführt werden muss.“
Ebenso verblüffend wäre es, wenn auf einem anderen Weltkörper ein gewisser Herr Puccini die Opern von Wagner geschrieben hätte, oder ein Herr Francis Bacon die Werke von William Shakespeare…
Es ist schwer vorstellbar, dass Felix Hausdorff bei dieser Passage nicht geschmunzelt haben sollte, etwa bei den Worten „für unstatthaft erklärt“. Andererseits steht hinter ihr ein „ernster“ Gedanke, der Hausdorff und seine Zeit sehr beschäftigt hatte, nämlich Nietzsches „ewige Wiederkunft des Gleichen“. Einige Anmerkungen hierzu findet der Leser in der Biographie von Hausdorff am Ende des zweiten Abschnitts.