Why is the cardinal number of power set $2^n$? Why does the total no. of subsets of $n$ elements equal $2^n$?
I was taught that it is because each element has two choices either making a set or not. Thus giving $2×2×2\ldots$ subsets.
But I didn't understand how does it work in giving this result.
 A: Proof by induction.
When $n=0$ then $\mathcal P(\emptyset)=\{\emptyset\}$ so $|\mathcal P(\emptyset)|=1.$
Now, assume it is true for all $|S|=n,$ and assume $|T|=n+1.$
Pick one element $x\in T.$ Then let $T_0=T\setminus \{x\}.$ We have $|T_0|=n.$
Then for every $M\subseteq T_0$ there are exactly two subsets of $T,$ $M$ and $M\cup\{x\}.$
So $$|\mathcal P(T)|=2|\mathcal P(T_0)|=2\cdot 2^{n}=2^{n+1}.$$

We could be alightly more rigorously prove this by defining a function $f:\mathcal P(T)\to \mathcal P(T_0)\times \{1,2\}$ and prove it is a bijection.
We define, for $M\subseteq T,$ $$f_2(M)=\begin{cases}1&x\in M\\2&x\notin M
\end{cases}$$
Then $f(M)=(M\cap T_0,f_2(M)).$
Showing this is a bijection is tedious work, but direct.
A: Suppose you number the elements $1,2,\cdots,n$. Then each element of the power set can be represented by a binary string of length $n$: Namely, a subset of the $n$ elements, say $S$, will be denoted by the $n$-bit string $b(S)=(b_1(S),b_2(S),\cdots,b_n(S))$, where $b_i(S)=1$ if the $i$-th elements belongs to $S$, or $b_i(S)=0$, otherwise. Note that each subset corresponds to a unique $n$-bit string, and vice versa. Now the number of $n$-bit strings is $2^n$. Hence the number of subsets is also $2^n$.
