3.5 Das Schröder-Bernstein-Theorem

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 3.5.1 Seien $A$ und $B$ zwei Mengen. Wir schreiben $A \leq B$ , wenn es eine injektive Funktion $f : A \to B$ gibt. Falls $A \leq B$ und $A ≉ B$ gilt, so schreiben wir $A < B$ .

Beispielsweise haben wir $N < R$ . Obige injektive Funktion $f : [0, 1] \times [0, 1] \to [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] \to [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 \to B$ und $g : B \to A$ gibt. Um daraus zu folgern, dass $A \approx B$ gilt, müssen wir diese zu einer bijektiven Funktion $h : A \to B$ kombinieren. Geht das immer?

Theorem 3.5.2 (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 \to B$ und $g : B \to A$ gibt, dann gibt es auch eine bijektive Funktion $h : A \to 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 , sodass und für alle gilt:

In Worten: sind die -Punkte, die keine eingehende -Kante haben. sind dann diejenigen Knoten, die auf einem Pfad vom Typ (2) liegen und von dem (blauen, in liegenden) Anfangspunkt Abstand haben. sind also die -Knoten, die auf einer Typ-(2)-Komponente liegen. Wir können nun unsere Bijektion definieren:

Wir müssen nun zeigen, dass bijektiv ist (falls das noch nicht klar sein sollte).

Behauptung 1. ist definiert für jedes .

Beweis. Wenn gilt, dann gilt , also für einen ungeraden Index. Nach Konstruktion gilt , die Menge aller Bilder von unter ; daher gibt es zu auch ein mit . In andere Worten: ist definiert.

Eindeutig ist sowieso, falls es existiert. Wir sehen nun: ist wohldefiniert. Ist es injektiv?

Behauptung 2. ist injektiv.

Beweis. Seien zwei verschiedene Elemente. Wir unterscheiden drei Fälle: (1) Wenn , dann gilt , weil injektiv ist. (2) Wenn , dann gilt und . Nun gilt auch : wenn nämlich gälte, dann auch ; ersteres ist aber , letzteres ist . (3) Wenn und ist (oder umgekehrt), dann gilt und , also . Wir müssen nun zeigen, dass . Da für ein muss gelten. Wenn ist, dann gilt . Da gilt aber und und sind verschieden. Wenn ist, dann bedeutet , dass es ein gibt mit . Da aber , gilt und somit auch .

Behauptung 3. ist surjektiv.

Beweis. Wir unterscheiden zwei Fälle. (1) Wenn ist, also sagen wir , dann sei . Es gilt und daher . Das Element hat also ein Urbild, nämlich .

(2) Wenn , dann gilt insbesondere ; also . Es gibt also ein mit . Was ist ? Wenn gilt, dann ist , und wir haben ein Urbild für gefunden. Was aber, wenn , also ? Weil wäre dann , wir befänden uns also in Fall (1).

Wir haben nun gezeigt, dass definiert ist, injektiv und surjektiv ist. Damit ist eine Bijektion.

Wenn Sie der formale Beweis zu sehr verwirrt, dann halten Sie sich einfach an die Bilder mit den zwei Arten von Punkten und Pfeilen.