Endliche und abzählbare Mengen – Analysis I (Kap. 1-9)

1.7 Endliche und abzählbare Mengen

In diesem Abschnitt diskutieren wir die Bedeutung von „Endlichkeit“, „Abzählbarkeit“ und „Überabzählbarkeit“ für Mengen. Letztere dienen innerhalb der Mathematik als Möglichkeit, die „Grösse“ einer Menge anzugeben. Auf den genauen Begriff der Kardinalität wollen wir hier nicht eingehen und verweisen stattdessen auf die Vorlesung „Grundstrukturen“ im Frühlingssemester.

Intuitiv ist eine endliche Menge eine Menge, deren Elemente sich „in endlich vielen Schritten“ auflisten lassen, also eine Menge der Form $X = {x_{1}, \dots, x_{n}}$ für ein $n \in ℕ$ (wobei wir aber auch die leere Menge $X = \emptyset$ erlauben werden). Folgende Definition formalisiert diese Intuition.

Definition 1.74 (Endliche Mengen).

Wir sagen, dass die Kardinalität der leeren Menge $\emptyset$ Null ist und schreiben $| \emptyset | = # \emptyset = 0$ . Für $n \in ℕ$ definieren wir ${1, \dots, n} = {m \in ℕ : m \leq n}$ und auch den eigenartigen Fall ${1, \dots, 0} = \emptyset$ . Sei nun $X$ eine beliebige Menge und $n \geq 1$ eine natürliche Zahl. Die Menge $X$ hat Kardinalität $n$ , falls eine Bijektion

\begin{array}{l} {1, \dots, n} \to X \end{array}

existiert. In diesem Fall schreiben wir $| X | = # X = n$ .

Des Weiteren ist $X$ eine endliche Menge, falls $| X | = n$ für eine nicht-negative ganze Zahl $n \in ℕ_{0} = {0, 1, 2, \dots}$ . In diesem Fall sagen wir auch, dass $X$ endliche Kardinalität hat und wir schreiben $| X | < \infty$ .

Ist $X$ keine endliche Menge, so nennen wir $X$ eine unendliche Menge (oder sagen, dass $X$ unendliche Kardinalität hat) und schreiben $| X | = \infty$ .

Man beachte, dass nach der Definition noch nicht klar ist, ob die Kardinalität einer endlichen Menge wohldefiniert ist; in der Tat, falls es eine Bijektion zwischen ${1, \dots, m}$ und ${1, \dots, n}$ für $m \neq n$ für $m \neq n$ gäbe, würde diese ungünstige Situation eintreffen.

Proposition 1.75 (Schubfachprinzip).

Seien $X$ und $Y$ endliche Mengen mit $| X | = m \in ℕ_{0}$ und $| Y | = n \in ℕ_{0}$ . Falls $m > n$ , dann gibt es keine injektive Abbildungen von $X$ nach $Y$ . Insbesondere ist die Kardinalität einer endlichen Menge eine eindeutig bestimmte Zahl in $ℕ_{0}$ und für je zwei endliche Mengen $X$ und $Y$ existiert genau dann eine Bijektion $X \to Y$ wenn $| X | = | Y |$ .

Wir bemerken, dass die Aussage des Schubfachprinzips sehr anschaulich ist. Angenommen man hat $n \geq 1$ Körbe und $m > n$ Äpfel, welche man in die Körbe legen will. Dann besagt das Schubfachprinzip, dass es immer einen Korb geben wird, in dem sich mindestens 2 Äpfel befinden werden und dies unabhängig davon, mit welcher Methode man die Äpfel in die Körbe verteilt. Auch wenn die Aussage von Proposition 1.75 intuitiv äusserst klar ist, werden wir einen Beweis mittels dem Induktionsprinzip durchführen.

Beweis.

Wir nehmen im Folgenden an, dass $X$ eine Menge mit $| X | = m \in ℕ_{0}$ ist, und schreiben $X = {x_{1}, \dots, x_{m}}$ – dies entspricht der Wahl einer Bijektion $i \in {1, \dots, m} \mapsto x_{i} \in X$ . Analog sei $Y$ eine Menge mit $| Y | = n \in ℕ_{0}$ und $Y = {y_{1}, \dots, y_{n}}$ . Wir beweisen nun das Schubfachprinzip mittels Induktion nach $m$ , also dass es für $m > n$ keine injektive Abbildung $f : X \to Y$ gibt.

Falls $n = 0$ ist, dann ist $Y$ die leere Menge. In diesem Fall gibt es für eine Menge $X$ mit $| X | = m > 0$ keine einzige Abbildung $f : X \to Y$ . Inbesondere gibt es für den Fall $m = 1$ (mit der einzige Möglichkeit $n = 0$ ) nichts zu beweisen. Des Weiteren dürfen wir im Folgenden immer $n \geq 1$ annehmen dürfen.

Sei nun $m = 2$ und damit $n = 1$ . In diesem Fall gibt es nur die konstante Funktion von $X = {x_{1}, x_{2}}$ nach $Y = {y_{1}}$ . Da aber $x_{1} \neq x_{2}$ und $f (x_{1}) = y_{1} = f (x_{2})$ , erhalten wir, dass $f$ nicht injektiv ist. Dies beweist das Schubfachprinzip für $m = 2$ .

Angenommen $m > 2$ und das Schubfachprinzip ist für einen Definitionsbereich $X^{'}$ mit $| X^{'} | = m - 1$ bereits bekannt. Seien also $m, n \in ℕ_{0}$ mit $m > n$ und

\begin{array}{l} f : X = {x_{1}, \dots, x_{m}} \to Y = {y_{1}, \dots, y_{n}} \end{array}

eine beliebige Funktion. Falls es ein $i \in {1, \dots, m - 1}$ mit $f (x_{i}) = f (x_{m})$ gibt, so sehen wir bereits, dass $f$ nicht injektiv ist. Also nehmen wir nun an, dass $f (x_{i}) \neq f (x_{m})$ für alle $i \in {1, \dots, m - 1}$ . In diesem Fall definieren wir $X^{'} = {x_{1}, \dots, x_{m - 1}}$ mit $| X^{'} | = m - 1$ , $Y^{'} = Y ∖ {f (x_{m})}$ mit $| Y^{'} | = n - 1$ Formal sollten wir dies begründen, indem wir eine Bijektion zwischen ${1, \dots, n - 1}$ und $Y^{'}$ angeben: Sei $k \in {1, \dots, n}$ so dass $f (x_{m}) = y_{k}$ , dann definiert $y_{i}^{'} = y_{i}$ für $i = 1, \dots, k - 1$ und $y_{i}^{'} = y_{i + 1}$ für $i = k + 1, \dots, n$ eine derartige Bijektion, die $i \in {1, \dots, n}$ auf $y_{i}^{'} \in Y^{'} = {y_{1}, \dots, y_{k - 1}, y_{k + 1}, \dots, y_{n}}$ abbildet., und $f^{'} : x_{i} \in X^{'} \mapsto f (x_{i}) \in Y^{'}$ als die Einschränkung von $f$ auf $X^{'}$ und den Wertebereich $Y^{'}$ . Aus der Induktionsannahme erhalten wir wegen $m - 1 > n - 1$ , dass $f^{'}$ nicht injektiv ist. Dies beweist aber auch (auf Grund der Definition von $f^{'}$ mittels $f$ ), dass $f$ nicht injektiv sein kann. Dies schliesst den Beweis des Induktionsschritts und wir erhalten damit das Schubfachprinzip.

Die verbleibenden Aussagen folgen nun unmittelbar. Für $X = Y$ und die Identität ${id}_{X} : X \to X$ impliziert obiges Schubfachprinzip inbesondere, dass die Kardinalität $| X |$ eindeutig durch $X$ bestimmt ist. Falls $X$ und $Y$ endliche Mengen sind und $f : X \to Y$ eine Bijektion ist, so erhalten wir ebenso zuerst $| X | \leq | Y |$ (da $f$ injektiv ist) und $| Y | \leq | X |$ (da $f^{- 1}$ injektiv ist). Falls $| X | = | Y | = m \in ℕ_{0}$ ist, so können wir die Aufzählungen $X = {x_{1}, \dots, x_{m}}$ und $Y = {y_{1}, \dots, y_{m}}$ verwenden, um die Bijektion $x_{i} \in X \mapsto y_{i} \in Y$ zu definieren.

■

Übung 1.76 (Schubfachprinzip mittels surjektiven Funktionen).

Seien $X$ und $Y$ endliche Mengen mit $| X | = m \in ℕ_{0}$ und $| Y | = n \in ℕ_{0}$ . Falls $m < n$ , dann gibt es keine sujektiven Abbildungen von $X$ nach $Y$ .

Hinweis.

Sie können versuchen der Beweismethode von Proposition 1.75 und Induktion nach $n$ zu folgen: Falls $f : X \to Y = {y_{1}, \dots, y_{n}}$ und $y_{n} \notin f (X)$ so erkennen wir bereits, dass $f$ nicht surjektiv ist. Ansonsten können wir die Induktionsannahme auf $f^{'} : x \in X^{'} = X ∖ f^{- 1} (y_{n}) \mapsto f (x) \in Y^{'} = {y_{1}, \dots, y_{n - 1}}$ anwenden.

Übung 1.77.

Sei $X$ eine endliche Menge und $f : X \to X$ eine Abbildung.

(i): Beweisen Sie, dass Injektivität, Surjektivität und Bijektivität von $f$ äquivalent sind.
(ii): Sei nun $f$ bijektiv. Zeigen Sie, dass es eine natürliche Zahl $n \geq 1$ gibt mit $f^{n} = {id}_{X}$ .

Eine Teillösung für (i).

Sei $X = {X_{1}, \dots, x_{m}}$ für eine natürliche Zahl $m \geq 1$ . Angenommen $f$ ist injektiv. Falls $f$ nicht surjektiv und $z \in X ∖ f (X)$ wäre, so könnte man eine injektive Funktion $f^{'} : x \in X \to f (x) \in Y = X ∖ {z}$ definieren, was im Widerspruch zum Schubfachprinzip steht.

Ein Hinweis für (ii).

Verwenden Sie für ein festes $x_{0} \in X$ das Schubfachprinzip für die Abbildung $n \in {0, \dots, | X |} \mapsto f^{\circ n} (x_{0})$ . Anschliessend kann man Bijektivität von $f$ benutzen, um ein $n \in ℕ$ mit $n \leq | X |$ zu finden mit $f^{\circ n} (x_{0}) = x_{0}$ zu finden.

Übung 1.78 (Funktionenräume für endliche Mengen).

Seien $X$ und $Y$ endliche Mengen. Wir erinnern daran, dass $Y^{X}$ die Menge aller Funktionen $f : X \to Y$ bezeichnet. Zeigen Sie, dass $| Y^{X} | = | Y |^{| X |}$ gilt. Verwenden Sie dazu vollständige Induktion nach der Kardinaliät $| X |$ .

Wie schon am Beispiel der Menge $ℕ$ aller natürlichen Zahlen zu sehen ist, sind nicht alle Mengen endlich. An dieser Stelle kann man sich fragen, ob sich unendliche Menge auch nach Grösse unterscheiden lassen. In der Tat existiert auch für unendliche Menge eine sogenannte Kardinalität; wir werden hier nicht genauer auf diese eingehen und verweisen stattdessen auf die Vorlesung „Grundstukturen“ des Frühlingssemester. Für uns ist hier ausreichend, jene Mengen zu identifizieren, die „gleich gross“ sind wie die Menge der natürlichen Zahlen.

Definition 1.79.

Eine Menge $X$ heisst abzählbar unendlich (oder kurz abzählbar), falls eine Bijektion zwischen $X$ und $ℕ$ existiert. Eine Menge, die weder endlich noch abzählbar unendlich ist, nennt man auch überabzählbar.

Die Definition wiederspiegelt die Anschauung, dass abzählbare Mengen gerade jene sein sollten, die sich „ abzählen lassen“.

Lemma 1.80 (Teilmengen von abzählbaren Mengen).

Sei $X$ eine abzählbar unendliche Menge und $Y \subseteq X$ eine Teilmenge. Dann ist $Y$ entweder endlich oder selbst auch abzählbar unendlich.

Beweis.

Wenn $f : ℕ \to X$ eine Bijektion ist, so ist die Einschränkung von $f$ auf $A = f^{- 1} (Y)$ eine Bijektion von $A$ nach $Y$ . Aus diesem Grund genügt es den Fall einer Teilmenge $A \subseteq ℕ$ zu untersuchen.

Wir definieren eine Funktion $g : A \to ℕ$ durch

\begin{array}{l} g : a \in A \mapsto | A \cap {1, \dots, a} | \in ℕ . \end{array}

Wir zeigen zuerst, dass $g$ injektiv ist. Seien also $a_{1}, a_{2} \in A$ mit $a_{1} \neq a_{2}$ . Falls $a_{1} < a_{2}$ , dann gilt

\begin{array}{l} (A \cap {1, \dots, a_{1}}) ⊔ {a_{2}} \subseteq A \cap {1, \dots, a_{2}} \end{array}

und damit auch $g (a_{1}) < g (a_{2})$ . Der Fall $a_{1} > a_{2}$ ergibt sich analog, und damit ist die Injektivität von $g$ bewiesen.

Wir behaupten nun, dass entweder $A$ endlich (und $g (A) = {1, \dots, | A |}$ ) ist oder dass die Bildmenge gleich $g (A) = ℕ$ ist. Gemeinsam mit obiger Injektivität ergibt sich aber damit genau die erwünschte Aussage des Lemmas für die Teilmenge $A \subseteq ℕ$ .

Für den Beweis der Behauptung wollen wir zuerst zeigen, dass für jedes $n \in ℕ$

\begin{align} {g (a) ∣ a \in A \land a \leq n} = {1, \dots, | A \cap {1, \dots, n} |} & (1.11) \end{align}

gilt. Wir beweisen (1.11) mittels vollständiger Induktion nach $n$ . Für $n = 1$ gibt es zwei Fälle: Falls $1 \in A$ , so ist $g (1) = 1$ und beide Seiten sind gleich ${1}$ . Falls hingegen $1 \notin A$ , so sind beide Seiten die leere Menge.

Angenommen (1.11) ist nun für $n \in ℕ$ bereits bekannt. Für $n + 1$ gibt es ebenso zwei Fälle zu unterscheiden: Falls $n + 1 \in A$ , so ist

\begin{array}{l} {g (a) ∣ a \in A \land a \leq n + 1} & = {g (a) ∣ a \in A \land a \leq n} ⊔ {g (n + 1)} \\ = {1, \dots, | A \cap {1, \dots, n} |} ⊔ {| A \cap {1, \dots, n + 1} |} \\ = {1, \dots, | A \cap {1, \dots, n + 1} |} \end{array}

nach Induktionsvorraussetzung und der Definition von

\begin{array}{l} g (n + 1) = | A \cap {1, \dots, n + 1} | = | A \cap {1, \dots, n} | + 1 . \end{array}

Falls hingegen $n + 1 \notin A$ , so ist

\begin{array}{l} {g (a) ∣ a \in A \land a \leq n + 1} & = {g (a) ∣ a \in A \land a \leq n} \\ = {1, \dots, | A \cap {1, \dots, n} |} \\ = {1, \dots, | A \cap {1, \dots, n + 1} |} . \end{array}

Dies schliesst den Induktionsschritt, womit (1.11) für alle $n \in ℕ$ bewiesen ist.

Falls $A$ eine endliche Menge und $n = \max A \in A$ das grösste Element von $A$ ist, so ist (1.11) für dieses $n$ genau die Aussage $g (A) = {1, \dots, | A |}$ .

Sei also $A$ eine unendliche Menge. In diesem Fall betrachten wir die Vereingung beider Seiten von (1.11) über alle $n \in ℕ$ . Links erhalten wir dabei genau die Bildmenge $g (A)$ . Und rechts erhalten wir als Vereinigung ganz $ℕ$ . Um letzteres zu sehen, wählen wir ein beliebiges $k \in ℕ$ . Da $A$ unendlich ist, gibt es paarweise verschiedene Elemente $a_{1}, a_{2}, \dots, a_{k} \in A$ . Wir wollen hier $a_{1} < a_{2} < \dots < a_{k}$ annehmen. Falls dies nicht erfüllt ist, nummerieren wir unsere Elemente $a_{1}, \dots, a_{k}$ entsprechend um, um dies zu erreichen† Dies ist ein Beispiel für den Formulierung „ohne Beschränkung der Allgemeinheit“.. Auf Grund der Definition von $g$ ist damit $g (a_{k}) \geq k$ und $k \in {1, \dots, g (a_{k})}$ wie behauptet. Also erhalten wir durch Vereinigung beider Seiten von (1.11) die Aussage $g (A) = ℕ$ , womit $A$ abzählbar unendlich ist.

■

Übung 1.81 (Gitterpunkte in der Ebene).

Zeigen Sie, dass $ℕ \times ℕ$ abzählbar unendlich ist.

Hinweis.

Zeichnen Sie sich ein Bild von $ℕ \times ℕ$ in der Ebene und betrachten Sie einen schlangenförmigen Weg durch diese Gitterpunkte.

Die folgende Übung zeigt, dass „abzählbar unendlich“ gewissermassen die kleinste unendliche Kardinalität ist.

Übung 1.82.

Zeigen Sie, dass es für jede unendliche Menge $X$ eine injektive Abbildung $f : ℕ \to X$ gibt.

Bemerkung.

Im Beweis von Übung 1.82 werden Sie wahrscheinlich abzählbar oft eine Wahl treffen müssen. Formal verwendet dies das sogenannte Auswahlaxiom der Mengenlehre (Axiom of Choice), welches wir implizit erlauben werden.