0
$\begingroup$

I am in my undergraduate level, but, still it is not clear to me "When we can use induction?"

Though I have a rough idea on the later question, I think when we have a successor function which maps $P(n)\mapsto P(n+1)$, where, $P(n)$ is a proposition which depend on $n$(Correct me please if I am wrong).

Can anyone explain these in a clear way please?

Actually I think I am not able to explain the question properly, probably explaining "Why the conditions(i.e; true for $P(0)$, if true for $P(n)$ and implies $P(n+1)$ is true) are sufficient and neceassary to conclude that $P$ will hold for any $n$" will answer my question.

$\endgroup$
  • 4
    $\begingroup$ There is a lot explained in the canonical hit on wikipedia, for example. If that doesn't cover it, please be more specific about what your why and when mean. Some concrete example of what prompted this question would help as well. $\endgroup$ – dxiv Sep 22 '18 at 6:33
  • 2
    $\begingroup$ Say we proved that $P(n)$ being true means that $P(n+1)$ is true. Then let's say we also proved that $P(0)$ is true. Then we can say that $P(1)$ is true, so $P(2)$ is true, so $P(3)$ is true, etc. etc. on forever so that $P(n)$ is true for any nonnegative integer $n$ at all. $\endgroup$ – YiFan Sep 22 '18 at 6:45
  • 1
    $\begingroup$ @taritgoswami it is not explained why it works See the formalization section. Why it works depends a lot on the context you are assuming or working within, which the question doesn't specify. $\endgroup$ – dxiv Sep 22 '18 at 7:01
  • 1
    $\begingroup$ @taritgoswami any intuitive explanation? There is a comment covering that already. $\endgroup$ – dxiv Sep 22 '18 at 7:20
  • 3
    $\begingroup$ ".. he mentioned that a well known mathematician proved the Four colors theorem using induction, but it was wrong and we can't use induction for that problem.." If the proof was wrong it wasn't because induction was wrong-- it was his reasoning for the truth of the inductive step was invalid. If you can prove 1) any five region can be colored with 4 colors and 2) if any $n$ region can be colored with 4 colors then any $n + 1$ region can be colored with 4 colors, then yes, you would have proven the 4 color theoren. Thing is I don't think he had proven 2). $\endgroup$ – fleablood Sep 22 '18 at 16:46
2
$\begingroup$

Induction is just an extended form of modus ponens, the logical rule whereby if you know that $P$ implies $Q,$ and you know that $P$ is true, then you can conclude that $Q$ is true.

The trick to induction on the integers is that when you prove that $P(n) \implies P(n+1),$ you prove many implications, one for each integer $n.$ You prove $P(0) \implies P(1),$ also $P(1) \implies P(2),$ also $P(2) \implies P(3),$ $P(3) \implies P(4),$ $P(4) \implies P(5),$ and $P(5) \implies P(6).$ And it doesn't stop there; it just keeps going and going as long as you need it to.

So let's say you have some propositional formula $P(n),$ you have proved the base case, $P(0),$ and you have proved the inductive step, $P(n) \implies P(n+1).$ Now suppose you want to show that $P(3)$ is true.

You can do this by applying modus ponens a finite number of times.

From $P(0) \implies P(1)$ and from $P(0)$ (both of which you have already proved) you can conclude that $P(1)$ is proved.

From $P(1) \implies P(2)$ and from $P(1)$ you can conclude that $P(2)$ is proved.

Finally, from $P(2) \implies P(3)$ and from $P(2)$ you can conclude that $P(3)$ is proved.

What if you wanted to prove $P(5)$? You would just need a couple more applications of modus ponens. With a few more applications, you could prove $P(17).$ To prove $P(1000000)$ this way takes a million applications of modus ponens. Few if any people would care to write out every step of such a proof, but clearly such a proof exists in principle.

What the principle of induction on the integers says is (in effect) that since you can count up to any integer by applying the successor function $n \mapsto n+1$ a finite number of times, if at each step you have the proven implication $P(n) \implies P(n+1)$ and if you have the proven base case $P(0)$ needed by the first application of modus ponens, you can (in principle) prove $P(k)$ for any integer $k$ simply by applying modus ponens $k$ times. Since $P(k)$ is provable for any integer $k$ in this way, $P(k)$ is true for every integer $k.$

So when can't you use induction over the integers? You cannot use it when a prerequisite for any single one of the applications of modus ponens for some integer $k$ is missing. If you do not have a proof for the base case $P(0),$ you do not even have the prerequisites for the first application of modus ponens, which would have proved $P(1).$ If there is even a single natural number $n$ for which your proof that $P(n)\implies P(n+1)$ is not valid, one of the applications of modus ponens is broken.

For example, there is a famous fake "proof" that all horses are the same color. (See these notes, in the middle of page 3.) In that proof, the base case is true, and it is also true that $P(n)\implies P(n+1)$ for every natural number $n$ . . . except when $n = 1.$

That one exception invalidates the entire induction. It means we cannot even prove $P(2)$ for that induction; and since we cannot do that, it is useless to know that $P(2) \implies P(3)$ or any of the other implications we could get from the inductive step for larger values of $n.$

$\endgroup$
1
$\begingroup$

Proof by induction can only be used to prove that every natural number $x$ has the some property $P$, i.e. that for all $x \in N$, we have $P(x)$ being true.

Although it may not be immediately obvious, the principle of mathematical induction is based on a fundamental property of the natural number; namely that any natural number can be reached by going from one number to the next starting at 0 (or 1 depending on which you choose to be the "first" number).

Here is how it works: Suppose you want to prove that for every $x\in N$, $x$ has property $P$, i.e. we have $P(x)$ being true. Fortunately, we do not have to test every natural number, but we do have to test the "first" number. If $0$ is your "first" number, then we would have to show that $0$ has property $P$, i.e. that $P(0)$ is true. Then we must prove that if $k \in N$ and $k$ has property $P$, then the "next" number $k+1$ must also have property $P$. To do this, assume $P(k)$ is true and then prove that P(k+1) must then also be true. And you are done! $P(0)$ is true, therefore $P(1)$ is true, therefore $P(2)$ is true, and so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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