# Thread: Counting Subsets of a Finite Set

1. ## Counting Subsets of a Finite Set

Let B be a finite set.
Set m= |B|.

Prove that B has 2^m subsets.

Help?

2. Originally Posted by mremwo
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 $[k]=\{1,\cdots,k\}$. Show that $2^{[k+1]}$ can be partitioned into two blocks, the elements of $2^{[k]}$ and the elements of $2^{[k]}$ united with $\{n+1\}$. Conclude that if $a_n=\#\left(2^{[n]}\right)$ then $a_{n+1}=2a_n$.

2) Note that $\displaystyle \#\left(2^{[n]}\right)=\sum_{k=0}^{n}{n\choose k}$ (why?)

3) Show that $\#\left(2^{[n]}\right)=\#\left(\{0,1\}^n\right)$ by showing that $f:2^{[n]}\to\{0,1\}^n$ by mapping $E\subseteq[n]$ to $\mathbf{1}_{E}$ (the indicator function) is a bijection.

3. 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.

4. Irrelevant to the thread: I see you are from Tampa. Do you go to USF? I go to UT.

5. i actually liked his response. really helped me think about in terms that make sense. any comment that makes me feel stupid for not realizing it before is always helpful. thanks snowtea

6. And to answer your question dwsmith, I don't go to school in Florida.