Let B be a finite set.

Set m= |B|.

Prove that B has 2^m subsets.

Help?

Printable View

- Dec 13th 2010, 09:17 PMmremwoCounting 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 PMDrexel28
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 PMsnowtea
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 PMdwsmith
Irrelevant to the thread: I see you are from Tampa. Do you go to USF? I go to UT.

- Dec 13th 2010, 10:13 PMmremwo
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 PMmremwo
And to answer your question dwsmith, I don't go to school in Florida.