7.Abzählbare Mengen

 Die einfachste unendliche Menge, die wir kennen, ist die Menge  der natürlichen Zahlen. Die natürlichen Zahlen werden insbesondere zum Zählen, Indizieren, Durchnumerieren, Ordnen, etc. anderer Mengen verwendet. Dies führt zu folgendem Begriff, der alle Mengen beschreibt, die sich durch natürliche Zahlen in dieser Weise kontrollieren lassen:

Definition (abzählbare Mengen)

Eine Menge M heißt abzählbar, falls gilt:

(i)

es existiert ein bijektives f : n  M für ein n  ∈  oder

(ii)

es existiert ein bijektives f :   M.

 Der Begriff „abzählbar“ entspricht folgender Anschauung. Eine Menge M ist abzählbar, wenn wir alle Elemente x, y, z, … von M der Reihe nach auf -viele Plätze verteilen können:

mengenlehre1-AbbID25

 Dabei ist für unendliche Mengen eine „geschickte“ Platzanweisung notwendig: Ist etwa M = , und besetzen wir Platz n mit der Zahl 2n, so bleiben „am Ende“ die ungeraden Zahlen stehen, obwohl  sicher abzählbar ist. Aus den Resultaten des vorangehenden Kapitels folgt, dass für endliche Mengen ein geschickter Platzanweiser entbehrlich ist: Nach jeder Platzzuweisung einer Menge mit genau n Elementen ist immer der Platz n der erste freie Sitz.

 Die -Endlichkeit, die wir zur Definition von abzählbar verwendet haben, scheint der intuitiven Bedeutung des Wortes „abzählen“ näher zu sein als die (äquivalente) Dedekind-Endlichkeit.

 Wir können auch Platzanweisungen betrachten, bei denen einige Plätze freibleiben dürfen, bevor ein neuer Platz besetzt wird:

mengenlehre1-AbbID26

 Eine solche lückenhafte Verteilung kann bequem durch eine Injektion von einer Menge in die natürlichen Zahlen beschrieben werden. Durch ein intuitiv klares, aber recht aufwendig zu organisierendes Nachrückverfahren − man denke an ein dunkles Kino − erhalten wir „richtige“ Abzählungen. Einfacher ist es an den Sitzen entlangzugehen und dabei M neu abzuzählen, wie dies im Beweis des folgenden Satzes geschieht.

Satz (Abzählbarkeit und Einbettbarkeit in die natürlichen Zahlen)

Sei M eine Menge. Dann sind äquivalent:

(i)

M ist abzählbar.

(ii)

|M|  ≤  ||.

Beweis

(i)  (ii):

Ist M abzählbar, so ist |M| = |n| für ein n  ∈   oder |M| = ||.

In beiden Fällen ist offenbar |M| ≤ ||.

(ii)  (i):

Sei |M| ≤ || und f : M   injektiv. Wir zählen nun rng(f) ⊆  monoton auf. Hierzu definieren wir durch Rekursion über n  ∈    solange möglich eine Funktion g wie folgt:

g(n) =  „das kleinste k  ∈  rng(f) mit k > g(i) für alle 0 ≤ i < n“, falls  ein solches k existiert.

Sei N = dom(g). Dann ist g : N  rng(f) bijektiv. Also ist f  − 1 ∘ g : N  M bijektiv. Aber es gilt N = n für ein n  ∈   oder N =  (!). Also ist M abzählbar.

 Zu einem schnellen Beweis führt natürlich eine Unterscheidung „rng(f) endlich“, also |M| = |rng(f)| = |n| für ein n  ∈  , oder „rng(f) unendlich“ also |M| = |rng(f)| = || zu einer Funktion g wie gewünscht, die dann aber mit f i. A. nichts mehr zu tun hat. Unsere Funktion g erhält die durch f gegebene Sitzordnung. Ein derartiges strukturelles Zusammenziehen eines Wertebereichs ist in der Mengenlehre vielfach nützlich.

 Es gilt f −1 ∘ g = h−1 mit h(x) = „das n  ∈   mit |n| = |{ y  ∈  M | f (y) < f (x) }|“ für x  ∈  M.

 Wir zeigen nun, dass jede unendliche Menge eine abzählbar unendliche Teilmenge besitzt. „Abzählbar unendlich“ ist also die erste „Anzahl“ nach den endlichen Größen.

Satz

Sei M eine unendliche Menge.

Dann existiert eine abzählbar unendliche Teilmenge von M.

Beweis

Wegen M unendlich gilt || ≤ |M| nach dem Satz über die Einbettbarkeit der natürlichen Zahlen in unendliche Mengen. Sei also f :   M injektiv. Dann ist rng(f) eine abzählbar unendliche Teilmenge von M.

 Der Beweis des Satzes ist elementar, da M als (Dedekind-)unendlich vorausgesetzt wird. Jedoch ist für den Beweis, dass jede -unendliche Menge eine abzählbar unendliche Teilmenge enthält, ein Auswahlakt notwendig. Man definiert hierzu rekursiv:

xn  =  „ein x  ∈  M mit x ≠ xi für alle 0 ≤ i < n“.

Aus M -unendlich folgt, dass diese Rekursion nicht abbricht. X = { xn | n  ∈   } ist dann eine abzählbar unendliche Teilmenge von M.

Die entscheidende Frage ist nun:

Ist jede Menge abzählbar?

Anders formuliert:

Ist jede unendliche Menge M gleichmächtig zu den natürlichen Zahlen, d. h. existiert für jede unendliche Menge M ein bijektives f :   M?

 Das Konzept der Mächtigkeit wäre dann nicht besonders interessant, denn jede Menge wäre dann entweder vom „Größentyp“ n = { 0, … , n − 1 } für ein n  ∈  , oder aber vom Typ .

 Es zeigt sich zunächst: Viele prominente Mengen sind abzählbar. Dies wollen wir jetzt von den ganzen, den rationalen und den algebraischen Zahlen zeigen. Zudem führen viele Operationen mit abzählbaren Mengen nicht aus dem Reich der Abzählbarkeit heraus.