# Finding The Power Set Of A Given Set

{∅,{∅}}

## The Attempt at a Solution

My answer is {∅, {{∅}}, {∅, {∅}}}
but the actual answer is: {∅,{∅},{{∅}},{∅,{∅}}}
I don't understand how the second element, {∅}, appears...

jedishrfu
Mentor
your set { a, b } so the power set has all proper subsets including the null set and the set itself:

{ nullset, {a}, {b}, {a,b} }

and in your example then the { a } corresponds to the { nullset } and the { b } corresponds to { { nullset } }

Okay, thank you.

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?

jedishrfu
Mentor
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

and therefore the powerset contains 64 elements.

HallsofIvy
Homework Helper
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= 20 member.

Suppose that, for some number k, any set with k member has 2k 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 2k subsets. That is, there are 2k 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 2k such sets, there are also 2k subsets of A that do contain x.

Therefore, there are 2k+ 2k= 2(2k)= 2k+1 subsets of A and we are done.