• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

All Horses Have The Same Color!

quantyst

quantyst

Joined
9/7/07
Messages
220
Points
28
[FONT=&quot]Do you agree with the following inductive proof? Clearly explain why or why not.[/FONT]


Theorem:[FONT=&quot] All horses have the same color.

[/FONT][FONT=&quot]PROOF: Let N denote the number of horses.
[/FONT]
Initial Case:
 [FONT=&quot]Clearly with just N=1 horse, all horses -- in this group of one horse -- have the same color.[/FONT]

[FONT=&quot]Inductive Step: [/FONT]
[FONT=&quot](It will be shown that: If it is true for any group of N horses (in which all have the same color), then it is also true for any group of N+1 horses).[/FONT][FONT=&quot] So, let's assume it is true for any group of N horses. Now, given any set of N+1 horses, if you remove a random horse, you get a set of N horses. By the inductive hypothesis, these N horses all have the same color. But by removing any other horse in the pack of N+1 horses, you can conclude that also in this new group of N horses, all have the same color. Since there are some horses common in both groups just considered, then both of the two removed horses must have the same color as the common horses. Therefore all N+1 horses have the same color. QED [/FONT]

[FONT=&quot]The last bit of reasoning goes like this. Let's be concrete, and suppose we assume the case is true when N=8. That is, we assume that in ANY group of 8 horses, they all have the same color. Now consider the case N+1=9. So, remove horse #1 from the group of 9 to get a group of 8 horses. By the inductive hypothesis, these 8 horses (i.e., horses #2 through #9) must all have the same color, let's say, color red. So, in particular, horse #6 has color red. Now, put horse #1 back in and this time remove horse #9. So, we have a (different) group of 8 horses. But by the inductive hypothesis, all these horses (i.e., horses #1 through #8) have the same color. More specifically, they all have the same color as horse #6, which has color red. So, horse #1 has color red, just like all the other 8 horses. So, all the 9 horses have the same color!
[/FONT]



WHAT IS WRONG WITH THE PROOF?

[FONT=&quot]Hint: Although the preceding concrete example is an accurate explanation of the reasoning, a superficial understanding of it is precisely where one is misled in thinking about the unsoundness of the 'proof'![/FONT]
 
Piece of cake. The inductive hypothesis breaks down when going from n=1 to n=2. Next.

(I prefer the proof of the theorem that a horse has an infinite number of legs.)
 
To bigbadwolf,

Of course!

But you should be good enough to give others a chance to ponder this for a while before you spill out the answer! Nonetheless, thanks for the answer!

This 'proof' serves as a good example of what happens when symbolism and formalism override the meaning behind the words.

Now, why don't you share with us the proof for the case in which a horse has infinitely many legs? I don't recall having heard it before.
 
When one come across some theorem, he should remember that this theorem is stated within some framework, which defines basic concepts and relations between them. We never can consider theorems separately from their framework.

This particular theorem can either holds or not holds depending on definition of the terms horse and, maybe, color. If we define 'horse' as usual species of particular type in whole their variety, then we immediately can find counter example for the statement of the theorem.

But, if one define 'horse' in some special way which will include only species of the same color, then theorem will holds either as an immediate consequence of definition or with different proof.
 
Theorem: A horse has an infinite number of legs.

Proof: A horse has hindlegs and it had forelegs, which makes six legs, which is surely an odd number of legs for a horse to have. But the only number that can be both odd and even is infinity and thus a horse has an infinite number of legs.

(Comment: this absurd proof has some profound lessons. The proof hings on the ambiguous meaning (or at least sound) of "fore" and "odd": they're being given two meanings, and a different one chosen for each purpose. And "infinity" is being treated as a number. So we have to be careful in proofs that we adhere to one clearly defined meaning.)
 
Hi Andriy,

You have shown important concerns.

However, the question is NOT about what is wrong with the theorem. The question is about what is wrong with the proof! I could have replaced the horses with mythical or arbitrarily defined creatures who -- everlastingly -- may all have had the same color. The proof would have still been deficient, anyway. Precisely because we already know that not all horses have the same color, the theorem grabs our attention psychologically. Anyway, bigbadwolf is correct and final in his/her response.
 
Back
Top