Mathe für Nicht-Freaks: Mächtigkeit von Mengen

Warnung: Das folgende Kapitel enthält stark kontraintuitive Aussagen. Beim Lesen kann es zu Erstaunen und Verblüffung kommen. Ihr Körper wird sich mit der Zeit an diese Aussagen gewöhnen.

In diesem Kapitel werden wir uns mit der Frage beschäftigen, wann zwei Mengen gleich groß sind. Hier werden wir insbesondere unendliche Mengen auf ihre Größe untersuchen. Dabei werden wir auf Ergebnisse stoßen, die scheinbar Paradox sind und unserer Erwartung widersprechen. Dies ist auch der Grund, warum viele Mathematiker die Frage nach der Größe unendlicher Mengen vermieden haben oder ihre erste Beantwortung durch Georg Cantor (1845-1918) abgelehnt haben. So schrieb Carl Friedrich Gauß (1777-1855):

„Ich verabscheue es, wenn ein unendliches Objekt wie ein vollständig gegebenes Objekt verwendet wird. In der Mathematik ist diese Operation verboten; das Unendliche ist eine Redensart“

Wir werden in diesem Kapitel sehr ausführlich das Unendliche untersuchen.

Bevor wir aber der Frage nach der Größe unendlicher Mengen nachgehen, möchte ich, dass du folgende Fragen für dich beantwortest (du kannst auch „aus dem Bauch“ antworten):

Beantworte intuitiv: Welche der folgenden Mengen ist größer? Welche der folgenden Mengen besitzt mehr Elemente?

• Menge der natürlichen Zahlen $\N$ oder die Menge der Quadratzahlen $Q=\{ n^2 \,|\, n\in \N\}$
• Menge der natürlichen Zahlen $\N$ oder die Menge der ganzen Zahlen $\Z$
• Menge der natürlichen Zahlen $\N$ oder die Menge der rationalen Zahlen $\Q$
• Menge der natürlichen Zahlen $\N$ oder die Menge der reellen Zahlen $\R$

Diese Fragen werden wir in diesem Kapitel beantworten.

Wann sind zwei Mengen gleich groß?

Die Grundfrage

Wann besitzen zwei Mengen $A$ und $B$ gleich viele Elemente? Im Fall, dass $A$ und $B$ endliche Mengen sind, ist diese Frage einfach zu beantworten: Man zählt die Elemente beider Mengen und vergleicht diese Anzahl miteinander. Doch diese Methode kann nicht auf den Fall übertragen werden, dass eine der beiden Mengen unendlich ist.

Nun könnte man annehmen, dass alle unendlichen Mengen gleich groß sind. Schließlich bezeichnen wir die Größe dieser Menge in unserer Alltagssprache mit demselben Wort: „unendlich“. Wir werden aber sehen, dass diese Annahme zu nicht sinnvollen Ergebnissen führen würde und dass es unterschiedliche Arten der Unendlichkeit gibt.

Da das Zählen der Elemente bei unendlichen Mengen fehlschlägt, müssen wir eine andere Methode finden, Mengen miteinander zu vergleichen. Schauen wir uns ein Beispiel aus der endlichen Welt an: Stell dir vor, dass du zwei Kisten mit unterschiedlich großen Steinen hast und wissen willst, in welcher Kiste mehr Steine sind. Leider hast du keinerlei Messgeräte und zählen kannst du auch nicht. Wie kannst du vorgehen?

Frage: Wie kannst feststellen, in welcher Kiste mit unterschiedlich großen Steinen mehr Steine sind, ohne dass du zählst oder irgendwelche Hilfsmittel benutzt?

Die Antwort auf die Grundfrage

Eine Möglichkeit ist Folgende: Du kannst die Steine beider Kisten in zwei Reihen so nebeneinander anordnen, dass jeweils ein Stein der einen Kiste neben ein Stein der anderen Kiste liegt. Ist eine Reihe von Steinen länger als die andere, so besitzt sie auch mehr Steine als die andere. Kann jeweils ein Stein der einen Kiste neben ein Stein der anderen Kiste gelegt werden und umgekehrt, so waren in den beiden Kisten dieselbe Anzahl von Steinen.

Was haben wir hier gemacht? Wir haben zwei endliche Mengen $A$ und $B$, die wir vergleichen wollen. Nun haben wir nacheinander jeweils ein Element $a\in A$ und ein Element $b\in B$ einander zugeordnet. Dabei war diese Zuordnung eineindeutig. „eineindeutig“ bedeutet, dass dem Element $a$ ein eindeutiges $b$ und dem Element $b$ ein eindeutiges Element $a$ zugeordnet wird. Waren wir damit in dem Sinn erfolgreich, dass wir jedem $a\in A$ ein eindeutiges $b\in B$ und jedem $b\in B$ ein eindeutiges $a\in A$ zuordnen konnten, dann sind beide Mengen gleich groß. Ist eine solche eineindeutige Zuordnung zwischen den Mengen $A$ und $B$ unmöglich, sind beide Mengen unterschiedlich groß.

Eine solche eineindeutige Zuordnung zwischen zwei Mengen ist aber nichts anderes als eine bijektive (umkehrbare) Abbildung zwischen den diesen beiden Mengen. Dementsprechend sind zwei endliche Mengen genau dann gleich groß, wenn es zwischen ihnen eine bijektive Abbildung gibt. Dieses Merkmal gleich großer endlicher Mengen kann auch auf unendliche Mengen übertragen werden.

So haben wir eine Methode gefunden, zwei Mengen miteinander zu vergleichen: Zwei Mengen sind genau dann gleich groß, wenn eine bijektive Abbildung zwischen ihnen möglich ist. An dieser Stelle möchte ich noch darauf hinweisen, dass in der Mathematik eher von der Mächtigkeit als von der Größe von Mengen die Rede ist. So würde ein Mathematiker anstatt „zwei Mengen sind gleich groß“ eher „zwei Mengen sind gleich mächtig“ sagen. Ich werde in diesem Kapitel auf beide Begriffe zurückgreifen.

Definition (Mächtigkeit von Mengen): Zwei Mengen $A$ und $B$ sind dann und nur dann gleich mächtig, wenn es möglich ist, zwischen ihnen eine bijektive Abbildung $f: A\rightarrow B$ zu definieren.

Beispiele

Schauen wir uns nun die obigen Beispiele an, bei denen du dich intuitiv entscheiden solltest, welche Menge mehr Elemente enthält.

Menge der natürlichen Zahlen und Menge der Quadratzahlen

Welche Menge ist nun größer: die Menge der natürlichen Zahlen $\N$ oder die Menge der Quadratzahlen $Q=\{ n^2 \,|\, n\in \N \}$? Ist es möglich eine Bijektion zwischen $\N$ und $Q$ zu finden?

Ja, es gibt eine bijektive Abbildung zwischen $\N$ und $Q$, nämlich die Abbildung $f: \N \rightarrow Q: n \mapsto n^2$. Also die Abbildung

$\begin{array}{ccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots\\[3px] \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \cdots \\[3px] 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 & \cdots\\ \end{array}$

Es gibt also eine Abbildung, die jeder natürlichen Zahl eine eineindeutige Quadratzahl zuordnet. So sieht man, dass es genauso so viele natürliche Zahlen gibt, wie es Quadratzahlen gibt. Dies ist ein erstes überraschendes Ergebnis: Denn aus der Tatsache, dass die Menge der Quadratzahlen eine echte Teilmenge der natürlichen Zahlen ist und dass es in fast jeder endlichen Teilmenge der natürlichen Zahlen mehr natürliche Zahlen als Quadratzahlen gibt, könnte man vermuten, dass die Menge der natürlichen Zahlen mehr Elemente enthält als die Menge der Quadratzahlen. Dies ist aber, wie wir gerade gesehen haben, nicht der Fall.

Du siehst: Für unendliche Mengen ist der in der endlichen Welt gültige Satz „Ist $A$ eine echte Teilmenge der Menge $B$, dann besitzt $B$ mehr Elemente als $A$“ nicht mehr anwendbar.

Menge der natürlichen Zahlen und Menge der ganzen Zahlen

Kommen wir zum nächsten Beispiel:

Frage: Ist die Menge der natürlichen Zahlen $\N$ und die Menge der ganzen Zahlen $\Z$ gleich groß?

Auch diese beiden Mengen sind gleich groß. Eine bijektive Abbildung zwischen der Menge der natürlichen Zahlen $\N$ und der Menge der ganzen Zahlen $\Z$ ist die Abbildung

$\begin{array}{ccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots\\[3px] \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \cdots \\[3px] 0 & -1 & 1 & -2 & 2 & -3 & 3 & -4 & \cdots\\ \end{array}$

oder in einer Formel

$f: \N \rightarrow \Z: n \mapsto \begin{cases} \tfrac{n-1}2 & n \text{ ist ungerade} \\ -\tfrac n2 & n \text{ ist gerade} \end{cases}$

Menge der natürlichen Zahlen und Menge der rationalen Zahlen

Auch die Menge der rationalen Zahlen ist gleich mächtig mit der Menge der natürlichen Zahlen. Hier ist es jedoch nicht so einfach, selbst auf den Beweis zu kommen. Zunächst musst du die rationalen Zahlen in eine geschickte zweidimensionale Anordnung bringen:

$\begin{array}{ccccccccccccccc} \cdots & -\tfrac 13 & & -\tfrac 12 & & -\tfrac 11 & & 0 & & \tfrac 11 & & \tfrac 12 & & \tfrac 13 & \cdots \\ & & & & & & & & & & & & & & \\ \cdots & -\tfrac 23 & & -\tfrac 22 & & -\tfrac 21 & & & & \tfrac 21 & & \tfrac 22 & & \tfrac 23 & \cdots \\ & & & & & & & & & & & & & & \\ \cdots & -\tfrac 33 & & -\tfrac 32 & & -\tfrac 31 & & & & \tfrac 31 & & \tfrac 32 & & \tfrac 33 & \\ & \vdots & & \vdots & & \vdots & & & & \vdots & & \vdots & & \vdots & \\ \end{array}$

Nun kannst du bei 0 beginnend die obige Anordnung der rationalen Zahlen so abzählen, dass jeder rationalen Zahl im Schema genau eine eindeutige natürliche Zahl zugeordnet wird:

$\begin{array}{clclclccclclclc} \cdots & -\tfrac 13 & & -\tfrac 12\ _{\color{Blue} (6)} & {\color{MidnightBlue}\leftarrow} & -\tfrac 11\ _{\color{Blue} (5)} & & 0\ _{\color{Blue} (1)} & {\color{MidnightBlue}\rightarrow} & \tfrac 11\ _{\color{Blue} (2)} & & \tfrac 12\ _{\color{Blue} (13)} & {\color{MidnightBlue}\rightarrow} & \tfrac 13\ _{\color{Blue} (14)} & \cdots \\[3px] & & & {\color{MidnightBlue}\downarrow} & & {\color{MidnightBlue}\uparrow} & & & & {\color{MidnightBlue}\downarrow} & & {\color{MidnightBlue}\uparrow} & & {\color{MidnightBlue}\downarrow} & \\[3px] \cdots & -\tfrac 23 & & -\tfrac 22\ _{\color{Blue} (7)} & & -\tfrac 21\ _{\color{Blue} (4)} & {\color{MidnightBlue}\leftarrow} & {\color{MidnightBlue}-} & {\color{MidnightBlue}-} & \tfrac 21\ _{\color{Blue} (3)} & & \tfrac 22\ _{\color{Blue} (12)} & & \tfrac 23\ _{\color{Blue} (15)} & \cdots \\[3px] & & & {\color{MidnightBlue}\downarrow} & & & & & & & & {\color{MidnightBlue}\uparrow} & & {\color{MidnightBlue}\downarrow} & \\[3px] \cdots & -\tfrac 33 & & -\tfrac 32\ _{\color{Blue} (8)} & {\color{MidnightBlue}\rightarrow} & -\tfrac 31\ _{\color{Blue} (9)} & {\color{MidnightBlue}-} & {\color{MidnightBlue}-} & {\color{MidnightBlue}\rightarrow} & \tfrac 31\ _{\color{Blue} (10)} & {\color{MidnightBlue}\rightarrow} & \tfrac 32\ _{\color{Blue} (11)} & & \tfrac 33\ _{\color{Blue} \cdots} & \cdots \\[3px] & \vdots & & \vdots & & \vdots & & & & \vdots & & \vdots & & {\color{MidnightBlue}\downarrow} & \\ \end{array}$

So erhältst du folgende Abbildung der natürlichen Zahlen in die Menge der rationalen Zahlen:

$\begin{array}{ccccccccccc} {\color{Blue}1} & {\color{Blue}2} & {\color{Blue}3} & {\color{Blue}4} & {\color{Blue}5} & {\color{Blue}6} & {\color{Blue}7} & {\color{Blue}8} & {\color{Blue}9} & {\color{Blue}10} & {\color{Blue}\dotsb} \\[3px] {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} \\[3px] 0 & \tfrac 11 & \tfrac 21 & -\tfrac 21 & -\tfrac 11 & -\tfrac 12 & -\tfrac 22 & -\tfrac 32 & -\tfrac 31 & \tfrac 31 & \dotsb \\ \end{array}$

Durch diese Abbildung werden zwar alle rationalen Zahlen mindestens einmal getroffen (die Abbildung ist surjektiv), aber es gibt verschiedene natürliche Zahlen, die auf dieselbe rationale Zahl abgebildet werden (die Abbildung ist nicht injektiv). So wird der 5 und der 7 dieselbe rationale Zahl -1 zugeordnet. Um nun auch die Abbildung injektiv (und damit insgesamt bijektiv) zu machen, überspringen wir beim Abzählen diejenigen rationalen Zahlen, die nicht vollständig gekürzt sind:

$\begin{array}{clclclccclclclc} \cdots & -\tfrac 13 & & -\tfrac 12\ _{\color{Blue} (6)} & {\color{MidnightBlue}\leftarrow} & -\tfrac 11\ _{\color{Blue} (5)} & & 0\ _{\color{Blue} (1)} & {\color{MidnightBlue}\rightarrow} & \tfrac 11\ _{\color{Blue} (2)} & & \tfrac 12\ _{\color{Blue} (11)} & {\color{MidnightBlue}\rightarrow} & \tfrac 13\ _{\color{Blue} (12)} & \cdots \\[3px] & & & {\color{MidnightBlue}\downarrow} & & {\color{MidnightBlue}\uparrow} & & & & {\color{MidnightBlue}\downarrow} & & {\color{MidnightBlue}\uparrow} & & {\color{MidnightBlue}\downarrow} & \\[3px] \cdots & -\tfrac 23 & & -\tfrac 22\ _{\color{Blue} (\cdot)} & & -\tfrac 21\ _{\color{Blue} (4)} & {\color{MidnightBlue}\leftarrow} & {\color{MidnightBlue}-} & {\color{MidnightBlue}-} & \tfrac 21\ _{\color{Blue} (3)} & & \tfrac 22\ _{\color{Blue} (\cdot)} & & \tfrac 23\ _{\color{Blue} (13)} & \cdots \\[3px] & & & {\color{MidnightBlue}\downarrow} & & & & & & & & {\color{MidnightBlue}\uparrow} & & {\color{MidnightBlue}\downarrow} & \\[3px] \cdots & -\tfrac 33 & & -\tfrac 32\ _{\color{Blue} (7)} & {\color{MidnightBlue}\rightarrow} & -\tfrac 31\ _{\color{Blue} (8)} & {\color{MidnightBlue}-} & {\color{MidnightBlue}-} & {\color{MidnightBlue}\rightarrow} & \tfrac 31\ _{\color{Blue} (9)} & {\color{MidnightBlue}\rightarrow} & \tfrac 32\ _{\color{Blue} (10)} & & \tfrac 33\ _{\color{Blue} \cdots} & \cdots \\[3px] & \vdots & & \vdots & & \vdots & & & & \vdots & & \vdots & & {\color{MidnightBlue}\downarrow} & \\ \end{array}$

So erhalten wir folgende bijektive Abbildung zwischen $\N$ und $\Q$:

$\begin{array}{cccccccccccc} {\color{Blue}1} & {\color{Blue}2} & {\color{Blue}3} & {\color{Blue}4} & {\color{Blue}5} & {\color{Blue}6} & {\color{Blue}7} & {\color{Blue}8} & {\color{Blue}9} & {\color{Blue}10} & {\color{Blue}11} & {\color{Blue}\cdots} \\[3px] {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} \\[3px] 0 & \tfrac 11 & \tfrac 21 & -\tfrac 21 & -\tfrac 11 & -\tfrac 12 & -\tfrac 32 & -\tfrac 31 & \tfrac 31 & \tfrac 32 & \tfrac 12 & \cdots \\ \end{array}$

Es ist also möglich $\N$ bijektiv auf $\Q$ abzubilden. Dies beweist, dass $\N$ und $\Q$ gleich mächtig sind, also dieselbe Anzahl an Elemente besitzen. Auch dies ist eine stark kontraintuitive Feststellung, denn allein im Intervall $[0,1]$ gibt es unendlich viele rationale aber nur zwei natürliche Zahlen.

Zur Übung kannst du nun folgende Aufgabe lösen:

Frage: Welche Menge ist größer: $\N$ oder $\Q^{+}$, die Menge der positiven rationalen Zahlen?

Auch die beiden Mengen $\N$ und $\Q^{+}$ sind gleich mächtig. Um dies zu Zeigen, wählen wir folgendes Schema zur Anordnung der positiven rationalen Zahlen:

$\begin{array}{cccccccccc} \tfrac 11 & & \tfrac 12 & & \tfrac 13 & & \tfrac 14 & & \tfrac 15 & \cdots \\ & & & & & & & & & \\ \tfrac 21 & & \tfrac 22 & & \tfrac 23 & & \tfrac 24 & & \tfrac 25 & \cdots \\ & & & & & & & & & \\ \tfrac 31 & & \tfrac 32 & & \tfrac 33 & & \tfrac 34 & & \tfrac 35 & \cdots \\ & & & & & & & & & \\ \tfrac 41 & & \tfrac 42 & & \tfrac 43 & & \tfrac 44 & & \tfrac 45 & \cdots \\ & & & & & & & & & \\ \tfrac 51 & & \tfrac 52 & & \tfrac 53 & & \tfrac 54 & & \tfrac 55 & \cdots \\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \\ \end{array}$

Um eine bijektive Abbildung von $\N$ nach $\Q$ zu erhalten, zählen wir die rationalen Zahlen im Schema diagonal beginnend bei $\tfrac 11$ ab, wobei wir nicht vollständig gekürzte Brüche überspringen:

$\begin{array}{lclclclclc} \tfrac 11\ _{\color{Blue} (1)} & {\color{MidnightBlue}\rightarrow} & \tfrac 12\ _{\color{Blue} (2)} & & \tfrac 13\ _{\color{Blue} (5)} & {\color{MidnightBlue}\rightarrow} & \tfrac 14\ _{\color{Blue} (6)} & & \tfrac 15\ _{\color{Blue} (11)} & {\color{MidnightBlue}\rightarrow} \\ & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & \\ \tfrac 21\ _{\color{Blue} (3)} & & \tfrac 22\ _{\color{Blue} (\cdot)} & & \tfrac 23\ _{\color{Blue} (7)} & & \tfrac 24\ _{\color{Blue} (\cdot)} & & \tfrac 25 & \cdots \\ {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\nearrow} & & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & & & \\ \tfrac 31\ _{\color{Blue} (4)} & & \tfrac 32\ _{\color{Blue} (8)} & & \tfrac 33\ _{\color{Blue} (\cdot)} & & \tfrac 34 & & \tfrac 35 & \cdots \\ & {\color{MidnightBlue}\swarrow} & & {\color{MidnightBlue}\nearrow} & & & & & & \\ \tfrac 41\ _{\color{Blue} (9)} & & \tfrac 42\ _{\color{Blue} (\cdot)} & & \tfrac 43 & & \tfrac 44 & & \tfrac 45 & \cdots \\ {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\nearrow} & & & & & & & & \\ \tfrac 51\ _{\color{Blue} (10)} & & \tfrac 52 & & \tfrac 53 & & \tfrac 54 & & \tfrac 55 & \cdots \\ & & \vdots & & \vdots & & \vdots & & \vdots & \\ \end{array}$

So haben wir folgende bijektive Abbildung zwischen $\N$ und $\Q$ gefunden, die beweist, dass beide Mengen gleich mächtig sind:

$\begin{array}{cccccccccccccccc} {\color{Blue} 1} & {\color{Blue} 2} & {\color{Blue} 3} & {\color{Blue} 4} & {\color{Blue} 5} & {\color{Blue} 6} & {\color{Blue} 7} & {\color{Blue} 8} & {\color{Blue} 9} & {\color{Blue} 10} & {\color{Blue} 11} & {\color{Blue} \cdots} \\[3px] {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} \\[3px] 1 & \tfrac 12 & 2 & 3 & \tfrac 13 & \tfrac 14 & \tfrac 23 & \tfrac 32 & 4 & 5 & \tfrac 15 & \cdots \\ \end{array}$

Das hier vorgestellte Vefahren wird auch Cantors erstes Diagonalargument genannt.

Menge der natürlichen Zahlen und Menge der reellen Zahlen

Als letztes Beispiel vergleichen wir die Menge $\N$ der natürlichen Zahlen mit der Menge $\R$ der reellen Zahlen. Hier werden wir sehen, dass es mehr reelle als natürliche Zahlen gibt. Doch wie kann man beweisen, dass $\N$ und $\R$ nicht gleich mächtig sind?

Wir werden diesen Beweis in zwei Schritten führen: Zunächst zeigen wir, dass die Menge der reellen Zahlen $\R$ und das offene Intervall $(0,1)$ gleich mächtig sind. Danach zeigen wir, dass $\N$ und $(0,1)$ nicht gleich mächtig sein können. So haben wir gezeigt, dass auch $\N$ und $\R$ nicht gleich mächtig sein können (wäre $\N$ und $\R$ gleich mächtig, so wäre auch $\N$ und $(0,1)$ gleich mächtig, was wir aber widerlegt haben).

Frage: Wieso sind $\R$ und $(0,1)$ gleich mächtig? Wie sieht eine bijektive Abbildung zwischen $\R$ und $(0,1)$ aus?

Wir wissen, dass der Tangens eine bijektive Abbildung von $(-\tfrac\pi2 ,\, \tfrac \pi2)$ nach $\R$ ist. Diese Funktion können wir nutzen, um eine bijektive Abbildung $f: (0,1)\rightarrow \R$ zu basteln. Durch die Zuordnung $x\mapsto \pi \cdot x - \tfrac \pi2$ wird das Intervall $(0,1)$ bijektiv auf $(-\tfrac\pi2 ,\, \tfrac \pi2)$ verschoben. Wenn man nun noch den Tangens anwendet, entsteht eine bijektive Abbildung $f$:

$f: (0,1) \rightarrow \R : x \mapsto \tan\left(\pi \cdot x - \tfrac \pi2 \right)$

Alternativ können wir mit dem Arkustangens eine bijektive Abbildung $g: \R\rightarrow (0,1)$ konstruieren:

$g: \R \rightarrow (0,1): x\mapsto \frac{\arctan(x)}\pi + \frac{1}{2}$

Nun müssen wir beweisen, dass $\N$ und $(0,1)$ nicht gleich mächtig sein können. Dies werden wir durch einen Widerspruchsbeweis beweisen. Dazu nehmen wir an, dass $\N$ und $(0,1)$ gleich mächtig sind, dass es also eine bijektive Abbildung $f:\N \rightarrow (0,1)$ gibt. Diese Annahme führen wir dann zu einem Widerspruch.

Sei also $f:\N \rightarrow (0,1)$ eine beliebige bijektive Abbildung. Wir können nun die einzelnen Funktionswerte dieser Funktion in ihrer Dezimalentwicklung in einer unendlich langen Liste untereinander schreiben:

$\begin{align} f(1) & = 0,\ a_{11}\ a_{12}\ a_{13}\ a_{14} \dots \\[3px] f(2) & = 0,\ a_{21}\ a_{22}\ a_{23}\ a_{24} \dots \\[3px] f(3) & = 0,\ a_{31}\ a_{32}\ a_{33}\ a_{34} \dots \\[3px] f(4) & = 0,\ a_{41}\ a_{42}\ a_{43}\ a_{44} \dots \\[3px] & \ \,\vdots \end{align}$

Dabei steht die Variable $a_{ij}$ für die Ziffer aus der Menge $\{1,2,3,\ldots, 9, 0\}$, die bei der Dezimalentwicklung der Zahl $f(i)$ an der $j$-ten Nachkommastelle auftritt. Sollte eine Dezimalentwicklung einer reellen Zahl abbrechen, so füllen wir diese mit Nullen auf. So wird aus der Dezimalentwicklung 0,25 der Zahl $\tfrac 14$ die Dezimalentwicklung $0,2500000000\dots$.

Wäre beispielsweise $f(1)=\tfrac 12$, $f(2)=\tfrac 34$, $f(3)=\tfrac 13$ und $f(4) = \pi-3$, so würden die ersten vier Zeilen unserer Liste so aussehen:

$\begin{align} f(1) & = 0,\ 5\ 0\ 0\ 0 \dots \\[3px] f(2) & = 0,\ 7\ 5\ 0\ 0 \dots \\[3px] f(3) & = 0,\ 3\ 3\ 3\ 3 \dots \\[3px] f(4) & = 0,\ 1\ 4\ 1\ 5 \dots \\[3px] & \ \,\vdots \end{align}$

Nun konstruieren wir mit Hilfe der Liste eine neue Zahl $x = 0,x_1\, x_2\, x_3\, x_4\dots$, welche im offenen Intervall $(0,1)$ liegt und nicht in der Liste enthalten ist. Dabei gehen wir nach folgendem Algorithmus vor:

• Wir setzen $x_1 = 5$, wenn $a_{11}\ne 5$ und $x_1=4$, wenn $a_{11}= 5$ ist. Damit ist $x\ne f(1)$.
• Wir setzen $x_2 = 5$, wenn $a_{22}\ne 5$ und $x_2=4$, wenn $a_{22}= 5$ ist. Damit ist $x\ne f(2)$.
• Wir setzen $x_3 = 5$, wenn $a_{33}\ne 5$ und $x_3=4$, wenn $a_{33}= 5$ ist. Damit ist $x\ne f(3)$.
• $\dots$

Die allgemeine Regel zur Konstruktion von $x$ lautet dabei:

• Setze $x_i=5$, wenn $a_{ii}\ne 5$ ist und setze ansonsten $x_i=4$.

Diese Regel garantiert, dass $x$ sich von jedem $f(i)$ für $i\in\N$ unterscheidet, da sich $x$ in seiner Dezimalbruchentwicklung an der $i$-ten Nachkommastelle von $f(i)$ unterscheidet.

Hinweis: Es gibt eine Möglichkeit, bei der zwei unterschiedliche Dezimalbruchentwicklungen dieselbe Zahl bezeichnen. Dies kann nämlich dann und nur dann auftreten, wenn eine der beiden Dezimalbruchentwicklungen mit lauter 9er endet. So ist beispielsweise: $0,999999\ldots = 3\cdot 0,333333\ldots = 3\cdot \tfrac 13 = 1 = 1,000000\ldots$ Da wir aber die Unterscheidung in $a_{ii}=5$ und $a_{ii}\ne 5$ machen und in der Dezimalbruchentwicklung von $x$ nur 5er und 4er nach dem Komma auftreten, kann dieser Fall in unserem Beweis nicht auftreten.

In unserem obigen Beispiel würden die ersten 4 Nachkommastellen von $x$ lauten:

$\begin{align} f(1) & = 0,\ {\color{Red}5}\ 0\ 0\ 0 \dots \\[3px] f(2) & = 0,\ 7\ {\color{Blue}5}\ 0\ 0 \dots \\[3px] f(3) & = 0,\ 3\ 3\ {\color{OliveGreen}3}\ 3 \dots \\[3px] f(4) & = 0,\ 1\ 4\ 1\ {\color{RedOrange}5} \dots \\[3px] & \ \,\vdots \\ \\ x &= 0,\ {\color{Red}4}\ {\color{Blue}4}\ {\color{OliveGreen}5}\ {\color{RedOrange}4} \dots \\ \end{align}$

Außerdem ist $x$ eine reelle Zahl im Intervall $(0,1)$, da als Nachkommastellen nur 4er und 5er auftreten und da $x$ keine Vorkommastellen ungleich Null besitzt. $x$ ist auch nicht in unserer Liste enthalten, was bedeutet, dass sie nicht durch die Funktion $f$ getroffen wird. Dies bedeutet aber, dass $f$ nicht surjektiv ist, was im Widerspruch zu unserer Annahme steht, dass $f$ bijektiv sein soll ↯.

Wir haben gerade bewiesen, dass es keine bijektive Abbildung zwischen der Menge der natürlichen Zahlen und der Menge der reellen Zahlen geben kann. Dies beweist, dass beide Mengen nicht gleich mächtig sind, dass es also unterschiedliche Arten der Unendlichkeit gibt.

Der obige Beweis wurde im Übrigen von Georg Cantor 1877 entdeckt und wird nach ihm Cantors zweites Diagonalargument genannt.

Abzählbarkeit und Überabzählbarkeit

Es gibt zwei wichtige Begriffe der Mathematik, die eng mit dem Begriff der Mächtigkeit von Mengen verknüpft sind: Abzählbarkeit und Überabzählbarkeit.

Wir nennen eine Menge abzählbar unendlich, wenn sie gleich mächtig mit der Menge $\N$ ist. Dies bedeutet, dass alle Elemente diese Menge in einer unendlichen Liste aufgeschrieben werden können. Dies ist gleichwertig damit, dass man alle Elemente dieser Menge abzählen kann (ihr also eine eineindeutige Indexnummer zuordnen kann).

Eine höchstens abzählbare ist eine Menge, die entweder endlich oder abzählbar unendlich ist. Eine überabzählbare Menge ist eine Menge, die nicht höchstens abzählbar, also mächtiger als die Menge der natürlichen Zahlen ist. Eine solche Menge kann nicht in einer unendlichen Liste aufgeschrieben werden. Dafür ist sie einfach zu groß.

Hinweis: In der Literatur wird der Begriff „abzählbar“ nicht eindeutig verwendet. Manchmal bedeutet dieser Begriff „abzählbar unendlich“ und manchmal „höchstens abzählbar“. In diesem Buch wird deshalb auf den Begriff „abzählbar“ weitestgehend verzichtet.

Die Begriffe dieses Abschnitts treten in der Mathematik oft und an verschiedenen Stellen auf. Deshalb ist es wichtig, dass du lernst, mit diesen Begriffen umzugehen.

Beispiel (abzählbar unendliche und überabzählbar unendliche Mengen): Die Menge $\N$, $\Z$ und $\Q$ sind abzählbar unendlich. Die Menge $\R$ und $\C$ sind überabzählbar unendlich.

Vertiefung zum Thema Mächtigkeit

Vertiefung: Der Inhalt des folgenden Abschnitts ist eine Vertiefung des Stoffes. Für die nächsten Kapitel ist es nicht notwendig, dass du dieses Kapitel gelesen hast.

Wir haben definiert, dass zwei Mengen $A$ und $B$ genau dann gleich mächtig sind, wenn es möglich ist, zwischen ihnen eine bijektive Abbildung zu definieren. Nun ist es möglich auf einer beliebigen Menge von Mengen eine Relation zu definieren, die besagt: „zwei Mengen $x$ und $y$ stehen genau dann in Relation zueinander, wenn es eine bijektive Abbildung $f:x\rightarrow y$ gibt“ Diese Relation ist eine Äquivalenzrelation.

Frage: Wieso ist die obige Relation eine Äquivalenzrelation?

Um zu überprüfen, ob die Relation „zwei Mengen $x$ und $y$ stehen genau dann in Relation zueinander, wenn es eine bijektive Abbildung $f:x\rightarrow y$ gibt“ eine Äquivalenzrelation ist, müssen wir überprüfen, ob sie reflexiv, symmetrisch und transitiv ist.

reflexiv: Zur Überprüfung der Reflexivität müssen wir zeigen, dass jede Menge $A$ in Relation zu sich selbst steht, dass es also für jede Menge $A$ eine bijektive Abbildung $f:A\rightarrow A$ gibt. Eine solche bijektive Abbildung ist beispielsweise die Identitätsabbildung $f:A\rightarrow A: x\mapsto x$.

symmetrisch: Sei $A$ und $B$ zwei Mengen, so dass $A$ mit $B$ in Relation steht. Somit gibt es eine bijektive Abbildung $f:A\rightarrow B$. Wir müssen nun zeigen, dass dann auch $B$ mit $A$ in Relation steht, dass es also eine bijektive Abbildung $g:B \rightarrow A$ gibt. Eine solche bijektive Abbildung ist die Umkehrabbildung von $f$, also $g=f^{-1}: B\rightarrow A$.

transitiv: Seien $A$, $B$ und $C$ Mengen, so dass $A$ mit $B$ und $B$ mit $C$ in Relation steht. Es gibt also bijektive Abbildungen $f:A\rightarrow B$ und $g:B\rightarrow C$. Wir müssen nun zeigen, dass unter diesen Voraussetzungen auch $A$ mit $C$ in Relation zueinander stehen, dass es also eine bijektive Abbildung $h:A\rightarrow C$ gibt. Eine solche Abbildung ist die Komposition der beiden Funktionen $f$ mit $g$, also $h=g\circ f: A\rightarrow C$. Diese Funktionskomposition ist bijektiv, weil die Komposition zweier bijektiver Abbildungen bijektiv ist.

Da die obige Relation eine Äquivalenzrelation ist, zerfällt jede Menge von Mengen unter dieser Relation in Äquivalenzklassen. Man kann also jede Menge von Mengen so in disjunkte, nicht-leere Teilmengen zerlegen, dass alle Mengen der gleichen Mächtigkeit in einer diese Teilmengen zusammengefasst sind.

Diese Teilmengen werden in der Mathematik durch Kardinalzahlen beschrieben. Kardinalzahlen sind verallgemeinerte natürliche Zahlen, die die Mächtigkeit einer Menge beschreiben. Im Fall einer endlichen Menge ist ihre Kardinalzahl nichts anderes als die Anzahl ihrer Elemente. Im unendlichen sieht es anders aus: Allen abzählbar unendlichen Mengen, also Mengen mit Mächtigkeit gleich der Mächtigkeit der natürlichen Zahlen, wird die Kardinalzahl $\aleph_0$ zugeordnet (Der Buchstabe Aleph $\aleph$ ist der erste Buchstabe des hebräischen Alphabets). Allgemein werden unendlichen Mengen Kardinalzahlen der Form $\aleph_i$ zugeordnet.

Die Schreibweise für die Kardinalzahl einer Menge $A$ ist $|A|$ (nicht verwechseln mit den Betragsstrichen oder der Determinantenfunktion aus der Linearen Algebra!). So ist $\left|\{3,4\}\right|=2$, $\left|\{\}\right|=0$ und $|\N|=\aleph_0$.

Durch folgende Definition kann man auch entscheiden, wann eine Menge mächtiger ist als eine andere ist:

Definition (Vergleich der Mächtigkeit): Eine Menge $A$ heißt höchstens gleichmächtig zu einer Menge $B$, wenn es möglich ist eine Bijektion zwischen $A$ und einer beliebigen Teilmenge von $B$ zu definieren. Die Schreibweise für „$A$ ist höchstens gleichmächtig zu $B$“ ist $|A|\le |B|$.

Die Relation $A~B\Leftrightarrow |A|\le|B|$ definiert eine totale Ordnungsrelation auf jeder Menge von Mengen. Man kann demnach jede Menge von Mengen nach ihrer Mächtigkeit sortieren.

$\aleph_0$ ist die kleinste Mächtigkeit, die eine unendliche Menge haben kann (Man kann zeigen, dass jede unendliche Menge eine Mächtigkeit größer gleich $\N$ besitzt). Außerdem hat Cantor im Satz von Cantor gezeigt, dass jede Potenzmenge $P(A)$ mächtiger ist ihre zugrunde liegende Menge $A$ ist. Da im Fall, dass $A$ eine endliche Menge mit $n$ Elementen ist, die Potenzmenge $\mathcal P(A)$ genau $2^n$ Elemente besitzt (Beweis siehe Abschnitt „Folgerung des binomischen Lehrsatz“), schreibt man für die Mächtigkeit der Potenzmenge $|\mathcal P(A)|=2^{|A|}$.

Man kann zeigen, dass $|\mathcal P(\N)|=2^{|\N|}=|\R|$ ist. Es stellt sich nun die Frage, ob es eine Menge gibt, die mächtiger als $\N$, aber weniger mächtig als $\R$ ist. Cantor vermutete, dass dies nicht der Fall ist, konnte seine Vermutung aber nicht beweisen. Diese Vermutung wird Kontinuumshypothese genannt. Es stellte sich jedoch heraus, dass diese Hypothese in der Mengenlehre (so wie sie bis heute erklärt ist) unbeweisbar ist.