Mächtigkeit von Potenzmengen

Satz:

Sei $M$ eine endliche Menge mit $n$ Elementen. Dann gilt:
$|\mathcal{P}(M)|=2^n$

Beweis

mit vollständige Induktion

Induktionsanfang $n=0$
$|\mathcal{P}(\varnothing )|=|\{\varnothing \}|=1=2^0$
Induktionschrintt: Für $n\ge 0$ und $|M|=n$ gelte
$|\mathcal{P}(M)|=2^n$
Zu zeigen ist nun, dass für alle $|M|=n+1$ gilt:
$|\mathcal{P}(M)|=2^{n+1}$

Sei also $M=\{m_1,m_2,...,m_n,m_{n+1}\}$ und $A\subseteq M$
Wir unterscheiden in zei Fälle:

1. $m_{n+1}\notin A$ d.h. $A\subseteq \{m_1,...,m_n\}$ Nach IndVor gibt es $2^n$ solcher Mengen.
2. $m_{n+1}\in A$ d.h. $A\backslash \{m_{n+1}\}\subseteq \{m_1,...,m_n\}$ Nach IndVor gibt es ebenso $2^n$solcher Teilmengen.

Insgesamt $2^n+2^n=2^{n+1}$ Teilmengen von $M$.

siehe:
Potenzmenge
Kardinaltät