The total number of subsets is $2^n$ for $n$ elements

Solution 1:

enter image description here

"Include A?" is stage 1
"Include B?" is stage 2
"Include C?" is stage 3.

Solution 2:

Label your $n$ elements so that $X=\{x_{1},...,x_{n}\}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string $$a_{1}\cdots a_{n}$$ imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S=\{x_{1},x_{3}\}$ would be represented as $1010$.

There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.

Solution 3:

Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include): $$ \begin{array}{|c|c|} \text{decimal}&\text{binary}&\text{subset}\\\hline 0&000&\{\}\\ 1&001&\{C\}\\ 2&010&\{B\}\\ 3&011&\{B,C\}\\ 4&100&\{A\}\\ 5&101&\{A,C\}\\ 6&110&\{A,B\}\\ 7&111&\{A,B,C\}\\ \end{array} $$ This is easily extendible to an $n$ element set with $n$ digit binary numbers.

Solution 4:

I think, more directly, what the book is saying can be stated as:

Choosing a subset $U$ of a set $S$ is the same as, for each element $x\in S$, choosing whether $x$ is in $U$ or not.

In particular, there is, at any time, only one set we're considering. So, if $S=\{A,B,C\}$ and we want to choose a subset $U$, we could make the following three choices: $$A\in U$$ $$B\in U$$ $$C\in U$$ And we would get $U=\{A,B,C\}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead $$A\not\in U$$ $$B\not\in U$$ $$C\in U$$ And then get $U=\{C\}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.