Here is a proposed proof for the statement “all cats have the same color”. We pr
ID: 3282436 • Letter: H
Question
Here is a proposed proof for the statement “all cats have the same color”. We proceed as follows: By induction on n we show that in any set of n cats, there are no two cats with a different color. Base step: A set consisting of one cat only clearly satisfies the claim. Inductive step: Suppose the theorem has been proven for all sets of n cats. Consider a set of n + 1 cats. Take one cat out of the set; call it “first cat”. By the inductive hypothesis, the rest of the cats (consisting of n cats), are of the same color, say color x. Take another cat away; call it “second cat”. Remember that the rest of the set has n ? 1 cats of color x. Now return the first cat to the set. The set has now n cats, n ? 1 of which are color x; the first cat has some unknown color. Since by inductive hypothesis a set of cats with n elements has just one color, the first cat must also have color x. Now bring the second cat back in, and we get back our set of n + 1 cats, all of which have color x. To summarize, we assumed any n cats were of color x, and we have proven that any n + 1 cats are of color x also.
Conclusion: By virtue of mathematical induction, all cats in the world are of the same color. Since this conclusion is obviously false, only three possibilities are available: the principle of mathematical induction is false or inapplicable to cats, logic is false or inapplicable to cats, or there is an error in the proof. Which one? Explain why!
Explanation / Answer
The error is in 'taking another cat away' at the step n+1 = 2.
When we take two cats away from a set of two cats, we end up with a set of zero cats. Color is not defined for a set of zero cats, since our base case is for a set of one cat. Hence induction fails: P(0) for the statement P(n) = "In a set of n cats, no two cats have the same color" is not defined to be true or false.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.