# Counting Subsets of a Finite Set

• Dec 13th 2010, 09:17 PM
mremwo
Counting Subsets of a Finite Set
Let B be a finite set.
Set m= |B|.

Prove that B has 2^m subsets.

Help?
• Dec 13th 2010, 09:27 PM
Drexel28
Quote:

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 $\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.
• Dec 13th 2010, 09:30 PM
snowtea
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.
• Dec 13th 2010, 09:38 PM
dwsmith
Irrelevant to the thread: I see you are from Tampa. Do you go to USF? I go to UT.
• Dec 13th 2010, 10:13 PM
mremwo
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
• Dec 13th 2010, 10:16 PM
mremwo
And to answer your question dwsmith, I don't go to school in Florida.