The "assumption" in proof by induction

Question

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.

Answer 1

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 true, 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}$$

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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:

4. 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.
5. On inspection, step 2 is a valid simple definition following from step 1, and also step 3 seems correct as well.
6. Therefore our error is either the logic itself, or our assumption at step 1.
7. 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 :)

Answer 6

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