Mächtigkeit von Mengen – Serlo „Mathe für Nicht-Freaks“

Warnung

Das folgende Kapitel enthält stark kontraintuitive Aussagen. Beim Lesen kann es zu Erstaunen und Verblüffung kommen. Ihr Geist 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, beantworte bitte für dich folgende Fragen (du kannst auch „aus dem Bauch heraus“ antworten):

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

• Menge der natürlichen Zahlen $\mathbb {N}$ oder die Menge der Quadratzahlen $Q=\{n^{2}\,|\,n\in \mathbb {N} \}$
• Menge der natürlichen Zahlen $\mathbb {N}$ oder die Menge der ganzen Zahlen $\mathbb {Z}$
• Menge der natürlichen Zahlen $\mathbb {N}$ oder die Menge der rationalen Zahlen $\mathbb {Q}$
• Menge der natürlichen Zahlen $\mathbb {N}$ oder die Menge der reellen Zahlen $\mathbb {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 du 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 so nebeneinander packen, dass jeweils ein Stein der einen Kiste neben einem Stein der anderen Kiste liegt. Ist eine Kiste leer und bleiben in der anderen Kiste Steine übrig, so besitzt die zweite Kiste mehr Steine als die erste. Werden beide Kisten gleichzeitig leer, 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 Abbildung zwischen 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.

Bei der Übertragung auf unendliche Mengen müssen wir aber vorsichtig sein. Es tritt nämlich etwas auf, was bei endlichen Mengen nicht auftritt. Bei endlichen Mengen ist es egal, wie wir die Elemente der Mengen paarweise zuordnen. Bei unendlichen Mengen ist es nicht egal, wie die folgenden Beispiele zeigen:

Beispiel

Wir betrachten die Menge der natürlichen Zahlen $\mathbb {N} _{0}$ mit Null und $\mathbb {N} ^{+}$ ohne Null.

1. Die Funktion $f:\mathbb {N} _{0}\longmapsto \mathbb {N} _{0}:f(x)=x+1$ ist injektiv, aber nicht surjektiv.
2. Die Funktion $g:\mathbb {N} ^{+}\longmapsto \mathbb {N} _{0}:g(x)=x-1$ ist bijektiv.

Im Beispiel 1 ist die Zahl $0$ kein Bild der Funktion $f$. Bei dieser Zuordnung bleibt die Zahl $0$ übrig. Im Beispiel 2 gilt $\mathbb {N} ^{+}\varsubsetneq \mathbb {N} _{0}$, aber $g$ ist bijektiv und bei dieser Zuordnung bleiben keine Elemente übrig. Also ist eine echte Teilmenge zur gesamten Menge "gleich groß". Wir können daher nicht verlangen, dass alle injektiven Funktionen zwei gleichgroße unendliche Mengen bijektiv aufeinander abbilden. Es muss genügen, wenn wir eine bijektive Abbildung finden, damit zwei unendliche Mengen gleich groß sind.

Hinweis

Unendliche Mengen können injektiv in eine echte Teilmenge abgebildet werden.

Wir haben also 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öchten wir 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 gleichmächtig“ sagen.

Definition (Gleichmächtigkeit von Mengen)

Zwei Mengen $A$ und $B$ sind dann und nur dann gleichmächtig, wenn es zwischen ihnen eine bijektive Abbildung $f:A\longmapsto B$ gibt:

$A\sim B:\iff {\text{ es gibt eine bijektive Abbildung }}f:A\longmapsto B$

Sind zwei Mengen nicht gleichmächtig, dann bleiben beim Vergleich bei einer der beiden Mengen Elemente übrig. Wir erhalten dann keine bijektive Abbildung, sondern nur eine injektive. Ist $f:A\longmapsto B$ Injektiv, haben wir aber allen Elementen aus $A$ ein Element aus $B$ zugeordnet, so ist $A$ auf jeden Fall nicht mächtiger als $B$. Wir definieren daher:

Definition (Mächtigkeit von Mengen)

Eine Mengen $B$ ist mächtiger als eine Menge $A$, wenn es eine injektive Abbildung $f:A\longmapsto B$ gibt. $A$ wird dann schmächtiger als $B$ genannt:

$A\precsim B:\iff {\text{ es gibt eine injektive Abbildung }}f:A\longmapsto B$

Beachte, dass diese Definition den Fall der Gleichmächtigkeit einschließt! Den Zusammenhang zwischen den beiden Definitionen liefert der Äquivalenzsatz von Cantor-Bernstein-Schröder:

Satz (Äquivalenzsatz von Cantor-Bernstein-Schröder)

Ist $A$ schmächtiger als $B$ und $B$ schmächtiger als $A$, dann sind $A$ und $B$ gleichmächtig:

$A\precsim B\land B\precsim A\Longrightarrow A\sim B$

Dieser Satz liefert ein weiteres Kriterium dafür, wie die Gleichmächtigkeit zweier Mengen bewiesen werden kann. Indem nämlich zwei Funktionen angegeben werden: $f:A\longmapsto B{\text{ injektiv}}$ und $g:B\longmapsto A{\text{ injektiv}}$. Den Beweis des Äquivalenzsatzes führen wir hier.

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 $\mathbb {N}$ oder die Menge der Quadratzahlen $Q=\{n^{2}\,|\,n\in \mathbb {N} \}$? Ist es möglich, eine Bijektion zwischen $\mathbb {N}$ und $Q$ zu finden?

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

${\begin{array}{ccccccccc}1&2&3&4&5&6&7&8&\cdots \\[0.3em]\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\cdots \\[0.3em]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 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 den meisten endlichen Teilmengen 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: Sind die Menge der natürlichen Zahlen $\mathbb {N}$ und die Menge der ganzen Zahlen $\mathbb {Z}$ gleich groß?

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

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

oder in einer Formel

$f:\mathbb {N} \rightarrow \mathbb {Z} :n\mapsto {\begin{cases}{\tfrac {n-1}{2}}&n{\text{ ist ungerade}}\\-{\tfrac {n}{2}}&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 {1}{3}}&&-{\tfrac {1}{2}}&&-{\tfrac {1}{1}}&&0&&{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&\cdots \\&&&&&&&&&&&&&&\\\cdots &-{\tfrac {2}{3}}&&-{\tfrac {2}{2}}&&-{\tfrac {2}{1}}&&&&{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&{\tfrac {2}{3}}&\cdots \\&&&&&&&&&&&&&&\\\cdots &-{\tfrac {3}{3}}&&-{\tfrac {3}{2}}&&-{\tfrac {3}{1}}&&&&{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&\\&\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 {1}{3}}&&-{\tfrac {1}{2}}\ _{\color {Blue}(6)}&{\color {MidnightBlue}\leftarrow }&-{\tfrac {1}{1}}\ _{\color {Blue}(5)}&&0\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{1}}\ _{\color {Blue}(2)}&&{\tfrac {1}{2}}\ _{\color {Blue}(13)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{3}}\ _{\color {Blue}(14)}&\cdots \\[0.3em]&&&{\color {MidnightBlue}\downarrow }&&{\color {MidnightBlue}\uparrow }&&&&{\color {MidnightBlue}\downarrow }&&{\color {MidnightBlue}\uparrow }&&{\color {MidnightBlue}\downarrow }&\\[0.3em]\cdots &-{\tfrac {2}{3}}&&-{\tfrac {2}{2}}\ _{\color {Blue}(7)}&&-{\tfrac {2}{1}}\ _{\color {Blue}(4)}&{\color {MidnightBlue}\leftarrow }&{\color {MidnightBlue}-}&{\color {MidnightBlue}-}&{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(12)}&&{\tfrac {2}{3}}\ _{\color {Blue}(15)}&\cdots \\[0.3em]&&&{\color {MidnightBlue}\downarrow }&&&&&&&&{\color {MidnightBlue}\uparrow }&&{\color {MidnightBlue}\downarrow }&\\[0.3em]\cdots &-{\tfrac {3}{3}}&&-{\tfrac {3}{2}}\ _{\color {Blue}(8)}&{\color {MidnightBlue}\rightarrow }&-{\tfrac {3}{1}}\ _{\color {Blue}(9)}&{\color {MidnightBlue}-}&{\color {MidnightBlue}-}&{\color {MidnightBlue}\rightarrow }&{\tfrac {3}{1}}\ _{\color {Blue}(10)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {3}{2}}\ _{\color {Blue}(11)}&&{\tfrac {3}{3}}\ _{\color {Blue}\cdots }&\cdots \\[0.3em]&\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 }\\[0.3em]{\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 }\\[0.3em]0&{\tfrac {1}{1}}&{\tfrac {2}{1}}&-{\tfrac {2}{1}}&-{\tfrac {1}{1}}&-{\tfrac {1}{2}}&-{\tfrac {2}{2}}&-{\tfrac {3}{2}}&-{\tfrac {3}{1}}&{\tfrac {3}{1}}&\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 {1}{3}}&&-{\tfrac {1}{2}}\ _{\color {Blue}(6)}&{\color {MidnightBlue}\leftarrow }&-{\tfrac {1}{1}}\ _{\color {Blue}(5)}&&0\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{1}}\ _{\color {Blue}(2)}&&{\tfrac {1}{2}}\ _{\color {Blue}(11)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{3}}\ _{\color {Blue}(12)}&\cdots \\[0.3em]&&&{\color {MidnightBlue}\downarrow }&&{\color {MidnightBlue}\uparrow }&&&&{\color {MidnightBlue}\downarrow }&&{\color {MidnightBlue}\uparrow }&&{\color {MidnightBlue}\downarrow }&\\[0.3em]\cdots &-{\tfrac {2}{3}}&&-{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&-{\tfrac {2}{1}}\ _{\color {Blue}(4)}&{\color {MidnightBlue}\leftarrow }&{\color {MidnightBlue}-}&{\color {MidnightBlue}-}&{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(13)}&\cdots \\[0.3em]&&&{\color {MidnightBlue}\downarrow }&&&&&&&&{\color {MidnightBlue}\uparrow }&&{\color {MidnightBlue}\downarrow }&\\[0.3em]\cdots &-{\tfrac {3}{3}}&&-{\tfrac {3}{2}}\ _{\color {Blue}(7)}&{\color {MidnightBlue}\rightarrow }&-{\tfrac {3}{1}}\ _{\color {Blue}(8)}&{\color {MidnightBlue}-}&{\color {MidnightBlue}-}&{\color {MidnightBlue}\rightarrow }&{\tfrac {3}{1}}\ _{\color {Blue}(9)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {3}{2}}\ _{\color {Blue}(10)}&&{\tfrac {3}{3}}\ _{\color {Blue}\cdots }&\cdots \\[0.3em]&\vdots &&\vdots &&\vdots &&&&\vdots &&\vdots &&{\color {MidnightBlue}\downarrow }&\\\end{array}}$

So erhalten wir folgende bijektive Abbildung zwischen $\mathbb {N}$ und $\mathbb {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 }\\[0.3em]{\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 }\\[0.3em]0&{\tfrac {1}{1}}&{\tfrac {2}{1}}&-{\tfrac {2}{1}}&-{\tfrac {1}{1}}&-{\tfrac {1}{2}}&-{\tfrac {3}{2}}&-{\tfrac {3}{1}}&{\tfrac {3}{1}}&{\tfrac {3}{2}}&{\tfrac {1}{2}}&\cdots \\\end{array}}$

Es ist also möglich, $\mathbb {N}$ bijektiv auf $\mathbb {Q}$ abzubilden. Dies beweist, dass $\mathbb {N}$ und $\mathbb {Q}$ gleich mächtig sind, also dieselbe Anzahl an Elementen 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: $\mathbb {N}$ oder $\mathbb {Q} ^{+}$, die Menge der positiven rationalen Zahlen?

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

${\begin{array}{cccccccccc}{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}$

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

${\begin{array}{lclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&\\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}\ _{\color {Blue}(\cdot )}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\{\tfrac {5}{1}}\ _{\color {Blue}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\&&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}$

So haben wir folgende bijektive Abbildung zwischen $\mathbb {N}$ und $\mathbb {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 }\\[0.3em]{\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 }\\[0.3em]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\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 $\mathbb {N}$ der natürlichen Zahlen mit der Menge $\mathbb {R}$ der reellen Zahlen. Hier werden wir sehen, dass es mehr reelle als natürliche Zahlen gibt. Doch wie kann man beweisen, dass $\mathbb {N}$ und $\mathbb {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 $\mathbb {R}$ und das offene Intervall $(0,1)$ gleich mächtig sind. Danach zeigen wir, dass $\mathbb {N}$ und $(0,1)$ nicht gleich mächtig sind. So haben wir gezeigt, dass auch $\mathbb {N}$ und $\mathbb {R}$ nicht gleich mächtig sind (wären $\mathbb {N}$ und $\mathbb {R}$ gleich mächtig, so wären auch $\mathbb {N}$ und $(0,1)$ gleich mächtig, was wir aber widerlegt haben).

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

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

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

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

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

Nun müssen wir beweisen, dass $\mathbb {N}$ und $(0,1)$ nicht gleich mächtig sein können, dass es also keine bijektive Abbildung $f:\mathbb {N} \rightarrow (0,1)$ gibt.

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

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

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 {1}{4}}$ die Dezimalentwicklung $0,2500000000\dots$

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

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

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}\neq 5$ und $x_{1}=4$, wenn $a_{11}=5$ ist. Damit ist $x\neq f(1)$.
• Wir setzen $x_{2}=5$, wenn $a_{22}\neq 5$ und $x_{2}=4$, wenn $a_{22}=5$ ist. Damit ist $x\neq f(2)$.
• Wir setzen $x_{3}=5$, wenn $a_{33}\neq 5$ und $x_{3}=4$, wenn $a_{33}=5$ ist. Damit ist $x\neq f(3)$.
• $\dots$

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

• Setze $x_{i}=5$, wenn $a_{ii}\neq 5$ ist und setze ansonsten $x_{i}=4$.

Diese Regel garantiert, dass $x$ sich von jedem $f(i)$ für $i\in \mathbb {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 9ern endet. So ist beispielsweise:

$0,999999\ldots =3\cdot 0,333333\ldots =3\cdot {\tfrac {1}{3}}=1=1,000000\ldots$

Da wir aber die Unterscheidung in $a_{ii}=5$ und $a_{ii}\neq 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{aligned}f(1)&=0,\ {\color {Red}5}\ 0\ 0\ 0\dots \\[0.3em]f(2)&=0,\ 7\ {\color {Blue}5}\ 0\ 0\dots \\[0.3em]f(3)&=0,\ 3\ 3\ {\color {OliveGreen}3}\ 3\dots \\[0.3em]f(4)&=0,\ 1\ 4\ 1\ {\color {RedOrange}5}\dots \\[0.3em]&\ \,\vdots \\\\x&=0,\ {\color {Red}4}\ {\color {Blue}4}\ {\color {OliveGreen}5}\ {\color {RedOrange}4}\dots \\\end{aligned}}$

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 es nicht durch die Funktion $f$ getroffen wird. Dies bedeutet aber, dass $f$ nicht surjektiv ist. Also ist $f$ sicher nicht bijektiv.

Da dieser Beweis für jede Abbildung $f$ funktioniert, gibt es keine bijektive Abbildung zwischen der Menge der natürlichen Zahlen und der Menge der reellen Zahlen. Dies beweist, dass beide Mengen nicht gleich mächtig sind, dass es also unterschiedliche Arten der Unendlichkeit gibt. Es gibt natürlich eine injektive Abbildung von $\mathbb {N}$ in $\mathbb {R}$, nämlich die Identität: $id:\mathbb {N} \longmapsto \mathbb {R} :id(x)=x$. Also ist $\mathbb {R}$ echt mächtiger als $\mathbb {N}$.

Der obige Beweis wurde von Georg Cantor 1877 entdeckt und wird Cantors zweites Diagonalargument genannt.

Abzählbarkeit und Überabzählbarkeit

Wir haben in den Beispielen zwei verschiedene Größen von unendlichen Mengen kennengelernt: die Abzählbarkeit und die Überabzählbarkeit. Eine Menge ist abzählbar unendlich, wenn sie gleichmächtig mit der Menge $\mathbb {N}$ ist. Dies bedeutet, dass alle Elemente dieser 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 Menge ist entweder endlich oder abzählbar unendlich. 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“.

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 Mengen $\mathbb {N}$, $\mathbb {Z}$ und $\mathbb {Q}$ sind abzählbar unendlich.
• Die Mengen $\mathbb {R}$ und $\mathbb {C}$ sind überabzählbar unendlich.

Äquivalenzsatz von Cantor-Bernstein-Schröder

Satz (Äquivalenzsatz von Cantor-Bernstein-Schröder)

Ist $A$ schmächtiger als $B$ und $B$ schmächtiger als $A$, dann sind $A$ und $B$ gleichmächtig:

$A\precsim B\land B\precsim A\Longrightarrow A\sim B$

Wir beweisen den Satz in mehreren Schritten und zeigen zunächst die Äquivalenz mit dem Zwischenmengensatz.

Satz (Zwischenmengensatz)

Liegt eine Menge $B$ zwischen einer Menge $A$ und einem injektiven Bild von $A$, so sind $A$ und $B$ gleichmächtig.

$f:A\longmapsto A{\text{ injektiv }}\land A\supseteq B\supseteq f(A)\Longrightarrow A\sim B$

Wir zeigen zunächst, dass der Äquivalenzsatz und der Zwischenmengensatz äquivalent sind:

Satz

${\text{Äquivalenzsatz von Cantor-Bernstein-Schröder }}\iff {\text{ Zwischenmengensatz}}$

Beweis

"$\Rightarrow$": Es gelte der Äquivalenzsatz von Cantor-Bernstein-Schröder. Weiterhin sei $f:A\longmapsto A{\text{ injektiv }}$ und es gelte $A\supseteq B\supseteq f[A]$. Setze $g:=f\upharpoonright B$, dann bildet $g$ injektiv in $A$ ab. Mit $B\supseteq f[A]$ bildet $f$ auch injektiv in $B$ ab. Mit dem Satz von Cantor-Bernstein-Schröder folgt $A\sim B$.

"$\Leftarrow$": Gelte nun der Zwischenmengensatz, sowie $f:A\longmapsto B$ injektiv und $g:B\longmapsto A$ Injektiv. Dann ist auch die Verkettung injektiv $(g\circ f):A\longmapsto A$ und es gilt: $A\supseteq g(B)\supseteq (g\circ f)(A)$. Mit dem Zwischenmengensatz folgt $A\sim B$. ✔

Für den Beweis des Zwischenmengensatzes definieren wir noch eine spezielle Halbordnung:

Definition (Spezielle Halbordnung)

Es sei $f:A\longmapsto A$ eine Funktion von $A$ in $A$. Dann ist ${\mathsf {Fix}}(f):=\{x\in A\,|\,f(x)=x\}$ die Menge der Fixpunkte von $f$. Für zwei beliebige Funktionen $f:A\longmapsto A$ und $g:A\longmapsto A$ ist die Relation $\sqsubseteq$ wie folgt definiert:

$g\sqsubseteq f:\iff {\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(f)\land \forall x:(x\neq g(x)\Rightarrow g(x)=f(x))$

$g\sqsubseteq f$ besagt, dass $g$ mehr Fixpunkte als $f$ hat, aber ansonsten mit $f$ übereinstimmt.

Aufgabe: Zeige, dass $\sqsubseteq$ eine Halbordnung ist.

Zu zeigen ist, $\sqsubseteq$ ist reflexiv, transitiv und antisymmetrisch.

reflexiv: Es gilt ${\mathsf {Fix}}(g)={\mathsf {Fix}}(g)$ und $g(x)=g(x)$, also auch $g\sqsubseteq g$.

transitiv: Gelte $g\sqsubseteq f$ und $f\sqsubseteq h$. Dann folgt ${\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(f)$ und ${\mathsf {Fix}}(f)\supseteq {\mathsf {Fix}}(h)$. Daraus ergibt sich ${\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(h)$. Für $x\neq g(x)$ ist $x$ kein Fixpunkt von $f$ und auch kein Fixpunkt von $h$. Also folgt $g(x)=f(x)=h(x)$ und somit $g\sqsubseteq h$.

antisymmetrisch: Gelte $g\sqsubseteq f$ und $f\sqsubseteq g$. Dann gilt ${\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(f)$ und ${\mathsf {Fix}}(f)\supseteq {\mathsf {Fix}}(g)$ also ${\mathsf {Fix}}(g)={\mathsf {Fix}}(f)$. Daher stimmen beide Funktionen überein $g(x)=f(x)$ und es gilt: $g=f$.

Die Beweisidee ist folgende: wir betrachten alle injektiven Funktionen $h:A\longmapsto B$, die zwar mehr Fixpunkte haben als die gegebene Funktion $f:A\longmapsto B$, aber ausserhalb dieser Fixpunkte mit $f$ übereinstimmen. Je mehr Fixpunkte diese Funktionen haben, desto weniger Funktionswerte stimmen mit $f$ überein. Unter diesen Funktionen gibt es (hoffentlich) welche, deren Bildbereich weitere Elemente von $B$ umfasst. Diese müssen Fixpunkte sein, denn ansonsten sind keine Abweichungen von $f$ erlaubt. Wenn es unter den betrachteten Funktionen eine gibt, in deren Bildbereich alle Elemente von $B$ liegen, haben wir eine Bijektion $A\longmapsto B$ gefunden.

Beweis (Zwischenmengensatz, Äquivalenzsatz)

Sei nun $f:A\longmapsto A{\text{ injektiv}}$ und gelte $A\supseteq B\supseteq f(A)$. Sei weiterhin:

$J:=\{h\,|\,h:A\longmapsto B{\text{ injektiv}}\land h\sqsubseteq f\}$

$J$ ist die Menge aller injektiven Funktionen $A\longmapsto B$, die mehr Fixpunkte als $f$ haben. Es gilt $f\in J$, denn $f$ ist nach Voraussetzung Injektiv, $f(A)\subseteq B$ und es gilt $f\sqsubseteq f$. Wir definieren:

$F:=\bigcup _{h\in J}{\mathsf {Fix}}(h)$

$F$ ist die Fixpunktmenge aller Funktionen aus $J$. Es gilt $F\subseteq B$, denn wenn $x\in F$ gibt es ein $h\in J$ dessen Fixpunkt $x$ ist und da $h:A\longmapsto B$ gilt $x=f(x)\in B$. Wir definieren schliesslich die gesuchte Bijektion:

$\color {red}g(x)={\begin{cases}x,&{\text{wenn }}x\in F\\f(x),&{\text{sonst}}\end{cases}}$

$g:A\longmapsto B{\text{ injektiv}}$, da $f$ injektiv ist, und es gilt nach Definition von $g$:

($\star$)   $\forall h\in J:g\sqsubseteq h$

Da ja $f\in J$, wie oben gezeigt, gilt $g\sqsubseteq f$. Wir zeigen nun: $g{\text{ ist injektiv}}$. Seien $x,y\in A$ und gelte $x\neq y$. Sind $x,y\in F$, dann folgt $g(x)=x\neq y=g(y)$. Sind $x,y\in A\setminus F$ folgt $g(x)=f(x)\neq f(y)=g(y)$ aus der Injektivität von $f$. Bleibt als letzter Fall $x\in F$ und $y\in A\setminus F$. Dann gibt es $h\in J$ mit $x\in {\mathsf {Fix}}(h)$ und es folgt: $g(x)=x=h(x)\neq h(y)=f(y)=g(y)$ mit der Injektivität von $h$. Insgesamt haben wir gezeigt:

$g\in J$

Als letzten Schritt beweisen wir, dass $g$ surjektiv auf $B$ ist und zeigen dazu $B\subseteq g(A)$. Wir definieren die Funktion $j:A\longmapsto B$ wie folgt:

$j(x)={\begin{cases}x,&{\text{ wenn }}x\in B\setminus g(A)\\g(x),&{\text{ sonst}}\end{cases}}$

$j$ ist injektiv wegen der Injektivität von $g$. Weiterhin gilt $j\sqsubseteq g$, denn $j$ hat allenfalls mehr Fixpunkte als $g$ und für $x\neq j(x)$ gilt $j(x)=g(x)$. Mit $g\sqsubseteq f$ folgt daraus $j\sqsubseteq f$ wegen wegen der Transitivität von $\sqsubseteq$. Insgesamt haben wir gezeigt: $j\in J$. Daraus folgt mit ($\star$) $g\sqsubseteq j$ und mit der Antisymmetrie von $\sqsubseteq$ ergibt sich $j=g$. Nach Definition von $j$ gilt $B\setminus g(A)\subseteq j(A)$ und mit der Gleichheit $j=g$ folgt $B\setminus g(A)\subseteq g(A)$. Das ist aber nur möglich, wenn $B\setminus g(A)=\varnothing$ gilt, also: $B\subseteq g(A)$. Also:

$\color {red}g:A\longmapsto B{\text{ bijektiv}}$, also: $A\sim B$

Damit ist der Beweis des Zwischenmengensatzes und des Äquivalenzsatzes von Cantor-Bernstein-Schröder beendet. ✔

Beispiel

Wir verwenden die Bezeichnungen wie im Beweis des Zwischenmengensatzes.

Beispiel (Zwischenmengensatz)

Es sei $A:=\mathbb {N} _{0}$ die Menge der natürlichen Zahlen, $B:=\mathbb {N} ^{+}=\{x\in \mathbb {N} \,|\,x\geq 1\}$ die Menge der natürlichen Zahlen größer oder gleich $1$ und $f:A\longmapsto B:f(x)=x+2$ die Funktion, die jede Zahl um 2 erhöht. $f$ ist injektiv und es gilt:

$A\supseteq B\supseteq f(A)$

$B$ ist eine echte Obermenge von $f(A))$, denn die $1$ ist kein Bild unter $f$. Wir definieren $g$ folgendermassen:

$g(x)={\begin{cases}x,&{\text{ wenn }}x{\text{ ungerade}}\\x+2,&{\text{ sonst}}\end{cases}}$

$g:A\longmapsto B$ ist injektiv und alle ungeraden Zahlen sind Fixpunkte. Auf den geraden Zahlen stimmt $g$ mit $f$ überein. Da $f$ keine Fixpunkte hat, gilt also $g\sqsubseteq f$. somit gilt $g\in J$. Da $g(1)=1$ ist, ist $g$ eine Bijektion auf $B$.

Mehr Fixpunkte als $g$ kann aber keine Funktion aus $J$ haben, denn die geraden Zahlen können keine Fixpunkte sein. Das folgt durch Induktion: $0$ ist kein Fixpunkt, denn $0\notin B$, tritt also nicht als Bild auf. Sei nun $n$ gerade und nach Induktionsvoraussetzung kein Fixpunkt. Dann ist das Bild von $n$ aber $f(n)=n+2$. Also kann $n+2$ auch kein Fixpunkt sein. Daher ist $g$ in diesem Beispiel tatsächlich die Funktion, deren Existenz im Beweis gezeigt wird.

Vertiefung zum Thema Mächtigkeit

Wir haben definiert, dass zwei Mengen $A$ und $B$ genau dann gleichmächtig sind, wenn es zwischen ihnen eine bijektive Abbildung gibt: $A\sim B$. Die Relation $\sim$ ist eine Äquivalenzrelation auf der Klasse aller Mengen.

Hinweis

Die Klasse aller Mengen ist zu groß für eine Menge, sie ist eine echte Klasse, vgl. "Axiomatische Mengenlehre".

Aufgabe: Zeige dass $\sim$ eine Äquivalenzrelation ist.

Um zu zeigen, dass eine Relation eine Äquivalenzrelation ist, müssen wir zeigen, dass sie reflexiv, symmetrisch und transitiv ist. Im folgenden seien $A,B,C$ beliebige Mengen.

Reflexiv: Die Identitätsabbildung $f:A\longmapsto A:f(x)=x$ ist eine Bijektion der Menge $A$ auf sich. Also gilt $A\sim A$.

Symmetrisch: Gelte $A\sim B$. Dann gibt es eine bijektive Abbildung $f:A\longmapsto B$. Daher ist die Umkehrfunktion $f^{-1}$ ebenfalls bijektiv und bildet die Menge $B$ auf die Menge $A$ ab: $f^{-1}:B\longmapsto A$. Also gilt $B\sim A$.

Transitiv: Gelte $A\sim B$ und $B\sim C$. Dann gibt es bijektive Abbildungen $f:A\longmapsto B$ und $g:B\longmapsto C$. Die Komposition dieser beiden Abbildungen $g\circ f$ ist als Komposition zweier bijektiven Abbildungen ebenfalls bijektiv und bildet $A$ auf $C$ ab: $g\circ f:A\longmapsto C$. Also gilt $A\sim C$. ✔

Da die Relation $\sim$ eine Äquivalenzrelation ist, zerfällt die Klasse aller Mengen unter dieser Relation in Äquivalenzklassen gleichmächtiger Mengen. Da diese Äquivalenzklassen ebenfalls echte Klassen sind, geht man zu einem Repräsentantensystem über, den sogenannten Kardinalzahlen:

Definition (Kardinalzahlen)

Die Kardinalzahlen sind Mengen und bilden ein Repräsentantensystem für die Äquivalenzklassen gleichmächtiger Mengen.

$|A|$ bezeichnet die Kardinalzahl, die zu der Äquivalenzklasse von $A$ gehört.

Anmerkung: Die Schreibweise $|A|$ sollte nicht mit den mit den Betragsstrichen oder der Determinantenfunktion aus der Linearen Algebra verwechselt werden.

Definition (Ordnung der Kardinalzahlen)

Die folgende Definition ist repräsentantenunabhängig:

$|A|\leq |B|:\iff A\precsim B$

Es ist leicht zu zeigen, dass die Relation $\leq$ reflexiv und transitiv ist. Die Antisymmetrie folgt mit dem Äquivalenzsatz von Cantor-Bernstein-Schröder. $\leq$ ist also eine Halbordnung. Mit dem Auswahlaxiom kann man zeigen, dass $\leq$ eine Totalordnung ist:

Satz

$\leq$ ist eine Totalordnung auf den Kardinalzahlen.

Kardinalzahlen lassen sich also der Größe nach vergleichen. Sie 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. Die endlichen Kardinalzahlen sind also die natürlichen Zahlen $0,1,2,3,\dots$. Beispielsweise ist $|\varnothing |=0$ und $|\{2,3\}|=2$.

$|\mathbb {N} |$ ist die kleinste Mächtigkeit, die eine unendliche Menge haben kann: man kann zeigen, dass jede unendliche Menge eine Mächtigkeit größer oder gleich $|\mathbb {N} |$ besitzt. Außerdem hat Cantor im Satz von Cantor gezeigt, dass jede Potenzmenge ${\mathcal {P}}(A)$ mächtiger als ihre zugrunde liegende Menge $A$ ist. Man kann zeigen, dass $|{\mathcal {P}}(\mathbb {N} )|=|\mathbb {R} |$ ist. Es gibt also unendlich viele unendliche Kardinalzahlen!

Die unendlichen Kardinalzahlen werden mit $\aleph _{0},\aleph _{1},\aleph _{2},\dots$ bezeichnet (der Buchstabe Aleph $\aleph$ ist der erste Buchstabe des hebräischen Alphabets). Es ist $\aleph _{0}=|\mathbb {N} |$. Es stellt sich nun die Frage, ob $\aleph _{1}=|\mathbb {R} |$ ist. Oder – anders formuliert – ob es eine Menge gibt, die mächtiger als $\mathbb {N}$, aber weniger mächtig als $\mathbb {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 mit den Axiomen von Zermelo-Fraenkel einschliesslich Auswahlaxiom weder beweisbar noch widerlegbar ist.

Generell kann man sich fragen, ob zwischen der Kardinalzahl einer unendlichen Menge $|X|$ und der ihrer Potenzmenge $|{\mathcal {P}}(X)|$ noch weitere Kardinlzahlen liegen. Falls nicht, wäre $\aleph _{0},\aleph _{1},\aleph _{2},\dots$ gerade $|\mathbb {N} |,|{\mathcal {P}}(\mathbb {N} )|,|{\mathcal {P}}({\mathcal {P}}(\mathbb {N} ))|,\dots$ usw. Das ist die allgemeine Kontinuumshypothese (GCH, General Continuum Hypothesis). Aber da schon die einfache Kontinuumshypothese in ZFC nicht beweisbar ist, ist es die allgemeine auch nicht. Sie kann aber widerspruchsfrei zu den ZFC-Axiomen zugefügt werden, d. h. wenn ZFC widerspruchsfrei ist, dann ist es auch ZFC + GCH.