The total number of subsets is $2^n$ for $n$ elements In my probability book, it says that to count the total number of subsets of n elements is a process of $n$ stages with binary choice of either adding this element to the subset or not to add it. Therefore, the total number is
$$2^n$$
But, for instance, we have 3 elements, according to this formula, there are 2 to the power of 3 elements, namely 8, which are
$${\emptyset},A,B,C, AB, AC, BC, ABC$$
However, I have a hard time of imagining the process or N stages binary choice that form this many subsets. Can anyone explain/help me to understand it? I mean, ABC, if we are making the choice of A, put it in or do not put it in, exactly which subset are we choosing to put in or not? Thank you.
 A: 


*

*"Include A?" is stage 1

*"Include B?" is stage 2

*"Include C?" is stage 3.

A: 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.
A: 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.
A: The set of subsets of $X$ can be seen as the set of all functions from $X$ to $\{0,1\}$, denoted $\{0,1\}^X$.  
For each such function,  consider the subset of $X$ consisting of all $x\in X$ such that $f(x)=1$.
This, it turns out, is a $1-1$correspondence.  
As a result,  the order of the power set is $\mid P(X)\mid=\mid \{0,1\}^X\mid=\mid\{0,1\}\mid^{\mid X\mid}=2^n$.
A: Proof by induction (on number of elements in the set):
For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.
Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n \cup \{x\}$ (where $x \notin U_n$). Which subsets of $U_{n+1}$ exists?


*

*The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)

*Any other subset includes $x$, so it is of the form $A \cup \{x\}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A \subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.


So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.
A: 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.
