Check workings for Strong Induction (Proof by Contradiction)

Question

I want to prove the following:

Suppose that $P(n)$ is a statement involving a general positive integer $n$.

Then $P(n)$ is true for all positive integers $n$ if:

i) $P(1)$ is true, and

ii) [$P(n)$ holds for all positive integers $n \le k$] $\Rightarrow$ $P(k+1)$, for all positive integers $k$

My Attempt:

First, I note that the axiom is equivalent to:

$\left[ P(1) \text{ and } \left[ P(m) \Rightarrow P(m+1), \text{ for }m\le k\right] \right] \Rightarrow \forall n P(n)$ where $m,k,n$ are positive integers.

So, suppose for contradiction that $\text{not } \forall n P(n)$ is true.

Therefore, we have $P(n_0)$ is false and $1\lt k \lt n_0$ and $n_0=k+1$. ($n_0$ is the least integer such that $P(n)$ is false)

But, since $P(k)$ is true, then $P(k+1)$ is true too. Therefore, $P(n_0)$ is true too. Hence, a contradiction.

Is my proof correct and complete and is there anything else I can do to improve it? My workings is base on this document.

Answer 1

Note that there are saveral principles in place here.

(i) The principle of mathematical induction :

$[P(0) \land \forall k (P(k) \rightarrow P(k+1))] \rightarrow \forall n P(n)$.

You want to prove a form of

(ii) The principle of strong induction :

$\forall k[\forall m(m < k \rightarrow P(m)) \rightarrow P(k)] \rightarrow \forall nP(n)$.

Strong induction is provable from mathematical induction.

In your prove "by contradiction", you made use of :

"suppose for contradiction that not $∀nP(n)$ is true, i.e. $P(n_0)$ is false for some $n_0$, where $n_0$ is the least integer such that $P(n)$ is false".

But this is

(iii) The least number principle :

$P(x) \rightarrow \exists y[P(y) \land \forall z (z < y \rightarrow \lnot P(z))]$

which is provable from strong induction.

Conclusion : you cannot avoid induction to prove it.