Abzählbare Mengen
Die Abzählbarkeit einer Menge ist gewissermaßen ein Äquivalent zur Größe von Mengen, denn bei unendlichen Mengen kann man nicht mit der Anzahl der Elemente rechnen, weil die Anzahl der Elemente unerwarteterweise … unendlich ist. Die Größe einer Menge bezeichnen wir auch mit dem Begriff Kardinalität.
Größe einer unendlichen Menge
Die Größe einer endlichen Menge zu bestimmen ist einfach, wir zählen die Elemente. Die Menge M = {a; b; c; d; e} hat also die Größe 5, wir schreiben |M| = 5.
Bei unendlichen Mengen ist die Situation deutlich komplizierter. Wie könnten wir die Größe unendlicher Mengen vergleichen? Geht das überhaupt, oder sind alle unendlichen Mengen „gleich groß“?
Nehmen 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 möchte 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 enthalten und noch einige Elemente zusätzlich – die ungeraden Zahlen.
Wir könnten also schreiben, dass S ⊂ ℕ gilt, die Menge S ist eine echte Teilmenge der Menge ℕ. Und wir könnten sagen, dass die Menge ℕ größer ist, wenn S ⊂ ℕ – sie enthält ja mehr Elemente als die Menge S.
Einer der Gründe, warum wir Mengen nicht anhand der Teilmengenrelation messen können, ist die Tatsache, dass Mengen verschieden groß sein können, obwohl keine der beiden Mengen eine Teilmenge der anderen ist. Das lässt sich auch an endlichen Mengen zeigen: A = {1; 3; 4; 9} und B = {b; u; r; z; m}. Es gilt: |A| = 4 und |B| = 5. Die Menge B ist größer als die Menge A, trotzdem gilt aber nicht A ⊂ B. Bei unendlichen Mengen sehen wir das an den geraden und ungeraden Zahlen. Keine der beiden Mengen ist eine Teilmenge der anderen.
Die Teilmengenrelation wird also kein idealer Kandidat dafür sein, zu entscheiden, ob eine Menge größer ist als eine andere.
Bijektion
Versuchen wir einen anderen Ansatz. Wir haben zwei Mengen, A und B. Wir können sagen, dass sie gleich groß sind, wenn zwischen ihnen eine bijektive Abbildung existiert. Was bedeutet das? Dass wir ein Element aus der Menge A und ein Element aus der Menge B nehmen und ein Paar (a, b) bilden. Diese Elemente entfernen wir aus den Mengen und machen weiter. Gelingt es uns, beide Mengen zu „leeren“, haben wir eine bijektive Abbildung gefunden.
Beispiel an endlichen 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 aufgebraucht, wir haben eine bijektive Abbildung gefunden. Wichtig ist, dass dies nicht die einzige bijektive Abbildung ist. Auch das ist eine gültige Lösung: (a, 3), (b, 1), (c, 2).
Bei unendlichen Mengen ist es schon etwas interessanter. Versuchen wir es mit den ungeraden und geraden natürlichen Zahlen. Intuitiv spüren wir, dass es gleich viele sein müssten. Probieren wir es aus. Wir nehmen die erste ungerade Zahl und bilden sie auf die erste gerade Zahl ab: (1, 2). Weiter die zweite ungerade und die zweite gerade Zahl: (3, 4). Usw. So erhalten wir die Paare: (1, 2), (3, 4), (5, 6), (7, 8), … Wir könnten schreiben, dass jede ungerade Zahl l auf die gerade Zahl l + 1 abgebildet wird und jede gerade Zahl s das Bild der ungeraden Zahl s − 1 ist. Für jede ungerade und für jede gerade Zahl haben wir also ein Paar, das diese Zahl enthält. Die Mengen der ungeraden und der geraden Zahlen sind also gleich groß.
Gerade vs. natürliche Zahlen
Nun versuchen wir dasselbe Vorgehen und vergleichen die Menge der natürlichen und der geraden Zahlen. 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 sein wird.
Versuchen wir aber nun, die entsprechende bijektive Abbildung zu finden. Wir können sagen, dass jede natürliche Zahl n auf ihr Doppeltes abgebildet wird, auf 2n. Dadurch erhalten wir die Paare (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Für jede natürliche Zahl n haben wir also ein Paar (n, 2n) und für jede gerade Zahl s haben wir ein Paar (s/2, s). Wir haben eine bijektive Abbildung gefunden, die Menge der geraden Zahlen und die Menge der natürlichen Zahlen sind also gleich groß, sie haben dieselbe Kardinalität.
Das kann verwirrend wirken, denn die natürlichen Zahlen enthalten doch mehr Elemente als die geraden Zahlen. Die natürlichen Zahlen enthalten alle geraden Zahlen und dazu noch alle ungeraden Zahlen. Wir können aber eine Bijektion finden, also sind beide Mengen gleich groß.
Vergleich mit den natürlichen Zahlen
Die natürlichen Zahlen bestimmen in Wirklichkeit die kleinste Größe einer unendlichen Menge. Ob eine andere Menge dieselbe Größe hat wie die Menge der natürlichen Zahlen, lässt sich oft recht leicht feststellen – es genügt, eine Bijektion auf die natürlichen Zahlen zu finden, was in der Praxis bedeutet, dass es genügt, wenn wir die Elemente unserer Menge M nummerieren, anordnen können.
Können wir also die Elemente einer Menge so aufreihen, dass wir entscheiden können, welches Element das erste, welches das zweite, dritte, vierte, zehnte usw. ist, dann ist die Menge genauso groß wie ℕ. Eine solche Menge nennen wir dann abzählbar.
Leicht sehen wir, dass die geraden und die ungeraden natürlichen Zahlen abzählbar sind, denn wir können die erste, zweite, dritte usw. gerade bzw. ungerade Zahl bestimmen. Was ist mit den geraden ganzen Zahlen? Also mit der Menge S = {…; −4; −2; 0; 2; 4; …}. Können wir sie anordnen? Ja, wir nehmen einfach dieselbe Anordnung wie zuvor und schreiben gleich hinter die positive gerade Zahl auch ihre negative Variante: S = {0; 2; −2; 4; −4; 6; −6; …}. Ähnlich zum Beispiel für die ganzen Zahlen.
Größe der rationalen Zahlen
Ein interessanteres Beispiel sind die rationalen Zahlen, die Brüche. Können wir sie anordnen? Ja, aber es wird schon etwas komplizierter. Wir konstruieren eine Tabelle, die unendlich viele Zeilen und Spalten hat. In jeder Zelle steht ein Bruch. In der n-ten Spalte und der m-ten Zeile steht der Bruch n/m. In der 1. Spalte und der 2. Zeile haben wir also
Wie ordnen wir diese Zahlen nun an, wie nummerieren wir sie? Wir können sie nicht zeilenweise oder spaltenweise nummerieren, weil wir sofort in der jeweiligen Zeile/Spalte ertrinken würden. Stattdessen nehmen wir die Zahlen entlang der Diagonalen: (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 sind noch viele doppelte Brüche darin, aber das macht nichts. Was mehr stört, ist, dass keine negativen Zahlen darin sind. Das lässt sich einfach lösen: Immer wenn wir einen Bruch hinschreiben, setzen wir gleich hinter ihn seine negative Variante. Und dann fehlt uns ganz am Anfang nur noch die Null. Und das ist schon alles, wir haben alle rationalen Zahlen in einer Folge.
Insgesamt erhalten wir so die 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, …
Größe der reellen Zahlen
Sind die reellen Zahlen genauso groß wie die natürlichen Zahlen? Die Entscheidung wird noch komplizierter als bei den rationalen Zahlen. Wir führen einen Widerspruchsbeweis. Nehmen wir an, die reellen Zahlen sind abzählbar und es existiert eine bijektive Abbildung auf die natürlichen Zahlen. Nehmen wir also an, dass sie sich anordnen lassen. Und angenommen, die folgende Abbildung ist diese Anordnung:
In der Tabelle stehen die ersten sieben reellen Zahlen, die in unserer Anordnung vorkommen. Diese Anordnung kann natürlich beliebig sein, die Zahlen müssen nicht nach ihrer Größe sortiert sein.
Laut Annahme sind in dieser unendlichen Tabelle alle reellen Zahlen angeordnet. (Die Tabelle ist wieder unendlich, hier sind nur die ersten sieben Einträge.) Wir versuchen jetzt, eine Zahl zu finden bzw. zu konstruieren, die reell ist, aber in dieser Tabelle nicht vorkommt. Finden wir eine solche Zahl, dann ist das ein Widerspruch dazu, dass in der Tabelle alle reellen Zahlen stehen, woraus wir weiter schließen können, dass die Menge der reellen Zahlen nicht abzählbar ist.
Jene Zahl, die in der Tabelle nicht vorkommt, konstruieren wir so:
Wir beginnen damit, dass wir 0,… schreiben. So wird unsere neue reelle Zahl am Anfang aussehen. An der ersten Dezimalstelle steht dann eine Ziffer, die nicht an der ersten Stelle der ersten reellen Zahl unserer Anordnung steht (in der Tabelle ist sie mit einem Rahmen hervorgehoben). Dort steht die Ziffer 3, also wählen wir zum Beispiel 1 und erhalten die Zahl 0,1…
Wir machen weiter. An der zweiten Stelle steht eine Ziffer, die nicht an der zweiten Stelle der zweiten reellen Zahl steht. Dort steht 9, also zum Beispiel 2. Wir erhalten die Zahl 0,12… An der dritten Stelle steht eine Ziffer, die sich von der dritten Ziffer der dritten reellen Zahl unterscheidet. Dort steht 3, also wählen wir etwa 7. Wir erhalten 0,127…
Und so weiter und so fort. An der n-ten Position der neuen Zahl steht immer eine Ziffer, die sich von der Ziffer an der n-ten Position der n-ten Zahl in unserer Anordnung unterscheidet.
Was erreichen wir damit? Wir erhalten eine Zahl, die sich von allen Zahlen in unserer Anordnung in mindestens einer Ziffer unterscheidet. Nehmen wir das letzte vorläufige Ergebnis: 0,127… Diese Zahl unterscheidet sich sicher von der ersten Zahl in unserer Anordnung mindestens in der ersten Ziffer – weil wir sie so konstruiert haben. Von der zweiten Zahl unterscheidet sie sich mindestens in der zweiten Ziffer. Von der dritten in der dritten Ziffer. Allgemein unterscheidet sich diese neue Zahl von der Zahl der Anordnung, die an n-ter Stelle steht, mindestens in der Ziffer an der n-ten Position.
Diese neu konstruierte Zahl finden wir also nicht in der Tabelle, die eine Bijektion zwischen den natürlichen und den reellen Zahlen darstellen sollte. Es gibt also mehr reelle Zahlen als natürliche Zahlen. Die reellen Zahlen sind nicht abzählbar, sie sind überabzählbar.
Weitere Quellen
Kapitel: Mengen, Vereinigung, Schnitt, Differenz und Komplement von Mengen, Abzählbare Mengen, Paradoxe der Mengenlehre
