24
$\begingroup$

The second step in proof by induction is to:

Prove that if the statement is true for some integer $n=k$, where $k\ge n_0$ then it is also true for the next larger integer, $n=k+1$

My question is about the "if"-statement. Can we just assume that indeed the statement is true? If we assume it, then the proof works... but isn't that similar to the following "proof":

Let $N$ be the largest positive integer.
Since $1$ is a positive integer, we must have $N\ge1$.
Since $N^2$ is a positive integer, it cannot exceed the largest positive integer.
Therefore, $N^2\le N$ and so $N^2-N\le0$.
Thus, $N(N-1)\le0$ and we must have $N-1\le0$.
Therefore, $N\le1$. Since also $N\ge1$, we have $N=1$.
Therefore, $1$ is the largest positive integer.

The only thing that is wrong with this "proof" is that we falsely assume there actually exists a largest positive integer.

So both in the above case and in proof by induction we do an assumption. In the second case the assumption leads to a false conclusion. What is the difference with proof by induction? Why is doing the assumption that the hypothesis is actually true valid here and why doesn't it lead to a similar contradiction?

EDIT: the "proof" above is not mine, it is taken from Calculus a Complete Course 8th edition as an example of why existence proofs are important.

|cite|improve this question
$\endgroup$
  • 7
    $\begingroup$ The logic of proof by induction goes as follows. "If $n=1$ is true, then $n=2$ is true", combined with "$n=1$ is true", implies that "$n=2$" is true. Then "If $n=2$ is true, then $n=3$ is true", combined with "$n=2$ is true", implies that "$n=3$" is true. So on and so forth. So you only need to show, in general, that "If $n=k$ is true, then $n=k+1$ is true" and "$n=1$ is true", namely the second and the first step in the proof. $\endgroup$ – hypernova Apr 15 '18 at 11:07
  • $\begingroup$ The issue here is the use of the term "some integer", existential quantification. This very common phrasing is not only misleading, it is wrong. Please read this question and my answer to it. $\endgroup$ – Git Gud Apr 15 '18 at 11:09
  • 5
    $\begingroup$ In induction, you do not show "the staement is true for $n=k+1$", you literally show "if the statement is true for $n=k$, then the statement is true for $n=k+1$". The fake proof actually shows, "if there is a largest integer, then it must be $1$", a true statement. $\endgroup$ – Hagen von Eitzen Apr 15 '18 at 16:18
  • $\begingroup$ Possibly helpful: matheducators.stackexchange.com/questions/10021/… $\endgroup$ – Ethan Bolker Apr 16 '18 at 0:24
28
$\begingroup$

Indeed, a fallacious conclusion may be reached by valid deduction from an unjustifiable premise.

This is why the first step of induction is to prove that the predicate is justified for the base case; to ensure that we do not do that.

If $\mathcal P(0)$ is proven and for all natural numbers $n$ we can show that $\mathcal P(n)\to\mathcal P(n+1)$ is provable, then we may successively prove $\mathcal P(1)$, $\mathcal P(2)$, $\mathcal P(3)$, and so forth, by iterative applications of modus ponens.

$${\text{We may soundly prove }\mathcal P(1)\text{ from having proven }\mathcal P(0)\textit{ and }\mathcal P(0)\to\mathcal P(1)\\\text{We may soundly prove }\mathcal P(2)\text{ from having proven }\mathcal P(1)\textit{ and }\mathcal P(1)\to\mathcal P(2)\\\text{We may soundly prove }\mathcal P(3)\text{ from having proven }\mathcal P(2)\textit{ and }\mathcal P(2)\to\mathcal P(3)\\\text{And so forth, and so on,}\textit{ et cetera,}\ldots}$$

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ PS: this is the method called Weak Induction. $\endgroup$ – Graham Kemp Apr 15 '18 at 12:20
  • 1
    $\begingroup$ That depends. Does $\mathcal{P}$ quantify over all the naturals less than its argument? (I.e., it may be strong inductions, depending on the details of $\mathcal{P}$) Of course, both types of induction are equivalent (in one direction, by the method I mention and in the other by accumulating truths). $\endgroup$ – Eric Towers Apr 15 '18 at 20:21
  • 1
    $\begingroup$ What I think confuses people is that it looks like we are assuming $\forall n \, \mathcal P(n)$. But we don't. We assume $\mathcal P(n)$ for some $n$ and from this show $\mathcal P(n+1)$. Then, since $n$ was taken arbitrary, we conclude that $\forall n \, ( \mathcal P(n) \implies P(n+1) ).$ This is then used together with $\mathcal P(0)$ to conclude $\forall n \, \mathcal P(n)$. $\endgroup$ – md2perpe Apr 15 '18 at 21:39
  • 2
    $\begingroup$ @md2perpe Good point. One helpful thing I've seen (actually in my very first encounters with induction, fortunately) is to use different symbols: we want to prove $\forall n \, \mathcal P(n)$, for which we prove $\mathcal P(0)$ and that $\mathcal P(k) \implies P(k+1)$ for arbitrary $k$ (note $k$, not $n$). This helps the beginner (without much mathematical maturity) a great deal, even though mathematically it's the same thing, because we're trying to prove $\mathcal P(n)$ but we never assume $\mathcal P(n)$, only $\mathcal P(k)$. :-) $\endgroup$ – ShreevatsaR Apr 16 '18 at 6:18
  • $\begingroup$ @ShreevatsaR. I have also seen using $k$ for the induction step and think that it's helpful, even for me. $\endgroup$ – md2perpe Apr 16 '18 at 14:55
36
$\begingroup$

Your confusion is that you think you have proved something wrong!

You have proved that

"If there exists a largest positive integer then that largest positive integer is $1$"

That is a true statement.

Note that the statement $$ P \implies Q$$ is false only if $P$ is true and $Q$ is false

In your case $P$ is false , so your statement is true.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ This answer would be improved if you tied it back to the induction proof. $\endgroup$ – Yakk Apr 16 '18 at 19:48
3
$\begingroup$

The assumption of the inductive hypothesis is valid because you have proven (in the first part of the proof by induction, the base case) that the statement $P$ holds for $n = n_0$. So you can think of it this way: initially, you only know that $P(n_0)$. But this, together with your proof of "if $P(n)$, then $P(n + 1)$", which implies "if $P(n_0)$, then $P(n_0 + 1)$", allows you to conclude that $P(n_0 + 1)$ by modus ponens. Another consequence of "if $P(n)$, then $P(n + 1)$ is "if $P(n_0 + 1)$, then $P(n_0 + 2)$", which then allows you to conclude that $P(n_0 + 2)$ by modus ponens. Continuing in this way, you can conclude $P(n_0 + k)$ for any natural number $k$ since any natural number $\ge n_0$ can be reached in this manner using a finite number of applications of modus ponens.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

The proof by induction is based on the following statement \begin{aligned} & \left [\mathcal {P}(0) \land \left( \mathcal {P}(n) \implies \mathcal {P}(n+1)\; \forall n\geq 0\right)\right] \\ & \implies \mathcal {P}(n)\; \forall n\geq 0 \, , \end{aligned} where $\mathcal {P}$ is a predicate over the natural integers $\Bbb N$. As soon as one has shown the inheritance property $\mathcal {P}(n) \implies \mathcal {P}(n+1)$ (with the if) and the initialization $\mathcal {P}(0)$, then $\mathcal {P}(n)\; \forall n$. If only the inheritance property is proven, one can obtain such stupid results as all natural integers are larger than $\pi$ (corresponding predicate $\mathcal {P}(n) : n \geq \pi$).

|cite|improve this answer
$\endgroup$
2
$\begingroup$

You have accomplished a proof by contradiction, not a proof by induction, and the hypothesis you've proved, is not the one you thought.

What you actually did argue in your 'proof':

  1. Assume a largest integer >= 1 exists.
  2. Let N be that largest integer.
  3. Then N cannot be more than N^2 (property of "squaring" for all positive integers) and N cannot be less than N^2 (contradicts steps 1+2)
  4. So N must be 1

Step 1 is how a "proof by contradiction" usually starts, and step 4 is incorrect. Actually steps 1 to 3 are okay, you just have not used them correctly.

Here is what should happen after step 3....

Correct conclusion:

  1. As 1 is not the largest integer (2 >= 1 for example), there is a contradiction, so one of our assumptions or steps in 1 - 3 is incorrect.
  2. On inspection, step 2 is a valid simple definition following from step 1, and also step 3 seems correct as well.
  3. Therefore our error is either the logic itself, or our assumption at step 1.
  4. If step 1 causes us to reach an incorrect deduction in our logic, then it looks like our conclusion should be one of 3 things: either (A) logic itself is broken / inconsistent, (B) we we have a very subtle logic error, or (C) there is no "largest integer more than 1".

At this point most mathematicians and logicians will doubt (A) very much. They will check if (B) is possible. Then, in this case at least, they will quickly conclude (C).

Comment:

Note that in some famous cases, the correct conclusion was indeed that the logic was subtly wrong. Those cases have changed logic and mathematics in the past! But this is not one of those famous examples :)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Step 4 is correct; assuming a largest integer >= 1 exists, it is 1. The OP's problem is that removing the step 1 assumption requires justification, not a flaw in the proof. And induction provides a way to take the local reasoning (with the assumption) and apply it globally. $\endgroup$ – Yakk Apr 16 '18 at 19:49
  • $\begingroup$ Step 4 is incorrect for what the OP set out to prove. That's the important thing. $\endgroup$ – Stilez Apr 16 '18 at 23:16
0
$\begingroup$

I to struggled with induction, so I justified it to myself with an analogy:

  • Well ordered principle: Assume that you have a (countably infinite) line of dominoes set up. We want to show that the entire line falls if we knock the first over
  • Induction step: You can prove that if the $n$th domino falls, then it knocks the $n+1$th domino too
  • Base case: To prove that all the dominoes fall sequentially, we knock the first one over, which knocks the second, which knocks the third etc.
|cite|improve this answer
$\endgroup$
0
$\begingroup$

Your proof is correct, but it doesn't prove what you want it to prove.

Let N be the largest positive integer.

Since 1 is a positive integer, we must have N≥1.

Since N2 is a positive integer, it cannot exceed the largest positive integer.

Therefore, N2≤N and so N2−N≤0.

Thus, N(N−1)≤0 and we must have N−1≤0.

Therefore, N≤1. Since also N≥1, we have N=1.

Therefore, 1 is the largest positive integer.

The above proof has one unfounded assumption -- that the largest positive integer exists (your first claim).

What you have proven is that if the largest possible integer exists, it is 1.

In order to remove the "if" on this proof, you have to justify it. And nothing above justifies it.

In the case of induction, we have a rule that lets us remove the "if". We build a sub-proof that looks like:

Assume $P(k)$

[Insert sub-proof here]

Thus $P(k+1)$

This proves $P(k)$ implies $P(k+1)$. It is a valid proof all by itself, but it does not prove $P$ for all $k$.

Induction is the rule that if you have $P(1)$ and ( $P(k)$ implies $P(k+1)$ for all natural numbers $k$ ), then you have $P(x)$ for all natural numbers $x$. It is a rule that lets you remove the if clause -- the assumption -- on the sub-proof, and generate a fact about natural numbers from it.

It is magical, in that that is basically the defining rule of the strange structure we call the natural numbers -- that they are the minimal thing closed under succession.

It can be pointed out that the structure of a proof by contradiction is similar.

Assume X

[Insert sub-proof here]

Thus Y

This proves $X$ implies $Y$. Then we proceed to show that $Y$ is false, which gives us $X$ is false as $(\neg Y \land (X \implies Y)) \implies \neg X$.

|cite|improve this answer
$\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.