Cardinality of Power Set/Proof 2

Theorem

Let $S$ be a set such that:

$\left|{S}\right| = n$

where $\left|{S}\right|$ denotes the cardinality of $S$,

Then:

$\left|{\mathcal P \left({S}\right)}\right| = 2^n$

where $\mathcal P \left({S}\right)$ denotes the power set of $S$.

Proof

We can see that enumerating the subsets of $S$ is equivalent to counting all of the ways of selecting $k$ out of the $n$ elements of $S$ with $k = 0, 1, \ldots, n$.

So, from Cardinality of Set of Subsets, the number we are looking for is:

$\displaystyle \left|{\mathcal P \left({S}\right)}\right| = \sum_{k=0}^n \binom n k$

But from the binomial theorem:

$\displaystyle \left({x + y}\right)^n = \sum_{k=0}^n \binom n k x^{n-k} y^k$

It follows that:

$2^n = \displaystyle \left({1 + 1}\right)^n = \sum_{k=0}^n \binom n k \left({1}\right)^{n-k} \left({1}\right)^k = \sum_{k=0}^n \binom n k = \left|{\mathcal P \left({S}\right)}\right|$

$\blacksquare$

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 2.3$: Example $35$