Endliche und abzählbare Mengen

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.71 (Endliche Mengen).

Wir sagen, dass die Kardinalität der leeren Menge $\emptyset$ Null ist und schreiben $| \emptyset | = # \emptyset = 0$ . 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} : = {m \in ℕ : m \leq 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$ eine nicht-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.72 (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.72 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$ (Wieso?), 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.73 (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$ .

Übung 1.74.

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^{\circ n} = {id}_{X}$ .

Übung 1.75 (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.76.

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“.

Übung 1.77 (Gitterpunkte in der Ebene).

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

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

Übung 1.78.

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

Bemerkung.

Im Beweis von Übung 1.78 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.