## Assertion

The power set *P(M)* of a set *M* with *n* elements contains *2 ^{n}* elements.

## Proof

### base case: n = 0

The set which contains 0 elements is the empty set \(\emptyset = \{~\}\).

Its power set contains 1 element (1 = 2^{0}), namely the empty set: \(P(\emptyset) = \{\emptyset\} = \{\{~\}\}\).

### Iinductive step: A(n) => A(n+1)

Let \(M_{n+1}\) be a set with *n+1* elements. \(e_1,~e_2,~\dots~e_{n},~e_{n+1}\).

It hast the subset \( M_{n} \) with *n* elements \( e_1,~e_2,~\dots~e_{n} \).

\( P(M_{n}) \) has \( 2^n \) elements (assumption), namely the \( 2^n \) subsets of \( M_{n} \): \( T_{1},~T_{2},\dots~T_{2^n} \).

They are the subsets of \( M_{n} \) that implies that they are subsets of \( M_{n+1}\) so they are elements of \(P(M_{n+1})\).

Additionally contains \( P(M_{n+1}) \) the subsets ofon \( M_{n+1} \) that contain the element \( e_{n+1} \)

Those can be constructed by joining \( T_i \quad i\in\{1\dots 2^n\}\) with \( e_{n+1} \)

Each subset \( T_i \) adds one element: \( e_{n+1} \). \(T_i‘ = T_i \cup e_{n+1}\). The number of subsets doubles.

We have:

\( P(M_{n+1}) = \{T_{1},~T_{2},\dots~T_{2^n},~T_{1}‘,~T_{2}‘,\dots~T_{2^n}’\}\)

The power set has \( 2^n + 2^n = 2\cdot 2^n = 2^{n+1} \) elements.

*q.e.d.*