Beweisarchiv: Mengenlehre: Mächtigkeiten (Kardinalzahlen): lineare Ordnung

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$ und $B$ zwei Mengen, so schreiben wir $|A|\leq|B|$ genau dann, wenn es eine injektive Abbildung $f\colon A\to B$ gibt. Im folgenden wird gezeigt, dass diese Relation die Axiome einer linearen Ordnung erfüllt.

Hierdurch wird es sinnvoll, $| A | = | B |$ als $|A|\leq|B|\and|B|\leq|A|$ sowie $| A | < | B |$ als $|A|\leq|B|\and\neg(|B|\leq|A|)$ zu definieren.

[Bearbeiten] Reflexivität

[Bearbeiten] Voraussetzung

Sei $A$ eine beliebige Menge.

[Bearbeiten] Behauptung

$|A|\leq|A|$ .

[Bearbeiten] Beweis

Die identische Abbildung $id\colon A\to A$ ist injektiv.

[Bearbeiten] Transitivität

[Bearbeiten] Voraussetzung

Seien $A, B, C$ Mengen mit $|A|\leq|B|$ und $|B|\leq|C|$ .

[Bearbeiten] Behauptung

$|A|\leq|C|$ .

[Bearbeiten] Beweis

Nach Voraussetzung gibt es injektive Abbildungen $f\colon A\to B$ und $g\colon B\to C$ . Da die Komposition injektiver Abbildungen injektiv ist, leistet $g\circ f\colon A\to C$ das Gewünschte.

[Bearbeiten] Totalität

[Bearbeiten] Voraussetzung

Seien $A, B$ zwei Mengen.

[Bearbeiten] Behauptung

$|A|\leq|B|$ oder $|B|\leq|A|$ .

[Bearbeiten] Beweis

Dieser Beweis erfordert das Auswahlaxiom, hier in Form des Lemmas von Zorn.

Sei $T$ die Menge aller Paare $(X, f)$ mit $X\subseteq A$ und $f\colon X\to B$ injektiv. Wir definieren auf $T$ eine Relation $\leq$ indem wir $(X,f)\leq(Y,g)$ genau dann setzen, wenn $X\subseteq Y$ und $g | X = f$ gilt.

Diese Relation ist offensichtlich reflexiv und transitiv.

Sei $K\subset T$ eine linear geeordnete Teilmenge von $T$ . Sei $M:=\bigcup_{(X,f)\in K} X$ . Definiere $m\colon M\to B$ wie folgt: Für $x\in M$ wähle $(X,f)\in K$ mit $x\in X$ und setze $m (x) = f (x)$ . Dies ist wohldefiniert, denn falls auch $(Y,g)\in K$ mit $x\in Y$ gilt, folgt $f (x) = g (x)$ , da ja $g | X = f$ oder $f | Y = g$ gilt. Die so definiert Abbildung $m\colon M\to B$ ist injektiv, denn aus $m (x 1) = m (x 2)$ folgt für geeignete $(X_1,f_1),(X_2,f_2)\in K$ , dass $f 1 (x 1) = m (x 1) = m (x 2) = f 2 (x 2)$ gilt. Gilt jetzt $X_1\subseteq X_2$ , so folgt $f 2 (x 1) = f 1 (x 1) = f 2 (x 2)$ , also $x 1 = x 2$ . Der Fall $X_2\subseteq X_1$ geht analog. Folglich ist $(M,m)\in T$ und eine obere Schranke für $K$ .

Nach dem Lemma von Zorn enthält $T$ folglich ein maximales Element $(Z, h)$ .

Falls $h$ surjektiv ist, so ist $h\colon Z\to B$ bijektiv und die Umkehrabbildung hiervon eine injektive Abbildung von $B$ nach $A$ , d.h. es gilt $|B|\leq|A|$ .

Ist dagegen $h$ nicht surjektiv, so gibt es ein $b\in B\setminus h(Z)$ . Wäre jetzt $Z\neq A$ , d.h. gabe es ein $a\in A\setminus Z$ , so ließe sich $h$ durch $h (a): = b$ auf $Z\cup\{a\}$ fortsetzen im Widerspruch zur Maximalität von $(Z, h)$ . Folglich ist $Z = A$ und $h$ eine injektive Abbildung von $A$ nach $B$ , d.h. $|A|\leq|B|$ .