5
$\begingroup$

This question already has an answer here:

Upon reading of All horses have the same color "paradox", I began to wonder a couple of things.

First of all, to me the inductive step seems flawed. Just because I have $n$ white horses, does not mean that the $n+1$ will be white, too.

The only explanation to make the inductive step work seems to me that the actual statement we are assuming as base case it's not "there are at least $n$ horses of the same color", but rather "$P(n)$ = any grouping of $n$ horses is such all the horses in that grouping have the same color".

Now this makes the inductive step works, but it's completely useless, as $P(2)$ already implies that all the horses have the same color.

And of course the base case $P(2)$ is not true because it's equivalent to our problem. Setting to prove $P(2)$ is the same as proving that all horses have the same color.

So I can't understand why this has been considered a "false" proof by induction; either the inductive step does not work or it's completely useless.

The wikipedia page linked before explains the problem as

The problem in the argument is the assumption that because each of these two sets contains only one color of horses, the original set also contained only one color of horses. Because there are no common elements (horses) in the two sets, it is unknown whether the two horses share the same color.

Which does not make any sense to me.. It's like looking at the finger instead that at the moon.

Is there something wrong with my understanding of induction?

Edit

Admittedly, the base case is $P(1)$ and not $P(2)$. But the point holds;the only implication we need is $P(1) \implies P(2)$. All the subsequent implications are useless; a proof of this type is seldom called a proof by "induction". Otherwise all proofs are by induction! :)

What is even the point of establishing what $P(n)$ is? Just prove $P(2)$ and use as known fact $P(1)$ as you would do with any other known fact.

Edit 2

Since there has been some confusion about what I asked, I'll explain my thought process:

1) Begin reading the proof. Imagine that the statement is "P(n) = at least n horses have the same color", and if by induction on $n$ this hold for every $n$, then QED.

2) Realize the inductive step does not work

3) Understand that the proposition to be proved has been (silently) changed and now it's "P(n) = any grouping of $n$ horses is such all the horses in that grouping have the same color"."

4) Realize that $P(2)$ is what we want to prove.

5) Wonder why on earth we are trying to show $P(n)$ for $n > 2$. Induction proof usually works because the final statement to be proved come from the fact that it works for all $n$. Here $n=2$ suffice, so it is really odd.

6) Starting to think I've missed something here. But hey, it's a false proof, let's see what was wrong.

7) Turns out that the outline of the proof is fine but here's the catch: of all the implications $P(1) \implies P(2)$ is not valid hence the whole $P(n)$ cannot be valid.

8) Thinking (again) that this seems weird. Wonder if I've missed something .

By extended discussion it turns out that my understanding of induction was right. This lead me to believe that is is a bad example because it "seems" like a proof by induction but really some essential elements are not present. It's not that is wrong (apart from the failed implication), is that it gives a very bad idea of what a proof by induction is

$\endgroup$

marked as duplicate by apnorton, dustin, user147263, Shuchang, Jonas Meyer Mar 10 '15 at 1:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ As far as I can tell, you're correctly understanding the flaw in the induction; from a formal angle, it is trivially false, but viewed intuitively it can be misleading. $\endgroup$ – Laertes Mar 9 '15 at 17:51
  • $\begingroup$ The base case is $P(1)$ (which is trivially true), not $P(2)$ (which is false). $\endgroup$ – Yves Daoust Mar 9 '15 at 17:57
  • $\begingroup$ @YvesDaoust right. I edited $\endgroup$ – Ant Mar 9 '15 at 18:00
  • $\begingroup$ Isn't the whole point of induction that if induction is true then $P(m) \implies P(n)$ for $n \geq m$? To formally use $P(2)$ and get $P(n)$ you would have to set up the induction, and it sound like you are assuming a statement about transitivity that you would prove with induction (albeit a fairly easy induction). $\endgroup$ – Paul Plummer Mar 9 '15 at 18:50
  • 4
    $\begingroup$ It's more of a joke than a well-chosen flawed proof example. Taken as a cautionary tale instead of as a joke, its point is not to assume $n$ is large when performing induction. You can make it a bit clearer than Wikipedia did: All horses have the same color. Proof: We show that for any finite set of horses all horses in that set have the same color, which implies the result. Work by induction on the size of the finite set. Base case (n=1): ... (obviously P(2) would be sufficient, but at least this way of writing has the form of a proof of the result; a flawed proof must obfuscate something). $\endgroup$ – aes Mar 9 '15 at 19:17
15
$\begingroup$

The flaw lies in the sentence "the first horse in the group is of the same color as the horses in the middle, who in turn are of the same color as the last horse".

When $n=2$, this does not apply as there are no horses "in the middle", hence the "first" and "last" horses needn't be of the same color.

So $P(1)$ holds, and $P(n)$ does imply $P(n+1)$, but provided $n>2$: this suffices to ruin the argument.

$\endgroup$
  • $\begingroup$ my point is that the only implication you need is $P(1) \implies P(2)$, as all the other $P(n)$ should not even been considered as they are superfluos. And of course a single implication is seldom considered a proof by induction! $\endgroup$ – Ant Mar 9 '15 at 17:56
  • $\begingroup$ The theorem we are trying to prove is not "all grouping of $n$ horses have the same color" but rather "all horses have the same color" which is trivially equivalent to $P(2)$ and we don't need $P(n)$ for $n > 2$.. right? $\endgroup$ – Ant Mar 9 '15 at 18:00
  • 1
    $\begingroup$ More abstractly, if you have a set $X$ with an equivalence relation $\sim$, and you know that for any two elements $x$ and $y$ that $x \sim y$ (which is $P(2)$ here), you do not need induction to show that there is only one equivalence class. ie, you don't need to prove $P(n)$. $\endgroup$ – Alex Zorn Mar 9 '15 at 18:05
  • 3
    $\begingroup$ @Ant You don't need induction to prove $P(2)\Rightarrow P(n)$, but you can prove it using induction. The fact that it is an easy statement to prove has nothing to do with the fact that the proof given is a proof by induction. $\endgroup$ – Qidi Mar 9 '15 at 18:38
  • 4
    $\begingroup$ @Ant The point of this proof is not to demonstrate how induction works, but to demonstrate how subtle errors could occur in a proof by induction. Also I won't say it tried to "obfuscate" the $P(1) \Rightarrow P(2)$ part. It simply assumed a false statement(existence of "in the middle" horses). The point of this proof is exactly to tell people to be careful about making such subtle assumptions, since it could lead to a devastating error. $\endgroup$ – Qidi Mar 9 '15 at 18:55
7
$\begingroup$

Yes, proving $P(2)$ is good enough and you don't really need induction. The trouble is that $P(2)$ is false. The induction argument is there to obfuscate this fact by referring to a generic $n$ and hoping the reader doesn't notice that the general argument fails for $n=2$. That's why it's a false proof by induction.

$\endgroup$
  • $\begingroup$ Uhm I see, maybe it was to obfuscate the reader. Nonetheless I think it is a terrible example of proof by induction (I got confused for a while when I read it because I couldn't understand what exactly induction had anything to do with it) $\endgroup$ – Ant Mar 9 '15 at 18:39
  • $\begingroup$ @Ant Of course, once you realize that $P(2)$ is false (which some people see right away without being told), the "proof" is clearly a terrible example of a proof by induction. That's one purpose of the exercise, in my opinion: to warn people against this way of writing terrible proofs. Another purpose, of course, is to amuse us. $\endgroup$ – David K May 15 '17 at 13:14
1
$\begingroup$

It is very common that false proofs by induction involve a faulty base case, so a way to unravel the argument is to use the base case on the inductive step and see if the argument makes sense for that case.

First, exclude the last horse and look only at the first n horses; all these are the same color since n horses always are the same color. Likewise, exclude the first horse and look only at the last n horses. These too, must also be of the same color. Therefore, the first horse in the group is of the same color as the horses in the middle, who in turn are of the same color as the last horse. Hence the first horse, middle horses, and last horse are all of the same color, and we have proven that:

So the base case is $n=1$, and $n+1 = 2$.

It is true that the first horse has the same color as the first and the second horse has the same color as the second. But the problem is that when the argument refers to the "horses in the middle," there are no such horses for $n=2$. You just have the first horse and the last horse. This is where the argument fails.

$\endgroup$
  • $\begingroup$ Yes, that is true :) However, that is not what I asked. Please see last edit of the question! $\endgroup$ – Ant Mar 9 '15 at 19:34
  • $\begingroup$ @Ant I have trouble understanding what your confusion is. The induction does not work because we need a base case of $P(2)$ for the inductive step, but $P(2)$ is, of course, not necessarily true. $\endgroup$ – user99185 Mar 9 '15 at 20:41
  • $\begingroup$ @user99185 From what I gather Ant does not have a problem understanding why its a false induction proof just that Ant doesn't think its a good example of induction because it doesn't feel like induction, and I guess that is because if $P(2)$ is true then $P(2) \implies P(n)$ (which I try to explain that is what induction is and that Ants "proof" is really just a rewording leaving induction to the reader) $\endgroup$ – Paul Plummer Mar 9 '15 at 20:53
  • $\begingroup$ @PaulPlummer OK. I leave this task to you. $\endgroup$ – user99185 Mar 9 '15 at 21:19
1
$\begingroup$

Isn't the whole point of induction that if induction is true then $P(m) \implies P(n)$ for $n \geq m$? To formally use $P(2)$ and get $P(n)$ you would have to set up the induction, and it sound like you are assuming a statement about transitivity that you would prove with induction (albeit a fairly easy induction).

You seem to think that this is a bad or faulty example of induction because $P(2) \implies P(n)$ so proving $P(2)$ is sufficient, but think if $P(2) \not\implies P(n)$ then this would be an awful case of induction because it wouldn't even be induction. In fact in some sense this is a "classic" case of induction from the fact the truth value of $P(n)$ actually depends on on the previous cases, so you are building up from the previous cases to get the next case, so if $P(2)$ is your base case all future cases should be built from $P(2)$.

$\endgroup$
  • $\begingroup$ I'm saying that it is a bad example of induction because is not true that $\forall n : P(n)$ is true $\implies $ statement I want to prove is true. Instead is $P(2) \implies$ statement I want to prove. :-) $\endgroup$ – Ant Mar 9 '15 at 19:53
  • $\begingroup$ @Ant That how induction works, the classic case of induction you prove $P(n)$ from $P(n-1)$ after proving some base cases, but that just means that in the end all that mattered were the base cases. In your comment "I don't think you do. Just take all the pairs $(1,2),(1,3),(1,4),....$ This means that all horses have the same color of the first horse. QED. There is no need to group more that 2 horses at the same time", the $....$ is just code for this is a super easy induction that anyone who knows anything about equiv relations should be able to prove. $\endgroup$ – Paul Plummer Mar 9 '15 at 19:59
  • $\begingroup$ I agree. But is a different induction, the statement changes. I used only pairs of horses instead of $n$-uples. $P(2) \implies $ statement may be showed with induction but that is not what we're doing in the proof, which is (according to me) pointless $\endgroup$ – Ant Mar 9 '15 at 20:03
  • $\begingroup$ @Ant So you came up with a different worded, although an essentially similar, proof by induction, therefore this (false) proof by induction is not really a good example of induction because its not really induction even though it is? I am not really sure what you have a problem with. $\endgroup$ – Paul Plummer Mar 9 '15 at 20:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.