1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

Even More Induction

  1. Jun 27, 2008 #1
    1. The problem statement, all variables and given/known data

    Show with induction that a set with n elements have 2n subsets.

    3. The attempt at a solution

    I assume this should only be for all natural numbers, but I cannot even show that it applies to n = 1. Let's say we have a set S = {x(1)}. That has 1 element, but only 1 subset, not 2? I'm confused. Have I missed something from basic set theory?
  2. jcsd
  3. Jun 27, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    It has two subsets. {x(1)} and the empty set {}.
  4. Jun 27, 2008 #3
    Of course. Thanks a bunch. Here is another go at it.

    3. The attempt at a solution

    (1) Show that it is true for n = 1:

    A set S contains the element x(1). S can form two subsets S' and S'', where S' = {x(1)} and S'' = {}.

    (2) Show that if it is true for n = p, then it is true for n = p + 1

    Assume that if a set P contain p elements, then 2p subsets can formed from it.

    P = {x(1), x(2),..., x(p)}
    Q = {x(1), x(2),..., x(p), x(p+1)}

    So P contains 2p subsets. Naturally, Q must contain 2p + C number of subsets, where C is a unknown constant. For (2) to be true 2p + C must be equal to 2p+1. This seems to mean that the power set P' contains 2p elements. So this means that I should attempt to figure out exactly how many elements are added to P' to form the power set Q' if you add an element to P? I'm not entire sure how to do this.
  5. Jun 27, 2008 #4


    User Avatar
    Homework Helper

    How many subsets are there that don't contain x(p+1)? (inductive hypothesis)

    then count how many have x(p+1) in it....add those two together.
  6. Jun 28, 2008 #5
    How many new possible subsets can you create, when you have one more element to pick?
  7. Jun 28, 2008 #6


    User Avatar
    Science Advisor

    Every subset of Q (with x(p+1) added) is of two kinds: those that do not have x(p+1) in them and those that do not. How many subsets of Q do NOT have x(p+1) in them (remember that those would also be subsets of P)?

    And every subset of Q that does contain x(p+1) is a subset of P union {x(p+1)}.
  8. Jun 28, 2008 #7
    That would be 2p?

    Too hard question.

    The first subset would be {x(p+1)}.
    Then we have the {x(n), x(p+1)} subsets, where n goes from 1 to p and so on with more elements added.

    I know no general principle or line of thought to answer your question.
  9. Jun 28, 2008 #8


    User Avatar
    Science Advisor
    Homework Helper

    Let be concrete here. Take P to be the set of {1,2,3...p}. Take Q to be the set of {1,2,3...p,p+1}. All of the subset of P are also subsets of Q. And there are 2^p of them by the inductive hypothesis. All of the subsets of P are also subsets of Q. The only new subsets consist of a subset S of P that contains also contains p+1. Right? So there are 2^p new subsets. What's 2^p+2^p?
  10. Jun 29, 2008 #9
    That's 2p+1, which proves that if it is true for n = p, it is also true for n = p+1. I understand that all subsets of P are also subsets of Q. However, I do not understand how the text in bold follows. How can you show how many more subsets can form when you add another element?
  11. Jun 29, 2008 #10


    User Avatar
    Science Advisor
    Homework Helper

    You have 2^p sets without that element. If you add that new element to each of the 2^p sets, you get 2^p additional sets. If you put them all together you get all sets made from p+1 elements. For a total of 2^(p+1).
  12. Jun 30, 2008 #11
    Of course. That makes sense. Thanks a bunch.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - More Induction Date
Prove sin(x)<x and more Aug 26, 2017
More to less quantity Nov 29, 2016
Some More Induction Jun 26, 2008
Even More Induction Jun 23, 2008
More Induction Jun 9, 2008