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

Mächtigkeit der Potenzmenge

Voraussetzung

$A$ sei eine beliebige Menge.

Behauptung

$|A|<|𝒫(A)|$

Beweis

Es sind die folgenden beiden Aussagen zu zeigen:

1. Es gibt eine Injektion $i:A\to 𝒫(A)$
2. Es gibt keine Bijektion zwischen $A$ und $𝒫(A)$

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

Zu 2. Angenommen, irgendeine Abbildung $f:A\to 𝒫(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\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:

$a\in M⟺a\in ̸f(a)⟺a\in ̸M$

(Die erste Äquivalenz beinhaltet die Definition von $M$, die zweite Äquivalenz benutzt nur die Urbildeigenschaft.)

Damit ist der gewünschte Widerspruch vorhanden.

Wikipedia-Verweise

Injektivität - Mächtigkeit - Potenzmenge - Surjektivität

---