Satz von Cantor-Bernstein-Schröder

In der Mengenlehre ist das Cantor-Bernstein-Schröder-Theorem eine Aussage über die Mächtigkeiten zweier Mengen.

Theorem

Wenn eine Injektion f: A -> B und eine Injektion g: B -> A existieren, dann existiert eine Bijektion h: A -> B.

Das bedeutet: Ist die Mächtigkeit von A kleinergleich der von B und die Mächtigkeit von B kleinergleich der von A, dann sind A und B gleichmächtig. Dies ist offenbar eine wünschenswerte Eigenschaft von Mächtigkeiten und damit auch von Kardinalzahlen.

Beweisidee

Wir geben hier eine Beweisidee (zuerst gegeben von Eilenberg?).

Wir definieren die Mengen

$C_{0}:=A\setminus g(B)$

$C_{n+1}:=g(f(C_{n}))\quad {\mbox{ für }}n\geq 0$

$C:=\bigcup _{n=0}^{\infty }C_{n}$

Für jedes x aus A setzen wir dann

$h(x):={\begin{cases}f(x)&{\mbox{ falls }}x\in C\\g^{-1}(x)&{\mbox{ falls }}x\not \in C\end{cases}}$

Da im Falle, dass x nicht in C ist, x in g(B) liegen muss, gibt es ein eindeutig bestimmtes Element g^-1(x) und h ist eine wohldefinierte Abbildung von A nach B.

Man kann nun zeigen, dass diese Funktion h: A -> B die gewünschte Bijektion ist.

Beachte, dass diese Definition von h nicht konstruktiv ist, d.h. es gibt kein Verfahren, um für beliebige Mengen A, B und Injektionen f, g in endlich vielen Schritten zu entscheiden, ob ein x aus A in C liegt oder nicht. Für spezielle Mengen und Abbildungen kann das natürlich möglich sein.

Veranschaulichung

Veranschaulichen kann man sich die Definition von h anhand der folgenden Darstellung.

Dargestellt sind Teile der (disjunkten) Mengen A und B sowie die Abbildungen f und g. Betrachtet man A vereinigt B als Graphen, dann zerfällt der Graph in verschiedene Zusammenhangskomponenten. Diese lassen sich in vier Typen einteilen: beidseitig unendliche Pfade; endliche Zyklen; unendliche Pfade, die in A beginnen; unendliche Pfade, die in B beginnen (von jedem Typ ist hier einer vertreten, da der Pfad durch das Element a beidseitig unendlich sein soll). Es ist aber allgemein nicht in endlich vielen Schritten entscheidbar, welchen Typ der durch ein vorgegebenen Element gehende Pfad hat.

Die oben definierte Menge C enthält nun genau die Elemente von A, die Teil eines in A beginnenden Pfades sind. Die Abbildung h wird so definiert, dass sie innerhalb einer jeden Zusammenhangskomponente eine Bijektion der A-Elemente auf "im Pfad benachbarte" B-Elemente herstellt (dabei hat man nur bei den beidseitig unendlichen Pfaden eine Richtungswahl und wir legen uns auf "rückwärts" fest).

Ursprünglicher Beweis

Der ursprüngliche Beweis von Georg Cantor basierte auf dem Auswahlaxiom, denn Cantor erhielt ihn als Folgerung aus dem Wohlordnungssatz. Der obige Beweis zeigt, dass man das Theorem auch ohne Auswahlaxiom erhält.