Let B be a finite set.

Set m= |B|.

Prove that B has 2^m subsets.

Help?

Printable View

- December 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? - December 13th 2010, 09:27 PMDrexel28
There are like forty different ways to do this. Three approaches:

1) Let . Show that can be partitioned into two blocks, the elements of and the elements of united with . Conclude that if then .

2) Note that (why?)

3) Show that by showing that by mapping to (the indicator function) is a bijection. - December 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. - December 13th 2010, 09:38 PMdwsmith
Irrelevant to the thread: I see you are from Tampa. Do you go to USF? I go to UT.

- December 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

- December 13th 2010, 10:16 PMmremwo
And to answer your question dwsmith, I don't go to school in Florida.