the purpose of induction

Question

After getting an answer (in a comment) from peter for this question I have a follow up question.

If, in all horses are the same color problem for example, we need to use reason, reason which is specific to the case, in order to find that "hole" between the correct base case and the correct inductive step. That "hole" where n=2 which makes the proof collapse.

So how can we verify that our hypotheses are correct and that there are no "holes"?

I mean if we proved the base case p(0) or p(1) or p((int)whatever) is true and the inductive step is true, how can be sure that there no "holes" in the hypothesis?

Do we use induction only to prove what we know, beyond any doubt, is true? But doesn't that contradicts the purpose of a proof?

I know this is such a Newbie question.. but I have searched for answers for these specific questions and I could not find..

Thank you all!

Answer 1

If the base case is correct and the implication $n\rightarrow n+1$ is correct FOR ALL $n$ ($\ge$ a given tresh-hold), then the induction is correct and proves the claim.

It is not always easy to see whether the implication is actually right for all $n$. So, in some cases, the base case should be chosen somewhat higher, although the "laziness" of many mathematicians leads to the fact, that the base case is mostly $n=0$ or $n=1$.

To check the implication needs careful analysis, as the "horse-example" shows.

Answer 2

You can prove statements inductively from which you did not know before being true or false.

You just need to make sure that there is no "hole" in your proof. In the case of your example the problem occured because the proof of the inductive step was simply wrong. But if you check that both p(0) and the inductive step can be proved formally correct then your proof will be valid and you don't need to search for "holes" afterwards.

Answer 3

Actually, the principle of induction is an axiom that is selected to look after that the set of all natural numbers is the smallest possible of all candidates:

$(0\in M\wedge\forall n\in M(n\in M\implies n+1\in M))\implies \mathbb N\subseteq M$.

The axiom is used to prove that certain conditions $p(n)$ is true for all numbers that is elements in the defined set $\mathbb N$, by $M=\{n\in \mathbb N|p(n)\}$.

Answer 4

Induction requires two ingredients: First, we must prove $p(0)$. Then, we must prove that $p(n)$ implies $p(n+1)$. If we can do this, then we are sure that there are no holes in our argument.

The problem with the proof in question is that, though we prove $p(1)$, our proof that $p(n)$ implies $p(n+1)$ is wrong. We try to prove this as as:

Given a set of $n+1$ horses and any two horses $A$ and $B$, and notice that, by hypothesis, $A$ is the same color as every horse in the set excluding $B$ and that $B$ is the same color as every horse in the set excluding $A$.

Which is good so far - but if we then try to conclude that this implies that all the $n$ horses are the same color, we silently invoke the condition that there must be a horse $C$ other than $A$ and $B$ to which we compare each. This implies $n+1\geq 3$, so we've only proved that $p(2)$ implies $p(n)$ for all $n$ (which is clearly true; if all pairs of horses are the same color, this proof inductively and correctly proves that all horses would be).

This isn't the statement we were supposed to prove. We wanted $p(n)\rightarrow p(n+1)$ for all n. We therefore can't invoke induction - as you see, there is no way for us to get from our base case $p(1)$ to $p(2)$. We never proved that: $$p(1)\rightarrow p(2)$$ which means induction is not applicable.

The problem is that the argument doesn't follow the rules of induction and therefore doesn't work. There is no general method to check whether a proof which is not purely symbolic works and you're right that our argument could have holes which we might not be aware of, but this applies to a proof of anything. If we thought our proof that $p(n)\rightarrow p(n+1)$ worked, we would have already been wrong, since $p(1)\rightarrow p(2)$ is false - and we didn't need induction to be wrong there. Rather, the issue of having holes in one's proof is an issue regardless of what technique you use.

Answer 5

In the all horses are the same color problem there is no

"hole" [the $n=2$ case] between the correct base case and the correct inductive step.

The proof of the inductive step : $P(n) \rightarrow P(n+1)$ is flawed, because it does not hold for $n=1$ [see my answer to your previous post].

Thus, if $P(2)$ is false (as it must be with a set of two horses, one brown and the other white) and $P(1)$ is true, we cannot conclude that : for all $n$, $P(n) \rightarrow P(n+1)$ is true.

Thus, the purported proof of the inductive step is not correct.

Answer 6

Classical notion of mathematical proofs is essentially finitary, namely each mathematical proof is just some finite chunk of words (just like how we write them on a paper). The most natural or standard model of arithmetic (Peano Arithmetic) is the structure of natural numbers where the distance between 2 numbers is only finite. Therefore, induction principle on natural numbers is really consistent with the finitary nature of proofs.

For example, suppose you have proofs for p(0), and any n p(n) $\rightarrow$ p(n+1), the natural way to prove p(10) per se is to prove p(1) using p(0) $\rightarrow$ p(1) and p(0) (apply modus ponens), then p(2),p(3) etc. Then concatenate those (finite) proofs to get a proof of p(10). In the process, each step we ensure there is no "hole" in it.

Now if you look at non-standard models of Peano Arithmetic: http://en.m.wikipedia.org/wiki/Non-standard_model_of_arithmetic, then the inducton principles become trickier as the intuition does not always lift. For example, let $M\models PA$ be nonstandard then the induction principle basically tells you that there is no definable cut, i.e. $I\subsetneq M$ and $I$ is closed downwards and closed under successor function. Hence each cut is rather complex in this case (standard natural numbers form a cut and obviously there is no first-order formula that defines it). For more on models of PA and restricted induction, Richard Kaye's book is classic.