Gfrktyl

• "Include A?" is stage 1


• "Include B?" is stage 2


• "Include C?" is stage 3.

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.

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.

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 $xin 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:
$$Ain U$$
$$Bin U$$
$$Cin 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
$$Anotin U$$
$$Bnotin U$$
$$Cin 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.

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 $xin 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}^Xmid=mid{0,1}mid^{mid Xmid}=2^n$.

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.