Actually, I have another question concerning power sets. My book says, "If a set has n elements, then its power set has 2^n elements." Why does this formula work?
okay the best way to thing of this is using a binary string of digits where each digit of the string represents an element of the set so I can encode the various subsets as strings of binary digis as follows:
000000 represents the nullset { }
100000 represents the first element {a}
010000 the 2nd { b }
001000 the 3rd... { c }
111000 a subset containing {a,b,c}
...
111111 the set itself { a,b,c,d,e,f }
so in creating a subset then
a is or isnt in the subset: 2 choices
b is or isnt in the subset : x 2 =4 choices
...
f is or isn't in the subset x 2 = 64 choices
or more succinctly:
a x b x c x d x e x f
2 x 2 x 2 x 2 x 2 x 2 = 2^6 = 64 possible subsets
Another proof, by induction. If set A has no elements, it is empty. The only subset of the empty set is the empty set itself so its power set contains only the empty set and so has 1= 2^{0} member.
Suppose that, for some number k, any set with k member has 2^{k} members. Let A be a set containing k+1 members. Since A is not empty, it contains at least one member. Pick a specific member and call it "x". Every subset of A contains x or not.
1) If subset B of A does not contain x, it is a subset of A\{x}. Since A contains k+1 members, A\{x} contains k and so has 2^{k} subsets. That is, there are 2^{k} subsets of A that do not include x.
2) If subset B contains x, then B\x does not and so is a subset of A\{x}. That is, eery subset containing x is just a subset that doesn't contain a, union {a}. Since there are 2^{k} such sets, there are also 2^{k} subsets of A that do contain x.
Therefore, there are 2^{k}+ 2^{k}= 2(2^{k})= 2^{k+1} subsets of A and we are done.