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: Please help understand the solution on Math Induction

  1. Aug 29, 2010 #1
    1. The problem statement, all variables and given/known data

    Please help me understand the given solution. Is there a simpler way of solving the problem?

    2. Relevant equations



    3. The attempt at a solution
     

    Attached Files:

    • pic.jpg
      pic.jpg
      File size:
      48.2 KB
      Views:
      136
  2. jcsd
  3. Aug 29, 2010 #2
    I am no expert but this is usually the proof given in most txtbooks.
    The proof is board, so which part do you not understand ?

    Do you know the definition of the power set ? Can you follow the logic of the proof or are you having trouble with the logic ?

    Please, elaborate on your difficulties.
     
    Last edited: Aug 29, 2010
  4. Aug 29, 2010 #3
    I don't follow logic....
     
  5. Aug 29, 2010 #4
    I don't blame you. The author has a not so friendly way of proving his proposition.

    Basically, what the author is trying to do is use induction to show the if a set, A, has n elements then p(A) has 2^n elements. This much I know you understand.

    The logic

    The author shows that for n=0 this holds
    The author uses the inductive hypothesis and assumes it holds for some K then, he tries to show it holds for K+1. This much I believe you understand.

    To accomplish his purpose the author does the following. He takes a set of K+1 elements. Lets call this set A.
    He then defines a set B like this
    B= A/{x} [ B has all the elements in A except x ( some x ) , therefore B has K elements ]

    We know by inductive hypothesis p(B) has 2^k elements, since B has K elements.

    We also know that if we take every subset of A it is either a subset of B or a set that contains the element x. Now we know there are two possible cases.

    Cases
    1) We have a subset of A that contains x
    2) We have a subset of A that does not contain x.

    We know that all subsets of B lie in A. We also know that the only thing that B is lacking is the element x.

    So from this we can "conclude" , based on the two cases, that for every subset of A there are two kinds; one that contains x and one that does not. p(B) is a collection of all subsets of A that do not have x . So this means there is a p(B*) which consist of every subset of A that contains x.

    Considering there are only two cases we can match up all the subsets that contain x and those that do not contain x.

    That is, we can form a bijection from p(B) to p(B*).

    From this we see that p(A) = 2p(B) = 2*2^k = 2^(k+1)


    Do you understand a little more ?
     
    Last edited: Aug 29, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook