Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove Power Set equation by Induction

  1. Jan 17, 2010 #1
    1. The problem statement, all variables and given/known data

    (a) Use induction to show that if n(A) = n then n(P(A)) = 2^n.

    n(A) is the cardinality of set A.
    P(A) is the power set of A.


    2. Relevant equations

    The answer is
    We apply induction to prove the claim.
    If n = 0 then A = null and in this case P(A) = {null}. Thus n(P(A)) = 1 = 2^0.
    As induction hypothesis, suppose that if n(A) = n then n(P(A)) = 2^n. Let B = {a1, a2, · · · , an, an+1}. Then P(B) consists of all subsets of {a1, a2, · · · , an} together with all subsets of
    {a1, a2, · · · , an} with the element an+1 added to them. Hence, n(P(B)) =
    2^n + 2^n = 2 · 2^n = 2^n+1.


    3. The attempt at a solution

    Can someone explain the step

    "Then P(B) consists of all subsets of {a1, a2, · · · , an} together with all subsets of {a1, a2, · · · , an} with the element an+1 added to them. "


    Why is this the case? Shouldn't P(B) just all the subsets {a1,a2,...,an,an+1)? So that's the power set of {a1,a2,...,an} plus something else, but what is that something else?

    The answer seems to say that the something else is all subsets of {a1, a2, · · · , an} with the element an+1 and that is equal to 2^n but why is that the case? How do we know that it is equal to 2^n?
     
  2. jcsd
  3. Jan 17, 2010 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Happyzor! :smile:

    (try using the X2 and X2 tags just above the Reply box :wink:)
    That's rather unclear.

    I'd prefer to say:

    P(B) consists of:
    i] all subsets of {a1, a2, · · · , an+1} which do include an+1
    plus
    ii] all subsets of {a1, a2, · · · , an+1} which don't include an+1.

    That's the same number as the number of:
    i] all subsets of {a1, a2, · · · , an}
    plus
    ii] all subsets of {a1, a2, · · · , an}. :wink:
     
  4. Jan 17, 2010 #3
    Why are they both equal to 2n? I understand why n*P({a1, a2, · · · , an}) is equal to 2n but why is the other one also 2n? Thanks for your help.
     
  5. Jan 17, 2010 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    the sets in i] all include an+1.

    So each set in i] is of the form (A U {an+1}) where A is a subset of {a1, a2, · · · , an}.

    Different sets in i] have different As, and every A corresponds to a set in i].

    ie there's a one-to-one correspondence between the sets in i] and P({a1, a2, · · · , an})

    ie they have the same number. :wink:
     
  6. Jan 17, 2010 #5
    Thanks for your help. I didn't really understand what you meant, but I got help from someone else. I really appreciate it!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook