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 I

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 II

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.

Sätze über endliche Mengen und Bijektionen

Für endliche Mengen gelten in Hinblick auf Bijektionen drei weitere Sätze, die für unendliche Mengen in analoger Weise NICHT gelten.

Allgemeine Voraussetzung

Es seien $A$ und $B$ endliche Mengen und $f\colon A\to B$ eine Abbildung.

Satz IIIa

Ist $f$ injektiv und gilt hinsichtlich der Mächtigkeiten $|A|\geq |B|$ , so ist $f$ sogar bijektiv und $|A|=|B|$.

Beweis

Es ist $A=\bigcup _{b\in f(A)}{f^{-1}(\{b\})}$ und dies ist eine disjunkte Vereinigung. Wegen der Injektivität besteht für jedes $b\in f(A)$ die Gleichung $|f^{-1}(\{b\})|=1$. Folglich gilt $|A|=\sum _{b\in f(A)}{1}=|f(A)|$.

Wäre nun $f$ nicht surjektiv, so hätte man ein $b\in B$ mit $f(A)\subseteq {B\setminus \{b\}}$ und folglich die Ungleichung $|A|\leq |B|-1$ und damit einen Widerspruch zur Voraussetzung.

Also hat man $f(A)=B$ und $|A|=|f(A)|=|B|$ und Satz IIIa ist bewiesen.

Satz IIIb

Ist $f$ surjektiv und gilt hinsichtlich der Mächtigkeiten $|A|\leq |B|$, so ist $f\$ sogar bijektiv und $|A|=|B|$.

Beweis

Wie zuvor hat man die disjunkte Vereinigung $A=\bigcup _{b\in f(A)}{f^{-1}(\{b\})}$.

Wegen der Surjektivität ist $f(A)=B$ und es besteht für jedes $b\in B$ die Ungleichung $|f^{-1}(\{b\})|\geq 1$. Folglich gilt $|A|=\sum _{b\in B}{|f^{-1}(\{b\})|}\geq |B|$.

Wäre nun f nicht injektiv, so hätte man für ein $b\in B$ sogar die Ungleichung $|f^{-1}(\{b\})|\geq 2$ und damit sogar $|A|>|B|$ und folglich einen Widerspruch zur Voraussetzung.

Also f sehr wohl injektiv und man hat wie zuvor $f(A)=B$ und $|A|=|f(A)|=|B|$ und Satz IIIb ist bewiesen.

Satz IIIc

Für jede endliche Menge $A$ und für jede Abbildung $f\colon A\to A$ sind Injektivität, Surjektivität und Bijektivität stets gleichwertige Eigenschaften.

Beweis

Dies ergibt sich als direkte Folgerung aus Satz IIIa und Satz IIIb. Satz IIIc ist damit bewiesen.