At the end of this video lecture on the Principle of Induction, the teacher gives the following example of a flawed proof that misuses the principle.(adsbygoogle = window.adsbygoogle || []).push({});

Theorem. All horses are the same colour.

Proof. (By induction.)

Base case. In a set of one horse {h}, the principle clearly holds.

Inductive step. Suppose S = {h_{1},...,h_{n+1}}, S' = {h_{1},...,h_{n}}, S'' = {h_{2},...,h_{n+1}} are sets of horses. Sets S' and S'' each have one horse fewer than S. h_{2}is an element of S' and of S''. Therefore all horses in S will have the same colour, in particular the same colour as h_{2}.

End proof.

The explanation offered is that this proof fails because the inductive step assumes that n does not equal 2, and so isn't general enough.

Is there another flaw, namely that the proof treats S' and S'' as distinct sets of horses but has indexed them with the same natural number as each other? To use the principle of induction correctly, wouldn't we need to use distinct labels for distinct objects?

EDIT. Correction: It assumes n+ 1does not equal 2.

**Physics Forums - The Fusion of Science and Community**

# A flawed proof by induction

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

- Similar discussions for: A flawed proof by induction

Loading...

**Physics Forums - The Fusion of Science and Community**