# Induction Axiom riddle

1. Sep 9, 2008

### fk378

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.

Pf)
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. Sep 9, 2008

### HallsofIvy

Staff Emeritus
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 $B\capC$ 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?

3. Sep 9, 2008

### fk378

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"?

4. Sep 9, 2008

### HallsofIvy

Staff Emeritus
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.