Why Is It That the Number of Subsets of a Set $S$ (the Cardinality of the Power Set of $S$) Is $2^{|S|}$?

Question

Why is it that the number of subsets of a set $S$ (the cardinality of the power set of $S$) is $2^{|S|}$?

I suspect that there is some sort of combinatorial argument for this fact?

I would greatly appreciate it if people could please explain this.

Answer 1

Here is an argument with a "combinatorial flavor", which works for finite $\vert S \vert$:

We observe that the binomial theorem yields

$2^k = (1 + 1)^k = \displaystyle \sum_{r = 0}^k \dfrac{k!}{r! (k - r)!} 1^r 1^{k - r} = \sum_{r = 0}^k \dfrac{k!}{r! (k - r)!}; \tag 1$

but

$C^k_r = \dfrac{k!}{r! (k - r)!} \tag 2$

is precisely the number of combinations of $k$ things taken $r$ at at time; that is, the number of ways we may choose $r$ elements from a set $S$ with $\vert S \vert = k$, irrespective of order; thus it is the number of $r$-element subsets of $S$. It follows then that the sums occurring in (1) count all subsets of $S$, whence

$\vert P(S) \vert = \displaystyle \sum_{r = 0}^k \dfrac{k!}{r! (k - r)!} = 2^k = 2^{\vert S \vert}, \tag 3$

as per request.

Answer 2

We can construct any subset of $S$ by examining each element and deciding whether or not to put it in the subset. For each element we have two options: put it in the subset, or leave it out. Thus, there are $2^{|S|}$ options for subsets since $|S|$ is the number of elements we go through in our decision process.

Of course, we require $|S|<\infty$.

Answer 3

The reason is that a subset $A$ of $S$ can be identified with a function $f$ from $S$ to a two element set, say $\{0,1\}$, with $f(x)=0$ if $x\not\in A$ and $f(x)=1$ if $x\in A$...