how to point out errors in proof by induction

Question

I have searched for an answer to my question but no one seems to be talking about this particular matter..

I will use the all horses are the same color paradox as an example.

Everyone points out that the statement is false for n=2 and that if we want to prove the propositions we should use 2 as the base case for this proof.

But, (as I see it..), you have to use reason to figure that out. My question is, is there anything wrong with induction itself? except for the fact that we can use reason to understand why the proof is faulty.

This goes for all these problematic propositions..

Thank you all!

Answer 1

The formulation that one horse cannot have different colors is mathematically correct, but useless for the case $n=2$.

Since we need two horses to compare the colors, we cannot follow that two horses have the same color out of the trivial fact that one horse cannot have different colors.

So, the induction step does not work from $n=1$ to $n=2$. Thus, the induction is false.

Answer 2

"But, (as I see it..), you have to use reason to figure that out. My question is, is there anything wrong with induction itself? except for the fact that we can use reason to understand why the proof is faulty."

I'm not entirely sure of what you mean with using 'reason', but I'm interpreting it as "is there way to spot the mistake in the argument without having the inspiration to check what happens for $n=2$?"

There is. Take Wikipedia's argument.

Inductive step

Assume that $n$ horses always are the same color. Let us consider a group consisting of $n+1$ horses.

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..

Consider a set of $n+1$ horses: $\{h_1, h_2,\ldots ,h_n, h_{n+1}\}$.

Wikipedia now tells you to consider $\{h_2, \ldots ,h_{n+1}\}$ and $\{h_1, \ldots h_n\}$ and apply the induction hypothesis on each of this sets, which then yields that $h_2, \ldots ,h_{n+1}$ are all of the same color and $h_1, \ldots ,h_{n}$ are all of the same color.

Up until this point there's nothing wrong. But now, to say that $h_1$ has the same color as $h_2$ and consequently as $h_3,\ldots ,h_{n+1}$ you need that $h_2\in \{h_1, \ldots ,h_n\}$, but this is only true if $n>2$, for $n+1=2$ one has $\{h_1 ,\ldots ,h_n\}=\{h_1\}$, so you can't make further progress.

Answer 3

The induction principle is expressed in formal terms as follows :

$[P(1) \land \forall n(P(n) \rightarrow P(n+1))] \rightarrow \forall nP(n)$

Note : I'm starting from $1$ instead of $0$ in order to comply with the "horses example".

Consider now this "fake" application of it; let $P(n) := 2 \times n = 2$.

Clearly : $P(1)$ holds; thus, we have the base case.

What about the induction step ? $P(2) = 2 \times 2 = 4 \ne 2$; thus, $P(2)$ does not hold.

What we can infer about induction ?

$P(1)$ is true while $P(2)=P(1+1)$ is false. Thus, by the truth-conditions for the conditional : $P(1) \rightarrow P(1+1)$ is false.

But this implies that $P(n) \rightarrow P(n+1)$ is not true for any $n$.

So, the antecedent of the induction principle : $P(1) \land \forall x(P(x) \rightarrow P(x+1))$ is false and the principle does not license us to infer anything about "all" $P(x)$'s, because a conditional with false antecedent is always true, irrespective of the consequent.

---

In conclusion, we have not "falsified" the induction principle ...

In the specific case, induction is not an issue here : having showed that $P(2)$ does not hold, we have already showed that $\forall nP(n)$ is false.

---

What we have learned from this "fake" example regarding the horses paradox ?

That the purported proof of the induction step is flawed, because we cannot correctly deduce, from the (true) fact that all the horses belonging to a single-members set of horses have the same color, the (false) fact that all the horses belonging to a two-members set of horses have the same color.

Answer 4

The problem with any of these "fake proofs" is that at some point the "proof" make an additional, unspoken assumption that is not valid to make at that point. If you observe that such an assumption is made, you know immediately that the proof is unsound. You do not necessarily know at that point that the conclusion is false, but you don't believe it to be true merely on account of this "proof" either.

This is not a problem with induction per se. It is a problem with proving virtually any substantial result. That is why there are various popular fake "proofs" that do not use mathematical induction at all.

For example, you can "prove" false results by dividing both sides of an equation by zero, or by relying on the way objects appear to be arranged in a geometric diagram without actually establishing that they really must be arranged that way (things that look like straight lines but are not, points listed in order $A,B,C$ on a line when in actuality they would occur in sequence $B,A,C,$ and so forth).

In the typical "proof" that all horses are the same color, there is a step that makes the unspoken assumption that $n \geq 2$ even though it is only actually given that $n \geq 1.$ The trick works when the unwary listener does not notice the invalid assumption.

People doing real math can make an invalid assumption during an attempted proof too, although usually something much more subtle than these.

In short, methods of mathematical proof are sound, but individual human beings are fallible and do not always follow the rules, even when we try to. If everyone simply accepted any one individual's work without checking it, we might indeed have a lot of false mathematics regarded as true. Fortunately that is not the way mathematics is done.