Satz von Schröder-Bernstein

Bei Untersuchungen zur Gleichmächtigkeit von Mengen ist es oft einfacher injektive Abbildungen zwischen den Mengen zu finden als Bijektionen. Dann hilft der Satz von Schröder-Bernstein weiter, der aus der Injektiviität zweier Mengen untereinander die Bijektivität folgert.

Zuerst ein Lemma

Sei $f:A\rightarrow B$ eine injektive Abbildung und $B\subseteq A$, dann lassen sich $A$ und $B$ bijektiv aufeinander abbilden.

Wenn $A=B$ ist, können wir trivialerweise ein Bijektion finden nämlich die identische Abbildung.

Für den nichttrivialen Fall gilt $A\setminus B\neq \emptyset$ und wir definieren induktiv ein Mengensystem $(C_n)$:

$C_0=A\setminus B$

$C_n=f(C_{n-1})$ für $n>0$

Offensichtlich gilt $C_n\subseteq B$ für $n>0$, damit ist jedes dieser $C_n$ disjunkt zu $C_0$.

Wir werden jetzt zeigen, dass die $C_n$ sogar paarweise disjunkt sind.

Diesen Teilbeweis führen wir indirekt und wir nehmen dazu an, dass die $C_n$ nicht paarweise disjunkt sind, dann muss es zwei $i\neq j$ geben, für die gilt $C_i\cap C_j\neq\emptyset$. Wir können sogar annehmen, dass diese $i$ und $j$ die kleinsten sind, für die die Disjunktheit verletzt ist. (Sonst nehmen wir einfach die kleineren.) Da aber alle Mengen für $n>0$ disjunkt zu $C_0$ sind, muss $i\neq 0$ und $j\neq 0$ gelten. Damit ist: $C_i=f(C_{i-1})$ und $C_j=f(C_{j-1})$ und wir haben $\emptyset\neq C_i\cap C_j=f(C_{i-1})\cap f(C_{j-1})$ $=f(C_{i-1}\cap C_{j-1})$. Letztere Identität ergibt sich insbesondere aus der Injektivität von $f$ und Satz 5212B. Damit ist aber $C_{i-1}\cap C_{j-1}\neq \emptyset$ im Widerspruch zur Annahme, dass $i,j$ minimal waren.

Nach soviel Vorarbeit werden wir jetzt eine Abbildung $h: A\rightarrow B$ konstruieren, die bijektiv ist.

Wir definieren $C:=\bigcup\limits_{n\in\dom N} C_n$ und

Mit diesen Festlegungen ist $h$ wohldefiniert, denn wenn $x\in C$, dann gibt es ein eindeutig bestimmtes $n$ mit $x\in C_n$ und $h(x)=f(x)\in B$. Wenn $x\notin C$ muss aber $x\in B$ gelten und $x=h(x)\in B$.

$h$ ist auf Grund der Konstruktion trivialerweise injektiv.

Um die Surjektivität von $h$ zu zeigen, unterscheiden wir für ein $b\in B$ zwei Fälle.

1. Fall: Sei $b\in C$, dann gibt es ein eindeutig bestimmtes $n>0$ mit $b\in C_n=f(C_{n-1})\subseteq B$. Damit muss es aber ein $a\in C_{n-1}$ geben mit $b=f(a)=h(a)$.

2. Fall: Sei $b\notin C$, dann gilt aber $b=h(b)$ und $b$ ist sein eigenes Urbild.

Damit ist die Bijektivität von $h$ gezeigt. $\qed$

Seien $A$ und $B$ zwei Mengen und $f: A\rightarrow B$ sowie $g: B\rightarrow A$ zwei injektive Abbildungen. Dann existiert eine Bijektion $h$ zwischen den Mengen $A$ und $B$; insbesondere sind sie dann gleichmächtig.

Mit den Vorbereitungen im obigen Lemma geht der Beweis flott von der Hand.

Wenn $f$ und $g$ injektiv sind, betrachten wir die Zusammensetzung $g\circ f: A\rightarrow g(B)$. Diese ist offensichtlich injektiv. Mit obigen Lemma gibt es dann also eine Bijektion $h^\prime: A\rightarrow g(B)$. Wegen der Injektivität von $g$ existiert $g^{-1}: g(B)\rightarrow B$ und ist auf $g(B)$ eingeschränkt sogar bijektiv (siehe Lemma 5212C). Wir definieren $h=g^{-1}\circ h'$ und haben unsere gesuchte Bijektion von $A$ auf $B$. $\qed$