3.1 Wer ist größer?

Für endliche Mengen haben den Begriff der Größe ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ hat zehn Elemente und ist somit größer als ${a, e, i, o, u}$ , die nur fünf Elemente hat. Können wir auch für unendliche Mengen einen Größenbegriff einführen, oder sie zumindest hinsichtlich ihrer Größe vergleichen?

Bei den "üblichen" unendlichen Mengen $N, Z, Q, R$ scheint das zu gehen. Es gilt nämlich $N ⊊ Z ⊊ Q ⊊ R$ , und damit können wir doch mit Fug und Recht behaupten: Die Menge der ganzen Zahlen ist kleiner als die der rationalen Zahlen.

Unser erster Versuch, unendliche Mengen ihrer Größe nach zu vergleichen, verwendet Mengeninklusion: wenn $A \subseteq B$ gilt, dann sagen wir, dass $A$ kleiner gleich $B$ gilt. Allerdings hat dieser Größenbegriff einen großen Nachteil: welche der beiden Mengen ist Ihrer Meinung denn größer:

\begin{array}{r} {\dots, - 4, - 2, 0, 2, 4, 6, \dots} oder {0, 1, 2, 3, \dots} ? \end{array}

Also die geraden ganzen Zahlen oder die natürlichen? Oder noch schlimmer: ist $Q$ oder ${a, b}^{*}$ größer? Die zweite Menge hat ja gar nichts mit Zahlen zu tun, sondern besteht aus Strings mit den Symbolen $a$ und $b$ . Und generell: auch zwischen den Mengen ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ und ${a, e, i, o, u}$ gibt es keine Inklusionsrelation, und dennoch ist erstere ganz klar größer als letztere.

Eine rigorose und belastbare Weise, unendliche Mengen hinsichtlich ihrer Größe zu vergleichen, hat Georg Cantor Ende des 19. Jahrhunderts gefunden. Sie war anfangs nicht unumstritten.

Beispiel 3.1.1 Beginnen wir mit einem einfachen Beispiel und betrachten die zwei Mengen $N = {0, 1, 2, 3, 4, \dots}$ und $N^{+} = {1, 2, 3, 4, \dots}$ . Beide sind unendlich, und $N^{+} ⊊ N$ . Dennoch sind sie in gewisser Weise gleich groß. Ihre Elemente lassen sich nämlich einander paarweise zuordnen:

Wir können diese Zuordnung auch mit einer einfachen Formel beschreiben. Die Funktion

\begin{aligned} f : N & \to N^{+} \\ n & \mapsto n + 1 \end{aligned}

ist eine Bijektion.

Diese anfangs etwas überraschende Tatsache, dass $N$ und $N^{+}$ "gleich groß" sind, ist als Hilberts Hotel bekannt. Das Hotel hat unendlich viele Zimmer, für jede Zahl $n \in N^{+}$ eins. Dann kommt ein neuer Gast (die $0$ ) und braucht ein Zimmer. Er kriegt das Zimmer $1$ . Da dies aber schon belegt ist, wird die Person, die bisher in Zimmer 1 logiert hat, auf Zimmer 2 verlegt; die dortige auf Zimmer 3, und so weiter. Das Hotel ist also voll belegt, kann aber dennoch weitere Gäste aufnehmen.

Beispiel 3.1.2 Ermutigt von unserem Erfolg gerade eben betrachten wir zwei unendliche Mengen, die sich stärker unterscheiden: $N$ und $Z = {\dots, - 2, - 1, 0, 1, 2, \dots}$ . Wir können diese beiden nicht so schön nebeneinander legen wie $N$ und $N^{+}$ in der obigen Abbildung. Um die Elemente paarweise zuzuordnen, müssen wir hin- und herspringen:

Dies ist etwas unübersichtlich. Besser geht es, wenn wir $Z$ umstellen:

Wir können also unsere Bijektion $f : N \to Z$ wie folgt definieren:

\begin{aligned} f : N & \to Z \\ n & \mapsto {\begin{cases} \frac{n}{2} & wenn n gerade ist, \\ - \frac{n + 1}{2} & wenn n ungerade ist. \end{cases} \end{aligned}

Übungsaufgabe 3.1.1 Finden Sie eine "geschlossene" Form für die Bijektion $f : N \to Z$ . Mit "geschlossen" meine ich, dass Sie sie mit den üblichen Operatoren (mal, plus, hoch, minus, geteilt durch) ohne Fallunterscheidung schreiben können.

Anmerkung: es ist überhaupt nicht schlimm, eine Funktion mit einer Fallunterscheidung zu definieren. Sie ist dadurch nicht etwa eine "Funktion zweiter Klasse".

Übungsaufgabe 3.1.2 Finden Sie die Umkehrfunktion $f^{- 1} : Z \to N$ . Gerne anfangs mit Fallunterscheidung, dann bitte als geschlossene Formel ohne Fallunterscheidung.

Wir sind nun reif für eine formale Definition:

Definition 3.1.3 Zwei Mengen und heißen gleichmächtig, wenn es eine Bijektion gibt. Wir schreiben in diesem Falle .

Es gilt trivialerweise immer , da wir ja die Identitätsfunktion als Bijektion nehmen können. Wenn es eine Bijektion gibt, dann natürlich auch eine Umkehrfunktion . Wenn und Bijektionen sind, dann ist auch eine. Wir sehen: Die Relation ist reflexiv, symmetrisch und transitiv und ist somit eine Äquivalenzrelation.

Definition 3.1.4 Eine Menge mit , die also gleichmächtig zu den natürlichen Zahlen ist, nennt man abzählbar unendlich, auf Englisch countably infinite oder einfach countable.

Wie wir sehen werden, gibt es tatsächlich unendliche Mengen, die nicht gleichmächtig mit sind, weil sie "viel viel größer" sind. Wir nennen sie überabzählbare Mengen, auf Englisch uncountably infinite.

Was ist unendlich?

Der Begriff der Gleichmächtigkeit liefert uns nun eine wunderbar einfache und rigorose Definition von Unendlichkeit.

Definition 3.1.5 Eine Menge heißt unendlich, wenn es eine echte Teilmenge gibt, zu der sie gleichmächtig ist, also .

Als Beispiel haben wir mit gesehen. Also ist im obigen Sinne unendlich.

Übungsaufgabe 3.1.3 Zeigen Sie: wenn eine Menge unendlich ist (im Sinne der obigen Definition), dann gibt es eine Teilmenge mit .

Hinweis: Tappen Sie nicht in die "Das ist doch offensichtlich"-Falle: die Menge könnte ja viel größer sein als und keine für Sie "greifbare" Struktur haben. Ihre Aufgabe ist es, dennoch eine abzählbar unendliche Teilmenge zu finden.

Angesichts der letzten Übungsaufgabe können wir also sagen, dass abzählbare Unendlichkeit die kleinste Stufe der Unendlichkeit ist. Unterhalb von abzählbar kommen nur noch die endlichen Mengen.