Problem 2 - A Gentle Introduction to the Art of Mathematics

Question

What is wrong with the following inductive proof of "all horses are the same color."? Theorem Let \(H\) be a set of \(n\) horses, all horses in \(H\) are the same color. Proof: We proceed by induction on \(n\). Basis: Suppose \(H\) is a set containing 1 horse. Clearly this horse is the same color as itself. Given a set of \(k+1\) horses \(H\) we can construct two sets of \(k\) horses. Suppose \(H=\left\\{h_{1}, h_{2}, h_{3}, \ldots h_{k+1}\right\\}\). Define \(H_{a}=\left\\{h_{1}, h_{2}, h_{3}, \ldots h_{k}\right\\}\) (i.e. \(H_{a}\) contains just the first \(k\) horses ) and \(H_{b}=\left\\{h_{2}, h_{3}, h_{4}, \ldots h_{k+1}\right\\}\) (i.e. \(H_{b}\) contains the last \(k\) horses). By the inductive hypothesis both these sets contain horses that are "all the same color." Also, all the horses from \(h_{2}\) to \(h_{k}\) are in both sets so both \(H_{a}\) and \(H_{b}\) con- tain only horses of this (same) color. Finally, we conclude that all the horses in \(H\) are the same color.

Step-by-Step Solution

Answer

The flaw is in the transition from k=1 to k+1=2, where the sets do not overlap.

Step 1: Understand the Basis

The basis of the proof considers a set containing just one horse. In this case, it is trivially true that the horse is of the same color as itself. Thus, the base case is valid.

Step 2: Consider the Inductive Step

The inductive step involves assuming that any set of k horses are the same color, and attempting to prove it for k+1 horses. Here, the set H = {h1, h2, ..., hk+1} is divided into two overlapping subsets: Ha = {h1, h2, ..., hk} and Hb = {h2, h3, ..., hk+1}.

Step 3: Analyze the Subsets

According to the inductive hypothesis, the horses in each subset Ha and Hb are the same color. Since both sets overlap from h2 to hk, the horses h1 to hk and h2 to hk+1 should all be the same color, hence all horses in H should be the same color.

Step 4: Identify the Flaw

However, the problem arises when transitioning from k = 1 to k+1 = 2 horses. For k=1, we show that a single horse is trivially the same color as itself. But when we increase to k+1=2, consider the sets Ha={h1} and Hb={h2}. These sets no longer overlap and hence do not provide any information about the color of each other's horses.

Step 5: Conclusion

Thus, the key flaw in the inductive step is that it does not hold for the transition from k=1 to k+1=2 horses because the overlapping condition does not apply. Therefore, the proof does not show that all horses are the same color.

Key Concepts

incorrect proof by induction

A proof by induction often follows these steps: a base case, where we prove the statement for a particular initial value (usually 1), and an inductive step, where we assume the statement for a given number n and prove it for n+1. The incorrect proof in the given example fails during the inductive step.

Specifically, when trying to prove that any set of n+1 horses are the same color, the argument breaks down when transitioning from n=1 to n+1=2 horses. The sets of horses considered don't overlap adequately to provide the necessary color information. This logic leap is an essential mistake, rendering the entire proof flawed.

mathematical induction

Mathematical induction is a powerful proof technique primarily used to prove statements for all natural numbers. It consists of two main steps: the base case and the inductive step.

• Base case: Prove the statement for the initial value, often n=1.
• Inductive step: Assume the statement holds for some arbitrary natural number k, then prove it for k+1.

If both steps are successfully completed, the statement is proven true for all natural numbers. The essence of induction hinges on the assumption to generalize the proof from n=k to n=k+1, and ensuring that this leap is logically valid.

logical fallacy in proofs

Logical fallacies often undermine mathematical proofs by introducing errors in reasoning. A logical fallacy in an inductive proof, such as the one illustrated in the 'all horses are the same color' problem, can invalidate the entire proof.

Common logical fallacies include:

• Begging the question: Assuming what you're trying to prove.
• False assumption: Making an incorrect assumption at any step of the proof.
• Invalid inductive step: Incorrectly making the jump from n to n+1.

The mentioned proof attempts to establish an inductive step that doesn’t hold for the transition from 1 to 2 horses due to lack of sufficient overlap in the subsets considered. Recognizing and correcting these logical missteps is crucial for constructing valid proofs.