Beweisarchiv: Mengenlehre: Mächtigkeiten (Kardinalzahlen): Kardinalität und Bijektionen

Beweisarchiv: Mengenlehre

Charakteristikum unendlicher Mengen

Injektivität Surjektivität Bijektivität: Faktoren · Komposition · Linksinverse · Linkskürzbarkeit · Rechtsinverse · Rechtskürzbarkeit

Verkettungen: Assoziativgesetz der Hintereinanderausführung

Mächtigkeiten (Kardinalzahlen): lineare Ordnung · Kardinalität und Bijektionen · Potenzmenge

Deskriptive Mengenlehre: Satz von Young

Rechenregeln für Mengenoperationen: Assoziativgesetze · Distributivgesetze · Differenzgesetze · Grundeigenschaften der Inklusion · De Morgansche Regeln für Mengen · Bild und Urbild

Ordinalzahlen: Ordinalzahlen enthalten sich nicht selbst als Element · Elemente von Ordinalzahlen sind Ordinalzahlen · Durchschnitte von Ordinalzahlen sind Ordinalzahlen · Wohlordnung der Klasse aller Ordinalzahlen · Ordinalzahlen bilden eine echte Klasse · Der Nachfolger einer Ordinalzahl ist Ordinalzahl · Vereinigungen von Ordinalzahlen sind Ordinalzahlen · Limes- und Nachfolgerzahlen · Äquivalenz verschiedener Definitionen

Sätze die in ZF Äquivalent zum Auswahlaxiom sind: Alternative Darstellung des Auswahlaxioms · Wohlordnungssatz · Lemma von Zorn

Sind $A,B$ Mengen, so schreiben wir $|A|\leq |B|$, falls es eine injektive Abbildung $f\colon A\to B$ gibt. Wir schreiben $|A|=|B|$ bzw. sagen, dass $A$ und $B$ gleichmächtig sind, falls $|A|\leq |B|$ und $|B|\leq |A|$.

Satz

Zwei Mengen $A,B$ sind genau dann gleichmächtig, wenn es eine Bijektion $h\colon A\to B$ gibt.

Beweis

Falls es eine Bijektion $h\colon A\to B$ gibt, ist klar, dass $|A|=|B|$ gilt, da sowohl die Abbildung $h$ als auch deren Umkehrung injektiv ist.

Es gelte jetzt $|A|=|B|$, und zwar seien $f\colon A\to B$ und $g\colon B\to A$ injektiv. Wir definieren jetzt eine Abbildung $h\colon A\to B$ wie folgt: Sei $A_{1}=A\setminus g(B)$ und dann rekursiv $A_{n+1}=g(f(A_{n}))$. Sei $C=\bigcup _{n\geq 1}A_{n}$.

• Ist $a\in C$, so setze $h(a)=f(a)$.
• Ist $a\not \in C$, so folgt insbesondere $a\in g(B)$, wir können somit $h(a)=g^{-1}(a)$ setzen.

Diese Abbildung $h$ ist injektiv: Es gelte $h(a_{1})=h(a_{2})$ für zwei Elemente $a_{1},a_{2}\in A$.

• Ist $a_{1}\in C$ und $a_{2}\not \in C$, so ergibt sich mit $a_{2}=g(h(a_{2}))=g(h(a_{1}))=g(f(a_{1}))\in A_{n+1}$ ein Widerspruch.
• Der Fall $a_{2}\in C$ und $a_{1}\not \in C$ ist ebenso ausgeschlossen.
• Ist $a_{1}\in C$ und $a_{2}\in C$, so folgt $f(a_{1})=h(a_{1})=h(a_{2})=f(a_{2})$, also $a_{1}=a_{2}$.
• Ist weder $a_{1}\not \in C$ und $a_{2}\not \in C$, so folgt $a_{1}=g(h(a_{1}))=g(h(a_{2}))=a_{2}$.

Die Abbildung ist aber auch surjektiv: Sei $b\in B$ beliebig.

• Ist $g(b)\in A_{n}$ für ein $n\geq 1$, so folgt nach Definition von $A_{1}$, dass sogar $n>1$ gilt. Folglich ist $g(b)=g(f(a))$ für ein $a\in A_{n-1}$ und $h(a)=f(a)=b$.
• Ansonsten gilt $h(g(b))=g^{-1}(g(b))=b$.

Folglich ist $h\colon A\to B$ eine Bijektion.

Satz

Sei $A\subseteq B$ so gilt, dass $|A|\leq |B|$

Beweis

Für den Fall, dass $A=\emptyset$ ist die Aussage trivial, also betrachten wir nur den Fall, dass $A\not =\emptyset$.

Da $A\not =\emptyset \Rightarrow \exists x\in A$. Bilde nun eine Abbildung

$f:B\rightarrow A,\quad b\mapsto {\begin{cases}b&\quad b\in A\\x&\quad b\notin A\end{cases}}$

Da $f$ surjektiv ist folgt die Behauptung.