Die Potenzmenge einer n-elementigen Menge enthält 2^n 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)

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.

$$T_i‘ = T_i \cup e_{n+1}$$

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.

Weiterlesen: Rekursive Folge