• Support PF! Buy your school textbooks, materials and every day products Here!

Finding The Power Set Of A Given Set

  • Thread starter Bashyboy
  • Start date
  • #1
1,421
5

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

Answers and Replies

  • #2
11,691
5,262
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 } }
 
  • #3
1,421
5
Okay, thank you.
 
  • #4
1,421
5
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?
 
  • #5
11,691
5,262
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.
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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.
 

Related Threads on Finding The Power Set Of A Given Set

Replies
2
Views
2K
Replies
0
Views
680
Replies
9
Views
6K
Replies
2
Views
741
Replies
1
Views
657
Replies
10
Views
844
  • Last Post
Replies
4
Views
678
Replies
2
Views
4K
Replies
3
Views
1K
Top