Let B be a finite set.
Set m= |B|.
Prove that B has 2^m subsets.
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.
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.