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

Aus Wikibooks

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

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

Deskriptive Mengenlehre: Satz von Young

Rechenregeln für Mengenoperationen: Assoziativgesetze - Distributivgesetze - Differenzgesetze

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|$ .

[Bearbeiten] Satz

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

[Bearbeiten] 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\geq1} 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\geq1$ , 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.

Von „http://de.wikibooks.org/wiki/Beweisarchiv:_Mengenlehre:_M%C3%A4chtigkeiten_%28Kardinalzahlen%29:_Kardinalit%C3%A4t_und_Bijektionen“

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

Aus Wikibooks

[Bearbeiten] Satz

[Bearbeiten] Beweis

Ansichten

Persönliche Werkzeuge

Navigation

Mitmachen

Suche

Werkzeuge