Kategorien

# The power set of a set with n elements contains 2^n elements

## Assertion

The power set P(M) of a set M with n elements contains 2n elements.

## Proof

### base case: n = 0

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

Its power set contains 1 element (1 = 20), 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.