Let B be a finite set.
Set m= |B|.
Prove that B has 2^m subsets.
Help?
There are like forty different ways to do this. Three approaches:
1) Let $\displaystyle [k]=\{1,\cdots,k\}$. Show that $\displaystyle 2^{[k+1]}$ can be partitioned into two blocks, the elements of $\displaystyle 2^{[k]}$ and the elements of $\displaystyle 2^{[k]}$ united with $\displaystyle \{n+1\}$. Conclude that if $\displaystyle a_n=\#\left(2^{[n]}\right)$ then $\displaystyle a_{n+1}=2a_n$.
2) Note that $\displaystyle \displaystyle \#\left(2^{[n]}\right)=\sum_{k=0}^{n}{n\choose k}$ (why?)
3) Show that $\displaystyle \#\left(2^{[n]}\right)=\#\left(\{0,1\}^n\right)$ by showing that $\displaystyle f:2^{[n]}\to\{0,1\}^n$ by mapping $\displaystyle E\subseteq[n]$ to $\displaystyle \mathbf{1}_{E}$ (the indicator function) is a bijection.
A subset picks elements from B.
Think about how we form a subset of B. For each element of B, we can either put it in the subset or leave it out.
So for each element there are 2 possibilities (in the subset / not in the subset)
There are m elements, this gives 2*2*2*..[m times]...*2 possibilities, or just 2^m possible subsets.