Finding The Power Set Of A Given Set

[Bashyboy]

Homework Statement

{∅,{∅}}

Homework Equations

The Attempt at a Solution

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

 

[jedishrfu]

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

 

[Bashyboy]

Okay, thank you.

 

[Bashyboy]

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]

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 isn't in the subset: 2 choices
b is or isn't 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]

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⁰ 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.