3.13 Endliche Mengen
In diesem Abschnitt definieren wir, wann eine Menge endlich ist, und wie viele Elemente sie dann hat. Wenn Sie (nicht ganz zu unrecht) denken, dass das ohnehin klar ist, können Sie ihn auch erstmal überspringen, weil die Beweise ein bisschen »technisch« sind. (Und wenn Sie sich irgendwann fragen, wie der Begriff endlich formal definiert wird, darauf zurückkommen.)
Oder Sie betrachten diese technischen Beweise als Fingerübungen, um den Umgang mit Injektivität, Surjektivität und Bijektivität von Abbildungen und der Beweismethode der Induktion zu trainieren.
Für jede natürliche Zahl \(n\) betrachten wir die Menge \([n]:= \{ 1, \dots , n \} \). (Wenn \(n=0\), dann soll das bedeuten, dass \([0]=\emptyset \) die leere Menge bezeichnet.) Das ist für uns der Prototyp für eine endliche Menge mit \(n\) Elementen.
Seien \(m\), \(n\) endliche Zahlen.
Wenn es eine injektive Abbildung \([m]\to [n]\) gibt, dann gilt \(m\le n\).
Wenn es eine bijektive Abbildung \([m]\to [n]\) gibt, dann gilt \(m= n\).
zu (1). Wir führen Induktion nach \(n\). Ist \(n=0\), so ist \([n]=\emptyset \). Ist \(M\to \emptyset \) irgendeine Abbildung, so muss auch \(M=\emptyset \) gelten. Es folgt \([m]=\emptyset \) und damit \(m=0=n\) (denn sonst wäre \(1\in [m]\)).
Sei nun \(n{\gt}0\). Ist \(m=0\), so ist nichts zu zeigen, wir nehmen also auch an, dass \(m {\gt} 0\). Sei \(f\colon [m]\to [n]\) eine injektive Abbildung. Gilt \(f([m-1])\subseteq [n-1]\), so folgt \(m-1 \le n-1\) nach Induktionsvoraussetzung, also \(m\le n\). Sonst ist \(n\in f([m-1])\) und wegen der Injektivität gibt es eine eindeutig bestimmte Zahl \(i\) mit \(1\le i {\lt} m\) und \(f(i)=n\). Andererseits muss (wieder wegen der Injektivität) \(f(m) \ne n\) gelten, also \(f(m)\in [n-1]\). Wir definieren die Abbildung \(g\colon [m-1]\to [n-1]\) wie folgt: \(g(i) = f(m)\), \(g(j) = f(j)\) für \(j \in [m-1]\setminus \{ i\} \). Dann ist \(g\) eine Injektion \([m-1]\to [n-1]\) und nach Induktionsvoraussetzung folgt \(m-1 \le n-1\), also \(m\le n\).
zu (2). Dies folgt direkt aus Teil (1): Ist \(f\) eine Bijektion zwischen \([m]\) und \([n]\), so ist \(f\) injektiv, also \(m\le n\) nach Teil (1), und die Umkehrabbildung von \(f\) ist eine Injektion \([n]\to [m]\), also gilt auch \(n\le m\).
Statt einer Bijektion \([n]\to M\) könnte man natürlich ebenso gut eine Bijektion \(M\to [n]\) betrachten. Durch Übergang zur Umkehrabbildung kann man ja zwischen diesen beiden Standpunkten hin und her gehen.
Wegen des Lemmas kann es für gegebenes \(M\) höchstens für eine einzige Zahl \(n\) eine Bijektion wie in der Definition geben. Die Zahl \(n\) ist also durch \(M\) eindeutig bestimmt, so dass die Definition der Mächtigkeit überhaupt sinnvoll ist. Wir sagen, der Begriff der Mächtigkeit sei wohldefiniert (siehe Abschnitte 3.71, C.1.1).
Ist \(M\) eine Menge und \(M\) nicht endlich, dann sagen wir, \(M\) sei unendlich (und schreiben manchmal \(\# M = \infty \)). Wichtig ist aber zu beachten, dass es zwischen zwei unendlichen Mengen nicht unbedingt eine Bijektion gibt. Zum Beispiel gibt es keine Bijektion zwischen \(\mathbb Q\) und \(\mathbb R\). Siehe Abschnitt 3.15.
Der Mächtigkeitsbegriff hat die Eigenschaften, die man erwartet; allerdings müssen diese, formal betrachtet, natürlich erst einmal bewiesen werden, bevor man sie dann benutzen kann. Zum Beispiel:
Sei \(X\) eine Menge und \(x\in X\) ein Element. Dann gilt
Sei etwa \(n\) die Mächtigkeit von \(X\setminus \{ x\} \), es gibt also eine Bijektion \(f\colon [n]\to X\setminus \{ x\} \). Wir definieren die Abbildung \(g\colon [n+1]\to X\) durch \(g(i) = f(i)\) für alle \(i=1, \dots , n\), und setzen \(g(n+1) = x\). Dann ist \(g\) ebenfalls bijektiv, also \(\# X = n+1 = \# (X\setminus \{ x\} ) + 1\).
Den Beweis des folgenden, ähnlichen Lemmas lassen wir als Übungsaufgabe.
Seien \(X, Y\subseteq M\) endliche Teilmengen einer Menge \(M\). Wenn \(X\cap Y = \emptyset \), dann gilt \(\# (X\cup Y) = \# X + \# Y\).
Eine andere Aussage, die Sie nicht überraschen wird, aber die eben auch eines Beweises bedarf:
Seien \(n\) eine natürliche Zahl, und \(X_1\), …, \(X_n\) nicht-leere Mengen. Dann ist das Produkt \(\prod _{i=1}^n X_i\) nicht leer.
Für \(n=1\) ist nichts zu zeigen, denn \(\prod _{i=1}^i X_i = X_1\) ist nach Voraussetzung nicht leer. (Und für \(n=0\) ist die Aussage auch richtig angesichts unserer Konvention, dass das Produkt mit leerer Indexmenge genau ein Element hat.)
Ist \(n{\gt}1\), so haben wir nach Definition
Nach Induktionsvoraussetzung ist \(\left(\prod _{i=1}^{n-1} X_i\right)\) nicht leer; sei \(x\) ein Element dieser Menge. Nach Voraussetzung ist \(X_n\) nicht leer. Sei \(x^\prime \in X_n\). Dann ist \((x,x^\prime )\in \left(\prod _{i=1}^{n-1} X_i\right)\times X_n\), also ist auch diese Menge nicht leer.
Sei \(f\colon X\to Y\) eine surjektive Abbildung von einer Menge \(X\) in eine endliche Menge \(Y\). Dann existiert eine Abbildung \(g\colon Y\to X\) mit \(f\circ g=\operatorname{id}_Y\).
Nach Lemma 3.61 ist \(\prod _{y\in Y} f^{-1}(\{ y\} )\ne \emptyset \). Ein Element dieses Produkts gibt uns für jedes \(y\in Y\) ein Element in \(X\) mit \(f(x)=y\). Wir definieren \(g(y):=x\).
(Wenn wir \(\prod _{y\in Y} f^{-1}(\{ y\} )\ne \emptyset \) als Teilmenge von \(\prod _{y\in Y} X = \operatorname{Abb}(Y, X)\) betrachten, dann ist jedes Element dieser Teilmenge eine Abbildung \(Y\to X\) mit der gewünschten Eigenschaft.)
So einleuchtend die Aussagen von Lemma 3.61 und Korollar 3.62, und so kurz (wenn auch »technisch«) die Beweise sind: Die Beweise, die wir hier gegeben haben, benötigen die Voraussetzung, dass es sich um ein Produkt mit endlicher Indexmenge handelt beziehungsweise dass \(Y\) eine endliche Menge ist. Für beliebige Indexmengen und Mengen \(Y\) sind diese (zueinander äquivalenten) Aussagen genau der Inhalt des Auswahlaxioms, eines der Axiome der Mengenlehre. Siehe Anhang B.1.
Sei \(f\colon X\to Y\) eine Abbildung zwischen endlichen Mengen.
Wenn \(f\) injektiv ist, dann gilt \(\# X \le \# Y\).
Wenn \(f\) surjektiv ist, dann gilt \(\# X \ge \# Y\).
Seien \(m\) und \(n\) die Mächtigkeiten von \(X\) und \(Y\). Dann existieren Bijektionen \(g\colon [m]\to X\), \(h\colon [n]\to Y\). Die Verkettung \(h^{-1}\circ f\circ g\) ist dann eine Injektion \([m]\to [n]\), und es folgt \(m\le n\) mit Lemma 3.57.
Für den Beweis von Teil (2) wenden wir Korollar 3.62 an und finden eine Abbildung \(g\colon Y\to X\) mit \(f\circ g= \operatorname{id}_Y\). Dann ist \(g\) notwendigerweise injektiv (Lemma 3.33) und die Behauptung folgt aus Teil (1), angewandt auf \(g\).
Seien \(X\), \(Y\) endliche Mengen mit \(\# X=\# Y\). Sei \(f\colon X\to Y\) eine Abbildung. Dann sind äquivalent:
Die Abbildung \(f\) ist injektiv.
Die Abbildung \(f\) ist surjektiv.
Die Abbildung \(f\) ist bijektiv.
Es ist offenbar ausreichend, die Äquivalenz von (i) und (ii) zu zeigen, denn nach Definition gilt (iii) \(\Leftrightarrow \) (i) und (ii).
Sei zunächst \(f\) injektiv. Ist \(f\) nicht surjektiv, dann existiert \(y\in Y\setminus \operatorname{Im}(f)\), also können wir \(f\) als Abbildung \(X\to Y\setminus \{ y\} \) betrachten (die natürlich ebenfalls injektiv ist). Das würde wegen Lemma 3.59 und Lemma 3.63 bedeuten, dass \(\# X \le \# Y -1\), ein Widerspruch.
Ist andererseits \(f\) surjektiv, so gibt es nach Korollar 3.62 eine Abbildung \(g\colon Y\to X\) mit \(f\circ g=\operatorname{id}_Y\). Lemma 3.33 zeigt, dass \(g\) injektiv ist. Aus Teil (1) folgt nun, dass \(g\) sogar bijektiv ist. Da \(f\circ g\) und \(g\) bijektiv sind, ist auch \(f\) bijektiv.
Für eine unendliche Menge ist das Lemma nicht richtig. Überlegen Sie sich eine injektive Abbildung \(\mathbb N\to \mathbb N\), die nicht surjektiv ist, und eine surjektive Abbildung \(\mathbb N\to \mathbb N\), die nicht injektiv ist.
Die Existenz von injektiven, aber nicht surjektiven Abbildungen \(\mathbb N\to \mathbb N\) wird in dem Gedankenexperiment des Hotels mit unendlich vielen Zimmern (zu jeder natürlichen Zahl \(n\) gibt es das Zimmer Nummer \(n\)) illustriert, das D. Hilbert in seiner Vorlesung »Über das Unendliche« 1924 beschrieben hat: Sind alle Zimmer mit Gästen belegt und kommt ein weiterer Gast an, so bittet der Hotelchef einfach jeden Gast, ein Zimmer weiter zu ziehen (von Zimmer \(n\) nach Zimmer \(n+1\)). Dann ist Zimmer \(0\) frei.
Hilberts Hotel auf Wikipedia und auf Youtube: Video von C. Spannagel, Steven Strogatz and Hilbert’s Infinite Hotel/WorldScienceFestival (englisch), Video von J. Dekofsky/Ted-ED (englisch).
Siehe Abschnitt 3.15.