A flawed proof by induction


by Rasalhague
Tags: flawed, induction, proof
Rasalhague
Rasalhague is offline
#1
Nov28-10, 09:08 AM
P: 1,400
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.

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 = {h1,...,hn+1}, S' = {h1,...,hn}, S'' = {h2,...,hn+1} are sets of horses. Sets S' and S'' each have one horse fewer than S. h2 is an element of S' and of S''. Therefore all horses in S will have the same colour, in particular the same colour as h2.

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 + 1 does not equal 2.
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
HallsofIvy
HallsofIvy is offline
#2
Nov28-10, 09:18 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,877
No, what is done their is perfectly legitimate. If you have, say, four objects, labeled a, b, c, and d, you are justified into breaking the set {a, b, c, d} into the union of {a, b, c} and {b, c, d} and that is all that is done. The indexing is completely irrelevant to the proof.
Rasalhague
Rasalhague is offline
#3
Nov28-10, 09:42 AM
P: 1,400
Is the inductive hypothesis here not only that all the horses in S' are the same colour as each other, but also that all the horses in S'' are the same colour as each other? I'm guessing so, since the sets are indexed just by the number of elements they have. Then what the inductive step has to show is that these statements imply that all the horses in S are the same colour as each other.

Landau
Landau is offline
#4
Nov28-10, 09:53 AM
Sci Advisor
P: 905

A flawed proof by induction


Quote Quote by Rasalhague View Post
Is the inductive hypothesis here not only that all the horses in S' are the same colour as each other, but also that all the horses in S'' are the same colour as each other?
Certainly. The proof goes by induction on the number, say n, of horses. First it is shown that for n=1 it holds. Then the inductive hypothesis is that it holds for some n, i.e. that any set of n horses has the same color. This is then applied to the sets S and S'', which are both sets of n horses.
Rasalhague
Rasalhague is offline
#5
Nov28-10, 10:08 AM
P: 1,400
Okay, I think I get it now. Thank to you both for your help.


Register to reply

Related Discussions
Proof by Induction Calculus & Beyond Homework 1
Proof by induction help. Calculus & Beyond Homework 1
Linear algebra, prove matrix inverse proof flawed Calculus & Beyond Homework 9
Proof by Induction Precalculus Mathematics Homework 3
Help with proof by induction Set Theory, Logic, Probability, Statistics 3