Beweisarchiv: Mengenlehre: Mächtigkeiten (Kardinalzahlen): Potenzmenge

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

[Bearbeiten] Mächtigkeit der Potenzmenge

[Bearbeiten] Voraussetzung

$A\$ sei eine beliebige Menge.

[Bearbeiten] Behauptung

$|A| < |\mathcal{P}(A)|$

[Bearbeiten] Beweis

Es sind die folgenden beiden Aussagen zu zeigen:

Es gibt eine Injektion $i: A \to \mathcal{P}(A)$
Es gibt keine Bijektion zwischen $A\$ und $\mathcal{P}(A)$

Zu 1. Die Zuordnung $i: a \mapsto \{a\}$ leistet das Verlangte.

Zu 2. Angenommen, irgendeine Abbildung $f: A \to \mathcal{P}(A)$ wäre surjektiv. Dies wird nun zum Widerspruch geführt, womit auch gezeigt ist, dass es keine Bijektion zwischen den beiden Mengen gibt.

Die Teilmenge $M\$ von $A\$ wird definiert als $M := \{a \in A \mid a \ \not\in \ f(a) \}$ . Da $f\$ als surjektiv angenommen wurde, hat $M\$ ein Urbild unter $f\$ , also ein Element $a \in A$ mit $f(a) = M\$ . Nun gilt: