Abzählbare Mengen
Kapitoly: Quantitäten, Plural Operationen, Abzählbare Mengen, Paradoxien der Mengenlehre
Die Abzählbarkeit einer Menge ist eine Art Äquivalent zur Größe von Mengen, denn bei unendlichen Mengen kann die Anzahl der Elemente nicht gezählt werden, weil die Anzahl der Elemente unerwartet ... unendlich ist. Die Größe einer Menge wird auch mit dem Begriff Kardinalität bezeichnet.
Die Größe einer unendlichen Menge
Die Bestimmung der Größe einer endlichen Menge ist einfach: Wir zählen die Anzahl der Elemente. So hat die Menge M = {a, b, c, d, e} die Größe 5, wir schreiben |M| = 5.
Bei unendlichen Mengen ist die Situation viel komplizierter. Wie können wir die Größe von unendlichen Mengen vergleichen? Ist das überhaupt möglich, oder sind alle unendlichen Mengen "gleich groß"?
Betrachten wir als Beispiel die Menge der natürlichen Zahlen und die Menge der geraden natürlichen Zahlen. Wir haben also die Mengen ℕ = {1, 2, 3, 4, 5, 6, …} und S = {2, 4, 6, …}. Man würde gerne sagen, dass die Menge der natürlichen Zahlen größer ist als die Menge der geraden Zahlen, weil die natürlichen Zahlen alle geraden Zahlen plus einige zusätzliche Elemente - die ungeraden Zahlen - enthalten.
Wir könnten also schreiben, dass S ⊂ ℕ, die Menge S eine echte Teilmenge der Menge ℕ ist. Und wir könnten sagen, dass wenn S ⊂ ℕ, dann ist die Menge ℕ größer - sie enthält mehr Elemente als die Menge S.
Ein Grund dafür, dass wir Mengen nicht anhand der Teilmengenrelation messen können, ist, dass Mengen unterschiedlich groß sein können, obwohl keine der beiden Mengen eine Teilmenge der anderen ist. Dies lässt sich an endlichen Mengen demonstrieren: A = {1, 3, 4, 9} und B = {b, u, r, z, m}. Es ist wahr: |A| = 4 und |B| = 5. Die Menge B ist größer als die Menge A, aber es ist nicht wahr A ⊂ B. Bei unendlichen Mengen können wir dies an geraden und ungeraden Zahlen sehen. Keine der beiden Mengen ist eine Teilmenge der anderen.
Daher ist eine Teilmengenbeziehung kein idealer Kandidat, um zu entscheiden, ob eine Menge größer als eine andere ist.
Bijekce
Versuchen wir einen anderen Ansatz. Wir haben zwei Mengen, A und B. Wir können sagen, dass sie gleich groß sind, wenn es eine bijektive Abbildung zwischen ihnen gibt. Was bedeutet das? Wir nehmen ein Element aus der Menge A, ein Element aus der Menge B, und bilden ein Paar [a, b]. Wir entfernen diese Elemente aus den Mengen und fahren fort. Wenn wir beide Mengen "leeren" können, haben wir eine bijektive Darstellung gefunden.
Ein Beispiel für endliche Mengen: A = {a, b, c} und B = {1, 2, 3}. Das erste Paar könnte [a, 1] sein, das nächste [b, 2] und schließlich [c, 3]. Wir haben alle Elemente aus beiden Mengen ausgeschöpft, wir haben eine bijektive Darstellung gefunden. Wichtig ist, dass dies nicht die einzige bijektive Darstellung ist. Dies ist auch eine gültige Lösung: [a, 3], [b, 1], [c, 2].
Für unendliche Mengen wird es etwas interessanter. Versuchen wir es mit ungeraden und geraden natürlichen Zahlen. Intuitiv haben wir das Gefühl, dass es die gleiche Anzahl von ihnen geben sollte. Versuchen wir dies. Wir nehmen die erste ungerade Zahl und bilden sie auf die erste gerade Zahl ab: [1, 2]. Dann die zweite ungerade Zahl und die zweite gerade Zahl: [3, 4]. Und so weiter. So erhalten wir die Paare: [1, 2], [3, 4], [5, 6], [7, 8], … Wir könnten schreiben, dass jede ungerade Zahl l auf eine gerade Zahl l + 1 abgebildet wird und jede gerade Zahl s das Bild einer ungeraden Zahl s − 1 ist. So haben wir für jede ungerade Zahl und für jede gerade Zahl ein Paar, das diese Zahl enthält. Die Mengen der ungeraden und geraden Zahlen sind also gleich groß.
Gerade vs. natürliche Zahlen
Nun wollen wir dasselbe Verfahren anwenden und die Menge der natürlichen und der geraden Zahlen vergleichen. Wir haben also die Mengen ℕ = {1, 2, 3, 4, 5, 6, …} und S = {2, 4, 6, …}. Intuitiv erwarten wir, dass die Menge der natürlichen Zahlen größer ist.
Aber versuchen wir nun, eine gegebene bijektive Darstellung zu finden. Wir können sagen, dass jede natürliche Zahl n auf ihr bijektives Gegenstück 2n abgebildet wird. Damit haben wir das Paar [1, 2], [2, 4], [3, 6], [4, 8], [5, 10], …. Für jede natürliche Zahl n haben wir also das Paar [n, 2n] und für jede gerade Zahl s haben wir das Paar [s/2, s]. Wir haben eine bijektive Abbildung gefunden, die Menge der geraden Zahlen und die Menge der natürlichen Zahlen sind beide gleich groß, sie haben die gleiche Kardinalität.
Dies mag verwirrend erscheinen, da die natürlichen Zahlen mehr Elemente enthalten als die geraden Zahlen. Die natürlichen Zahlen enthalten alle geraden Zahlen und alle ungeraden Zahlen. Wir können jedoch eine Bijektion finden, so dass die beiden Mengen gleich groß sind.
Vergleich mit natürlichen Zahlen
Die natürlichen Zahlen sind eigentlich durch die kleinste Größe einer unendlichen Menge definiert. Ob eine andere Menge die gleiche Größe wie die Menge der natürlichen Zahlen hat, lässt sich oft recht einfach herausfinden - wir müssen nur die Bijektion zu den natürlichen Zahlen finden, was in der Praxis bedeutet, dass wir die Elemente unserer Menge M einfach nur nummerieren und anordnen können müssen.
Das heißt, wenn wir die Elemente der Menge so anordnen können, dass wir entscheiden können, welches Element das erste, zweite, dritte, vierte, zehnte usw. ist, dann ist die Menge so groß wie ℕ. Wir sagen dann, dass eine solche Menge abzählbar ist.
Wir können leicht sehen, dass gerade und ungerade natürliche Zahlen abzählbar sind, weil wir die ersten, zweiten, dritten usw. geraden/ungeraden Zahlen bestimmen können. Was ist mit geraden ganzen Zahlen? D.h. die Menge S = {…, −4, −2, 0, 2, 4, …}. Können wir sie anordnen? Ja, wir können die gleiche Reihenfolge wie beim letzten Mal verwenden und direkt nach der positiven geraden Zahl ihre negative Variante aufschreiben: S = {0, 2, −2, 4, −4, 6, −6, …} Ähnlich verhält es sich zum Beispiel mit den ganzen Zahlen.
Die Größe der rationalen Zahlen
Ein interessanteres Beispiel sind die rationalen Zahlen, die Brüche. Kann man sie anordnen? Man kann, aber es ist etwas komplizierter. Konstruieren wir eine Tabelle mit unendlich vielen Zeilen und Spalten. In jeder Zelle befindet sich ein Bruch. In der n-ten Zeile und m-ten Spalte haben wir den Bruch n/m. In der 1. Zeile und 2. Spalte haben wir also $\frac12$ und in der 3. Zeile und 4. Spalte 3/4.
$$\begin{array}{ccccc} 1/1&2/1&3/1&4/1&…\\ 1/2&2/2&3/2&4/2&…\\ 1/3&2/3&3/3&4/3&…\\ 1/4&2/4&3/4&4/4&…\\ …&…&…&…&… \end{array}$$
Wie können wir nun diese Zahlen sortieren und nummerieren? Wir können sie nicht nach Zeilen oder Spalten nummerieren, weil wir dann sofort in dieser Zeile/Spalte untergehen würden. Stattdessen nehmen wir die Zahlen diagonal: (erste Diagonale:) 1/1, (zweite Diagonale:) 2/1, 1/2, (dritte Diagonale:) 3/1, 2/2, 1/3, (vierte Diagonale:) 4/1, 3/2, 2/3, 1/4, ... Es gibt immer noch eine Menge doppelter Brüche, aber das ist in Ordnung. Was mehr stört, ist, dass es keine negativen Zahlen gibt. Das lässt sich leicht lösen: Jedes Mal, wenn wir einen Bruch schreiben, setzen wir seine negative Variante direkt dahinter. Und dann fehlt uns die Null ganz am Anfang. Und das war's, wir haben alle rationalen Zahlen in der Folge.
Alles in allem erhalten wir eine Folge: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …
Die Größe der reellen Zahlen
Sind die reellen Zahlen gleich groß wie die natürlichen Zahlen? Die Entscheidung wird noch komplizierter als im Fall der rationalen Zahlen. Führen wir einen Widerspruchsbeweis durch. Nehmen wir an, dass die reellen Zahlen abzählbar sind und dass es eine bijektive Abbildung auf die natürlichen Zahlen gibt. Nehmen wir also an, dass sie geordnet werden können. Und nehmen wir an, die folgende Abbildung ist diese Ordnung:
$$\begin{array}{ccccccccc} 0,&3&5&2&2&4&6&0&\ldots\\ 0,&2&9&2&4&3&7&5&\ldots\\ 0,&7&2&3&0&8&4&5&\ldots\\ 0,&1&4&3&7&9&0&6&\ldots\\ 0,&0&8&6&5&7&5&8&\ldots\\ 0,&7&5&4&6&3&6&3&\ldots\\ 0,&3&4&1&9&7&0&0&\ldots\\ \ldots \end{array}$$
Es gibt die ersten sieben reellen Zahlen in der Tabelle, die sich in unserer Anordnung befinden. Diese Anordnung kann natürlich beliebig sein, sie muss nicht nach der Größe der Zahlen geordnet sein.
Wir gehen davon aus, dass alle reellen Zahlen in dieser unendlichen Tabelle angeordnet sind (auch hier ist die Tabelle unendlich; hier gibt es nur die ersten sieben Einträge). Wir werden nun versuchen, eine reelle Zahl zu finden/zu ordnen, die nicht in dieser Tabelle aufgeführt ist. Wenn wir eine solche Zahl finden, ist das ein Widerspruch zu der Tatsache, dass alle reellen Zahlen in der Tabelle stehen, woraus wir weiter schließen können, dass die Menge der reellen Zahlen nicht abzählbar ist.
Wir konstruieren die Zahl, die nicht in der Tabelle enthalten ist, wie folgt:
$$\begin{array}{ccccccccc} 0,&\fbox{3}&5&2&2&4&6&0&\ldots\\ 0,&2&\fbox{9}&2&4&3&7&5&\ldots\\ 0,&7&2&\fbox{3}&0&8&4&5&\ldots\\ 0,&1&4&3&\fbox{7}&9&0&6&\ldots\\ 0,&0&8&6&5&\fbox{7}&5&8&\ldots\\ 0,&7&5&4&6&3&\fbox{6}&3&\ldots\\ 0,&3&4&1&9&7&0&\fbox{0}&\ldots\\ \ldots \end{array}$$
Wir beginnen mit der Eingabe von 0,…. So sieht unsere neue reelle Zahl am Anfang aus. Die erste Nachkommastelle ist dann eine Ziffer, die in der ersten reellen Zahl unserer Anordnung nicht an erster Stelle steht (dies ist in der Tabelle durch ein Kästchen hervorgehoben). Es gibt die Ziffer 3, also wählen wir zum Beispiel 1 und erhalten die Zahl 0,1…
Wir fahren fort. Die zweite Ziffer ist diejenige, die sich nicht an der zweiten Stelle der zweiten reellen Zahl befindet. Es gibt 9, also zum Beispiel 2. Wir erhalten die Zahl 0,12…. An dritter Stelle steht eine Ziffer, die sich von der dritten Ziffer der dritten reellen Zahl unterscheidet. Es gibt 3, also wählen wir z.B. 7. Wir erhalten 0, 127…
Und so weiter und so fort. Es wird immer eine Ziffer an der n-ten Stelle der neuen Zahl stehen, die sich von der Ziffer an der n-ten Stelle der n-ten Zahl in unserer Anordnung unterscheidet.
Was erhalten wir also? Wir erhalten eine Zahl, die sich von allen Zahlen in unserer Anordnung um mindestens eine Ziffer unterscheidet. Nehmen wir das letzte vorläufige Ergebnis: 0,127… Diese Zahl unterscheidet sich definitiv von der ersten Zahl in unserer Anordnung um mindestens die erste Ziffer - denn so haben wir es eingerichtet. Sie unterscheidet sich von der zweiten Zahl mindestens in der zweiten Ziffer. Von der dritten unterscheidet sie sich in der dritten Ziffer. Im Allgemeinen unterscheidet sich diese neue Zahl von den Zahlen in der Anordnung, die sich in n-ter Position befindet, in mindestens einer Ziffer in n-ter Position.
Daher findet sich diese neu konstruierte Zahl nicht in der Tabelle, die die Bijektion zwischen den natürlichen Zahlen und den reellen Zahlen symbolisieren soll. Die reellen Zahlen sind also größer als die natürlichen Zahlen. Die reellen Zahlen sind nicht abzählbar, sie sind nicht abzählbar.