Die Potenzmenge ist die Menge aller Teilmengen einer gegebenen Grundmenge. Die Potenzmenge einer Menge enthält unter anderem immer die leere Menge und auch die Grundmenge selbst. Wir beweisen durch vollständige Induktion: Wenn die Grundmenge n Elemente hat, dann hat ihre Potenzmenge 2n Elemente.
Behauptung
Die Potenzmenge P(M) einer n-elementigen Menge M enthält genau 2n Elemente.
Beweis
Induktionsanfang: n=0
Die Menge mit 0 Elementen ist die leere Menge \(\emptyset = \{~\}\).
Ihre Potenzmenge enthält 1 Element (1 = 20), nämlich die leere Menge: \(P(\emptyset) = \{\emptyset\} = \{\{~\}\}\).
Induktionsschritt: A(n) => A(n+1)
Wir gehen davon aus, dass die Aussage für eine Menge mit n-Elementen richtig ist. Damit beweisen wir, dass die Aussage auch für eine Menge mit n+1-Elementen richtig ist.
Sei \(M_{n+1}\) eine Menge mit n+1 Elementen \(e_1,~e_2,~\dots~e_{n},~e_{n+1}\).
Diese hat die Teilmenge \( M_{n} \) mit den n Elementen \( e_1,~e_2,~\dots~e_{n} \).
\( P(M_{n}) \) hat nach Induktionsvoraussetzung \( 2^n \) Elemente, die \( 2^n \) Teilmengen von \( M_{n} \): \( T_{1},~T_{2},\dots~T_{2^n} \).
Diese sind als Teilmengen von \( M_{n} \) auch Teilmengen von \( M_{n+1}\) und damit Elemente von \(P(M_{n+1})\).
Zusätzlich enthält \( P(M_{n+1}) \) noch die Teilmengen von \( M_{n+1} \), die das Element \( e_{n+1} \) enthalten.
Diese kann man bilden, indem man die Mengen \( T_i \quad i\in\{1\dots 2^n\}\) mit \( e_{n+1} \) vereinigt.
Jeder Teilmenge \( T_i \) wird also ein Element hinzugefügt: \( e_{n+1} \). \(T_i‘ = T_i \cup e_{n+1}\). Damit verdoppelt sich die Anzahl der
Es gilt also:
\( P(M_{n+1}) = \{T_{1},~T_{2},\dots~T_{2^n},~T_{1}‘,~T_{2}‘,\dots~T_{2^n}’\}\)
Die Potenzmenge hat also \( 2^n + 2^n = 2\cdot 2^n = 2^{n+1} \) Elemente.
q.e.d.