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!

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




Similar Discussions: Prove Power Set equation by Induction
  1. Proving by induction (Replies: 1)

  2. Prove by Induction (Replies: 2)

  3. Prove by induction (Replies: 5)

  4. Prove by Induction (Replies: 17)

Loading...