1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding The Power Set Of A Given Set

  1. Sep 28, 2012 #1
    1. The problem statement, all variables and given/known data
    {∅,{∅}}


    2. Relevant equations



    3. The attempt at a solution
    My answer is {∅, {{∅}}, {∅, {∅}}}
    but the actual answer is: {∅,{∅},{{∅}},{∅,{∅}}}
    I don't understand how the second element, {∅}, appears...
     
  2. jcsd
  3. Sep 28, 2012 #2

    jedishrfu

    Staff: 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 } }
     
  4. Sep 28, 2012 #3
    Okay, thank you.
     
  5. Sep 28, 2012 #4
    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?
     
  6. Sep 28, 2012 #5

    jedishrfu

    Staff: 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.
     
  7. Sep 28, 2012 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding The Power Set Of A Given Set
  1. Power set? (Replies: 4)

Loading...