1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Induction Axiom riddle

  1. Sep 9, 2008 #1
    1. The problem statement, all variables and given/known data

    The inductive hypothesis P(n): For any counting number n in N, and set of billiard balls with n members, all the balls have the same color.

    Consider any set A of n+1 balls, and the subsets
    B=(first n balls), C=(last n balls)

    The inductive hypothesis applies to both B and C, so all balls in B have the same color, and likewise for the balls in C. Since the 2 sets have a ball in common, all the balls in their union A=BUC have the same color, proving that P(n+1) is true. By the Induction Axiom, P(n) is true for all counting numbers n so all billiard balls have the same color.

    The conclusion is absurd. Can you spot the "error" in this proof?

    3. The attempt at a solution
    The end says that ALL billiard balls have the same color. But this is true only for the union, not the intersection, of B and C, so not ALL balls apply.
    You can have A'=B'UC'=empty set and still fulfill the requirement that all of B' is one color, and all of C' is one color, yet they are not the same color as each other.

    Is my "error" finding correct?
    Last edited: Sep 9, 2008
  2. jcsd
  3. Sep 9, 2008 #2


    User Avatar
    Science Advisor

    What do you mean by B' and C'? Complement of B and C? But you haven't declared a "universal set". I don't know what you mean by "the union, intersection of B and C". If you mean that in both the union and intersection all balls of the same color then the union IS "all balls".

    Suppose n= 5 so n+1= 6. A has 6 balls. B contains the first 5 of those balls and C contains the last 5. All of the balls in B have the same color and all the balls in C have the same color. But [itex]B\capC[/itex] consists of 4 balls that are in both B and C! What does that tell you about the "two" colors?

    Now suppose n= 1 so n+1= 2. A contains 2 Balls. B contains the first one and C contains the last one. What happens now?
  4. Sep 9, 2008 #3
    Sorry typo, I meant to write it refers only to "the union, NOT the intersection of B and C."

    So in your first case n=5, all the balls in B and C are the same color.

    In the second case n=1, B can be one color, and C can be one color.

    How do I explain this in "proof-language"?
  5. Sep 9, 2008 #4


    User Avatar
    Science Advisor

    I'm not sure what you mean by "proof-language". If n= 1 so that n+1= 2, set B and C are disjoint so the statement in the origina proof, "Since the 2 sets have a ball in common" is false. That's the error.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook