Benutzer:Jürgen-Michael Glubrecht/Mächtigkeit

Äquivalenzsatz von Cantor-Bernstein-Schröder

Satz (Äquivalenzsatz von Cantor-Bernstein-Schröder)

Ist $A$ schmächtiger als $B$ und $B$ schmächtiger als $A$, dann sind $A$ und $B$ gleichmächtig:

$A\precsim B\land B\precsim A\Longrightarrow A\sim B$

Dieser Satz liefert ein weiteres Kriterium dafür, wie die Gleichmächtigkeit zweier Mengen bewiesen werden kann. Indem nämlich zwei Funktionen angegeben werden: $f:A\longmapsto B{\text{ injektiv}}$ und $g:B\longmapsto A{\text{ injektiv}}$. Wir beweisen den Satz in mehreren Schrtten und zeigen zunächst die Äquivalenz mit dem Zwischenmengensatz.

Satz (Zwischenmengensatz)

Liegt eine Menge $B$ zwischen einer Menge $A$ und einem injektiven Bild von $A$, so sind $A$ und $B$ gleichmächtig.

$f:A\longmapsto A{\text{ injektiv }}\land A\supseteq B\supseteq f(A)\Longrightarrow A\sim B$

Wir zeigen zunächst, dass der Äquivalenzsatz und der Zwischenmengensatz äquivalent sind:

Satz

${\text{Äquivalenzsatz von Cantor-Bernstein-Schröder }}\iff {\text{ Zwischenmengensatz}}$

Beweis

"$\Rightarrow$": Es gelte der Äquivalenzsatz von Cantor-Bernstein-Schröder. Weiterhin sei $f:A\longmapsto A{\text{ injektiv }}$ und es gelte $A\supseteq B\supseteq f[A]$. Setze $g:=f\upharpoonright B$, dann bildet $g$ Injektiv in $A$ ab. Mit dem Satz von Cantor-Bernstein-Schröder folgt $A\sim B$.

"$\Leftarrow$": Gelte nun der Zwischenmengensatz, sowie $f:A\longmapsto B$ injektiv und $g:B\longmapsto A$ Injektiv. Dann ist auch die Verkettung injektiv $(g\circ f):A\longmapsto A$ und es gilt: $A\supseteq g(B)\supseteq (h\circ f)(A)$. Mit dem Zwischenmengensatz folgt $A\sim B$. ✔

Für den Beweis des Zwischenmengensatzes definieren wir noch eine spezielle Halbordnung:

Definition (Spezielle Halbordnung)

Es sei $f:A\longmapsto A$ eine Funktion von $A$ in $A$. Dann ist ${\mathsf {Fix}}(f):=\{x\in A\,|\,f(x)=x\}$ die Menge der Fixpunkte von $f$. Für zwei beliebige Funktionen $f:A\longmapsto A$ und $g:A\longmapsto A$ ist die Relation $\sqsubseteq$ wie folgt definiert:

$g\sqsubseteq f:\iff {\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(f)\land \forall x:(x\neq g(x)\Rightarrow g(x)=f(x))$

$g\sqsubseteq f$ besagt, dass $g$ mehr Fixpunkte als $f$ hat, aber ansonsten mit $f$ übereinstimmt.

Aufgabe: Zeige, dass $\sqsubseteq$ eine Halbordnung ist.

Zu zeigen ist, $\sqsubseteq$ ist reflexiv, transitiv und antisymmetrisch.

reflexiv: Es gilt ${\mathsf {Fix}}(g)={\mathsf {Fix}}(g)$ und $g(x)=f(x)$, also auch $g\sqsubseteq g$.

transitiv: Gelte $g\sqsubseteq f$ und $f\sqsubseteq h$. Dann folgt ${\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(f)$ und ${\mathsf {Fix}}(f)\supseteq {\mathsf {Fix}}(h)$. Daraus ergibt sich ${\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(h)$. Für $x\neq g(x)$ ist $x$ kein Fixpunkt von $f$ und auch kein Fixpunkt von $h$. Also folgt $g(x)=f(x)=h(x)$ und somit $g\sqsubseteq h$.

antisymmetrisch: Gelte $g\sqsubseteq f$ und $f\sqsubseteq g$. Dann gilt ${\mathsf {Fix}}(g)\supseteq {\mathsf {Fix}}(f)$ und ${\mathsf {Fix}}(f)\supseteq {\mathsf {Fix}}(g)$ also ${\mathsf {Fix}}(g)={\mathsf {Fix}}(f)$. Daher stimmen beide Funktionen überein $g(x)=f(x)$ und es gilt: $g=f$.

Die Beweisidee ist folgende: wir betrachten alle injektiven Funktionen $h:A\longmapsto B$, die zwar mehr Fixpunkte haben als die gegebene Funktion $f:A\longmapsto B$, aber ausserhalb dieser Fixpunkte mit $f$ übereinstimmen. Je mehr Fixpunkte diese Funktionen haben, desto weniger Funktionswerte stimmen mit $f$ überein. Unter diesen Funktionen gibt es (hoffentlich) welche, deren Bildbereich weitere Elemente von $B$ umfasst. Diese müssen Fixpunkte sein, denn ansonsten sind keine Abweichungen von $f$ erlaubt. Wenn es unter den betrachteten Funktionen eine gibt, in deren Bildbereich alle Elemente von $B$ liegen, haben wir eine Bijektion $A\longmapsto B$ gefunden.

Beweis (Zwischenmengensatz, Äquivalenzsatz)

Sei nun $f:A\longmapsto A{\text{ injektiv}}$ und gelte $A\supseteq B\supseteq f(A)$. Sei weiterhin:

$J:=\{h\,|\,h:A\longmapsto B{\text{ injektiv}}\land h\sqsubseteq f\}$

$J$ ist die Menge aller injektiven Funktionen $A\longmapsto B$, die mehr Fixpunkte als $f$ haben. Es gilt $f\in J$, denn $f$ ist nach Voraussetzung Injektiv, $f(A)\subseteq B$ und es gilt $f\sqsubseteq f$. Wir definieren:

$F:=\bigcup _{h\in J}{\mathsf {Fix}}(h)$

$F$ ist die Fixpunktmenge aller Funktionen aus $J$. Es gilt $F\subseteq B$, denn wenn $x\in F$ gibt es ein $h\in J$ dessen Fixpunkt $x$ ist und da $h:A\longmapsto B$ gilt $x=f(x)\in B$. Wir definieren schliesslich die gesuchte Bijektion:

$\color {red}g(x)={\begin{cases}x,&{\text{wenn }}x\in F\\f(x),&{\text{sonst}}\end{cases}}$

$g:A\longmapsto B{\text{ injektiv}}$, da $f$ injektiv ist, und es gilt nach Definition von $g$:

($\star$)   $\forall h\in J:g\sqsubseteq h$

Da ja $f\in J$, wie oben gezeigt, gilt $g\sqsubseteq f$. Wir zeigen nun: $g{\text{ ist injektiv}}$. Seien $x,y\in A$ und gelte $x\neq y$. Sind $x,y\in F$, dann folgt $g(x)=x\neq y=g(y)$. Sind $x,y\in A\setminus F$ folgt $g(x)=f(x)\neq f(y)=g(y)$ aus der Injektivität von $f$. Bleibt als letzter Fall $x\in F$ und $y\in A\setminus F$. Dann gibt es $h\in J$ mit $x\in {\mathsf {Fix}}(h)$ und es folgt: $g(x)=x=h(x)\neq h(y)=f(x)=g(y)$ mit der Injektivität von $h$. Insgesamt haben wir gezeigt:

$g\in J$

Als letzten Schritt beweisen wir, dass $g$ surjektiv auf $B$ ist und zeigen dazu $B\subseteq g(A)$. Wir definieren die Funktion $j:A\longmapsto B$ wie folgt:

$j(x)={\begin{cases}x,&{\text{ wenn }}x\in B\setminus g(A)\\g(x),&{\text{ sonst}}\end{cases}}$

$j$ ist injektiv wegen der Injektivität von $g$. Weiterhin gilt $j\sqsubseteq g$, denn $j$ hat allenfalls mehr Fixpunkte als $g$ und für $x\neq j(x)$ gilt $j(x)=g(x)$. Mit $g\sqsubseteq f$ folgt daraus $j\sqsubseteq f$ wegen wegen der Transitivität von $\sqsubseteq$. Insgesamt haben wir gezeigt: $j\in J$. Daraus folgt mit ($\star$) $g\sqsubseteq j$ und mit der Antisymmetrie von $\sqsubseteq$ ergibt sich $j=g$. Nach Definition von $j$ gilt $B\setminus g(A)\subseteq j(A)$ und mit der Gleichheit $j=g$ folgt $B\setminus g(A)\subseteq g(A)$. Das ist aber nur möglich, wenn $B\setminus g(A)=\varnothing$ gilt, also: $B\subseteq g(A)$. Also:

$\color {red}g:A\longmapsto B{\text{ bijektiv}}$, also: $A\sim B$

Damit ist der Beweis des Zwischenmengensatzes und des Äquivalenzsatzes von Cantor-Bernstein-Schröder beendet. ✔

Beispiel

Wir verwenden die Bezeichnungen wie im Beweis des Zwischenmengensatzes.

Beispiel (Zwischenmengensatz)

Es sei $A:=\mathbb {N} _{0}$ die Menge der natürlichen Zahlen, $B:=\mathbb {N} ^{+}=\{x\in \mathbb {N} \,|\,x\geq 1\}$ die Menge der natürlichen Zahlen größer oder gleich $1$ und $f:A\longmapsto B:f(x)=x+2$ die Funktion, die jede Zahl um 2 erhöht. $f$ ist injektiv und es gilt:

$A\supseteq B\supseteq f(A)$

$B$ ist eine echte Obermenge von $f(A))$, denn die $1$ ist kein Bild unter $f$. Wir definieren $g$ folgendermassen:

$g(x)={\begin{cases}x,&{\text{ wenn }}x{\text{ ungerade}}\\x+2,&{\text{ sonst}}\end{cases}}$

$g:A\longmapsto B$ ist injektiv und alle ungeraden Zahlen sind Fixpunkte. Auf den geraden Zahlen stimmt $g$ mit $f$ überein. Da $f$ keine Fixpunkte hat, gilt also $g\sqsubseteq f$. somit gilt $g\in J$. Da $g(1)=1$ ist, ist $g$ eine Bijektion auf $B$.

Mehr Fixpunkte als $g$ kann aber keine Funktion aus $J$ haben, denn die geraden Zahlen können keine Fixpunkte sein. Das folgt durch Induktion: $0$ ist kein Fixpunkt, denn $0\notin B$, tritt also nicht als Bild auf. Sei nun $n$ gerade und nach Induktionsvoraussetzung kein Fixpunkt. Dann ist das Bild von $n$ aber $f(n)=n+2$. Also kann $n+2$ auch kein Fixpunkt sein. Daher ist $g$ in diesem Beispiel tatsächlich die Funktion, deren Existenz im Beweis gezeigt wird.

Vertiefung zum Thema Mächtigkeit

Wir haben definiert, dass zwei Mengen $A$ und $B$ genau dann gleichmächtig sind, wenn es zwischen ihnen eine bijektive Abbildung gibt: $A\sim B$. Die Relation $\sim$ ist eine Äquivalenzrelation auf der Klasse aller Mengen.

Hinweis

Die Klasse aller Mengen ist zu groß für eine Menge, sie ist eine echte Klasse, vgl. "Axiomatische Mengenlehre".

Frage: Zeige dass $\sim$ eine Äquivalenzrelation ist.

Um zu zeigen, dass eine Relation eine Äquivalenzrelation ist, müssen wir zeigen, dass sie reflexiv, symmetrisch und transitiv ist. Im folgenden seien $A,B,C$ beliebige Mengen.

Reflexiv: Die Identitätsabbildung $f:A\longmapsto A:f(x)=x$ ist eine Bijektion der Menge $A$ auf sich. Also gilt $A\sim A$.

Symmetrisch: Gelte $A\sim B$. Dann gibt es eine bijektive Abbildung $f:A\longmapsto B$. Daher ist die Umkehrfunktion $f^{-1}$ ebenfalls bijektiv und bildet die Menge $B$ auf die Menge $A$ ab: $f^{-1}:B\longmapsto A$. Also gilt $B\sim A$.

Transitiv: Gelte $A\sim B$ und $B\sim C$. Dann gibt es bijektive Abbildungen $f:A\longmapsto B$ und $g:B\longmapsto C$. Die Komposition dieser beiden Abbildungen $g\circ f$ ist als Komposition zweier bijektiven Abbildungen ebenfalls bijektiv und bildet $A$ auf $C$ ab: $g\circ f:A\longmapsto C$. Also gilt $A\sim C$. ✔

Da die Relation $\sim$ eine Äquivalenzrelation ist, zerfällt die Klasse aller Mengen unter dieser Relation in Äquivalenzklassen gleichmächtiger Mengen. Da diese Äquivalenzklassen ebenfalls echte Klassen sind, geht man zu einem Repräsentantensystem über, den sogenannten Kardinalzahlen:

Definition (Kardinalzahlen)

Die Kardinalzahlen sind Mengen und bilden ein Repräsentantensystem für die Äquivalenzklassen gleichmächtiger Mengen.

$|A|$ bezeichnet die Kardinalzahl, die zu der Äquivalenzklasse von $A$ gehört.

Anmerkung: Die Schreibweise $|A|$ sollte nicht mit den mit den Betragsstrichen oder der Determinantenfunktion aus der Linearen Algebra verwechselt werden.

Definition (Ordnung der Kardinalzahlen)

Die folgende Definition ist repräsentantenunabhängig:

$|A|\leq |B|:\iff A\precsim B$

Es ist leicht zu zeigen, dass die Relation $\leq$ reflexiv und transitiv ist. Die Antisymmetrie folgt mit dem Äquivalenzsatz von Cantor-Bernstein-Schröder. $\leq$ ist also eine Halbordnung. Mit dem Auswahlaxiom kann man zeigen, dass $\leq$ eine Totalordnung ist:

Satz

$\leq$ ist eine Totalordnung auf den Kardinalzahlen.

Kardinalzahlen lassen sich also der Größe nach vergleichen. Sie sind verallgemeinerte natürliche Zahlen, die die Mächtigkeit einer Menge beschreiben. Im Fall einer endlichen Menge ist ihre Kardinalzahl nichts anderes als die Anzahl ihrer Elemente. Die endlichen Kardinalzahlen sind also die natürlichen Zahlen $0,1,2,3,\dots$. Beispielsweise ist $|\varnothing |=0$ und $|\{2,3\}|=2$.

Die unendlichen Kardinalzahlen werden mit $\aleph _{0},\aleph _{1},\aleph _{2},\dots$ bezeichnet (der Buchstabe Aleph $\aleph$ ist der erste Buchstabe des hebräischen Alphabets).

$\aleph _{0}$ ist die kleinste Mächtigkeit, die eine unendliche Menge haben kann: man kann zeigen, dass jede unendliche Menge eine Mächtigkeit größer oder gleich $|\mathbb {N} |$ besitzt. Außerdem hat Cantor im Satz von Cantor gezeigt, dass jede Potenzmenge $P(A)$ mächtiger als ihre zugrunde liegende Menge $A$ ist. Man kann zeigen, dass $|{\mathcal {P}}(\mathbb {N} )|=|\mathbb {R} |$ ist. Es stellt sich nun die Frage, ob es eine Menge gibt, die mächtiger als $\mathbb {N}$, aber weniger mächtig als $\mathbb {R}$ ist. Cantor vermutete, dass dies nicht der Fall ist, konnte seine Vermutung aber nicht beweisen. Diese Vermutung wird Kontinuumshypothese genannt. Es stellte sich jedoch heraus, dass diese Hypothese in der Mengenlehre mit den Axiomen von Zermelo-Fraenkel einschliesslich Auswahlaxiom weder beweisbar noch widerlegbar ist.