Betrachten wir noch einmal einen Beweis, dass $[0,1] \times [0,1] \approx [0,1]$. Wir nehmen zwei Zahlen $(x,y) \in [0,1] \times [0,1]$ und schreiben sie in Binärdarstellung $0.x_1 x_2 x_3 \dots$ und $0.y_1 y_2 y_3\dots$, wobei wir $1$ nicht als $1.000\dots$, sondern als $0.111\dots$ schreiben. Wir produzieren eine Zahl $f(x,y) \in [0,1]$, indem wir die Binärdarstellungen von $x$ und $y$ verschränken: $f(x,y) = 0.x_1 y_1 x_2 y_2 x_3 y_3 \dots$. Diese Funktion ist injektiv. Aber eben nicht surjektiv: die Zahl $0.00111111$ beispielsweise ist nicht im Wertebereich der Funktion. Aber da $[0,1] \times [0,1]$ ja viel größer als $[0,1]$ erscheint, ist die Hauptarbeit geleistet. Surjektivität herzustellen sollte nicht so schwer sein. Formalisieren wir diese Gedanken durch etwas Notation.
Definition Seien $A$ und $B$ zwei Mengen. Wir schreiben $A \leq B$, wenn es eine injektive Funktion $f : A \rightarrow B$ gibt. Falls $A \leq B$ und $A \not \approx B$ gilt, so schreiben wir $A \lt B$.
Beispielsweise haben wir $\N \lt \R$. Obige injektive Funktion $f : [0,1]\times [0,1]\rightarrow [0,1]$ bezeugt, dass $[0,1] \times [0,1] \leq [0,1]$. Gilt auch $[0,1] \leq [0,1] \times [0,1]$? Natürlich: die Funktion $g : [0,1] \rightarrow [0,1] \times [0,1]$ mit $g(x) = (x,0)$ ist injektiv. Jetzt sollten Sie aufhorchen: wir haben zwei Mengen $A = [0,1] \times [0,1]$ und $B = [0,1]$ und haben $A \leq B$ und $B \leq A$ gezeigt. Folgt daraus nicht offensichtlich, dass $A$ und $B$ gleich groß sind, also $A \approx B$? Lassen Sie sich nicht von der suggestiven Notation $\leq$ verführen! $A \leq B$ und $B \leq A$ heißen, dass es injektive Funktion $f : A \rightarrow B$ und $g : B \rightarrow A$ gibt. Um daraus zu folgern, dass $A \approx B$ gilt, müssen wir diese zu einer bijektiven Funktion $h: A \rightarrow B$ kombinieren. Geht das immer?
Theorem (Schröder-Bernstein-Theorem). Seien $A$ und $B$ zwei Mengen. Wenn $A \leq B$ und $B \leq A$ gilt, dann gilt $A \approx B$. In Worten: wenn es injektive Funktionen $f: A \rightarrow B$ und $g : B\rightarrow A$ gibt, dann gibt es auch eine bijektive Funktion $h: A \rightarrow B$.
Beweis. Wir tun so, als ob $A \cap B = \emptyset$ gälte. Falls dies nicht der Fall sein sollte, können wir $A$ durch $A \times \{0\} = \{ (a,0) \ | \ a \in A\}$ ersetzen und $B$ durch $A \times \{1\} = \{ (b,1) \ | \ b \in B\}$. Wir betrachten nun die Menge $A \cup B$ und zeichnen Pfeile ein: $f$-Pfeile von jedem $a$ zu $f(a)$ und $g$-Pfeile von jedem $b$ zu $f(b)$:
Wenn wir die Menge $A \cup B$ zusammen mit den $f$- und $g$-Pfeilen als Graphen auf einer unendlichen Menge betrachten, dann sehen wir, dass es vier Arten von Komponenten: (1) unendliche Pfade, die mit einem roten kreisförmigen Punkt $a \in A$ beginnen; (2) unendliche Pfade, die mit einem blauen quadratischen Punkt $b \in B$ beginnen; (3) solche, die in beide Richtungen unendlich sind und keinen Anfangspunkt haben; (4) solche, die aus endlich vielen Punkten bestehen. Wir definieren nun die Bijektion $h$, indem wir in den Komponenten vom Typ (1), (3) und (4) die Funktion $f$ verwenden, in den vom Typ (2) jedoch $g^{-1}$:
Formalisieren wir das ein bisschen. Wir definieren eine Folge $X_0, X_1, \dots$, sodass $X_{2i} \subseteq B$ und $X_{2i+1} \subseteq A$ für alle $i \geq 0$ gilt:
\begin{align*} X_0 & := B \setminus {\rm img} (f) \\ X_{2i+1} & := g(X_{2i}) \\ X_{2i+2} & := f(X_{2i+1})\\ A' & := X_1 \cup X_ 3 \cup X_5 \cup X_7 \cup \dots \ . \end{align*}In Worten: $X_0$ sind die $B$-Punkte, die keine eingehende $f$-Kante haben. $X_i$ sind dann diejenigen Knoten, die auf einem Pfad vom Typ (2) liegen und von dem (blauen, in $B$ liegenden) Anfangspunkt Abstand $i$ haben. $A'$ sind also die $A$-Knoten, die auf einer Typ-(2)-Komponente liegen. Wir können nun unsere Bijektion $h : A \rightarrow B$ definieren:
\begin{align*} h : A & \rightarrow A\\ a & \mapsto \begin{cases} f(a) & \textnormal{ if $a \in A \setminus A'$} \\ g^{-1}(a) & \textnormal{ if $a \in A'$.} \end{cases} \end{align*}Wir müssen nun zeigen, dass $h$ bijektiv ist (falls das noch nicht klar sein sollte).
Behauptung 1. $g^{-1}(a)$ ist definiert für jedes $a \in A'$.
Beweis. Wenn $a \in A'$ gilt, dann gilt $a \in X_{2i+1}$, also für einen ungeraden Index. Nach Konstruktion gilt $X_{2i+1} = g(X_{2i})$, die Menge aller Bilder von $X_{2i}$ unter $g$; daher gibt es zu $a \in X_{2i+1}$ auch ein $b \in X_{2i}$ mit $g(b) = a$. In andere Worten: $g^{-1}(a)$ ist definiert.
\(\square\)Eindeutig ist $g^{-1}(a)$ sowieso, falls es existiert. Wir sehen nun: $h$ ist wohldefiniert. Ist es injektiv?
Behauptung 2. $h$ ist injektiv.
Beweis. Seien $a, a' \in A$ zwei verschiedene Elemente. Wir unterscheiden drei Fälle: (1) Wenn $a, a' \in A \setminus A'$, dann gilt $h(a) = f(a) \ne f(a') = h(a')$, weil $f$ injektiv ist. (2) Wenn $a, a' \in A$, dann gilt $h(a) = g^{-1}(a) =: b$ und $h(a') = g^{-1}(a') =: b'$. Nun gilt auch $b \ne b'$: wenn nämlich $b = b'$ gälte, dann auch $g(b) = g(b')$; ersteres ist aber $a$, letzteres ist $a'$. (3) Wenn $a \in A \setminus A'$ und $a' \in A'$ ist (oder umgekehrt), dann gilt $h(a) = f(a) =: b$ und $h(a') = g^{-1}(a') =: b'$, also $g(b') = a'$. Wir müssen nun zeigen, dass $b \ne b'$. Da $a' \in X_{2i+1}$ für ein $i$ muss $b' \in X_{2i}$ gelten. Wenn $i=0$ ist, dann gilt $b' \in X_{2i} = B \setminus {\rm img}(f)$. Da $f(a) = b$ gilt aber $b \in {\rm img}(f)$ und $b$ und $b'$ sind verschieden. Wenn $i \geq 1$ ist, dann bedeutet $b' \in X_{2i}$, dass es ein $a'' \in X_{2i-1}$ gibt mit $f(a'') = b'$. Da $a'' \in X_{2i-1} \subseteq A'$ aber $a \in A \setminus A'$ , gilt $a'' \ne a$ und somit auch $b \ne b'$. \(\square\)
Behauptung 3. $h$ ist surjektiv.
Beweis. Wir unterscheiden zwei Fälle. (1) Wenn $b \in X_0 \cup X_2 \cup X_4 \cup \dots$ ist, also sagen wir $b \in X_{2i}$, dann sei $a := f(b)$. Es gilt $a \in X_{2i+1}$ und daher $h(a) = g^{-1}(a) = b$. Das Element $b$ hat also ein Urbild, nämlich $a$.
(2) Wenn $b \not \in B'$, dann gilt insbesondere $b \not \in X_0 = B \setminus {\rm img}(f)$; also $b \in {\rm img} (f)$. Es gibt also ein $a \in A$ mit $f(a) = b$. Was ist $h(a)$? Wenn $a \in A \setminus A'$ gilt, dann ist $h(a) = f(a) = b$, und wir haben ein Urbild für $b$ gefunden. Was aber, wenn $a \in A'$, also $a \in X_{2i+1}$? Weil $f(a)=b$ wäre dann $b \in X_{2i+2} \subseteq B'$, wir befänden uns also in Fall (1).
\(\square\)Wir haben nun gezeigt, dass $h$ definiert ist, injektiv und surjektiv ist. Damit ist $h$ eine Bijektion. \(\square\)
Wenn Sie der formale Beweis zu sehr verwirrt, dann halten Sie sich einfach an die Bilder mit den zwei Arten von Punkten und Pfeilen.