Induction Axiom riddle

  • Thread starter fk378
  • Start date
  • #1
367
0

Homework Statement



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?



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:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
966

Homework Statement



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




The Attempt at a Solution


The end says that ALL billiard balls have the same color. But this is true only for the union, 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.
Also, by the way, the complement of B union the complement of C is NOT the complement of A.


Is my "error" finding correct?
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?
 
  • #3
367
0
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
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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.
 

Related Threads on Induction Axiom riddle

  • Last Post
Replies
5
Views
814
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
24
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
6
Views
3K
Top