analysis - Proof for Strong Induction Principle

I am currently studying analysis and I came across the following exercise.

---

Proposotion 2.2.14
Let $m_0$ be a natural number and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m\geq m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0\leq m'< m$, then $P(m)$ is also true. (In particular, this means that $P(m_0)$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m\geq m_0$.

Prove Proposition 2.2.14. (Hint: define $Q(n)$ to be the property that $P(m)$ is true for all $m_0\leq m < n$; note that $Q(n)$ is vacuously true when $n

---

I have difficulty understanding how I should use the hint and in general what the framework of this proof would look like (probably an inductive proof; but on what variable do we induct, what will be the induction hypothesis and how would I go about proving the inductive step etc.?). Could anyone please provide me with some hints to help me get started?

Answer

Let $B$ be the subset of $N=\{m_0,m_0+1,...\}$ such that $P(m)\iff m\in B$. This $B$ is not empty since for all $m_0\le m'

Remark: This works for all sets $N$ where each non-empty subset has a minimal element with respect to a relation $R$. These sets are called well-founded.

If you want to use the hint, show that $Q(n)$ implies $Q(n+1)$ and that $Q(m_0)$: Since $Q(m')$ is true for all $m_0\le m'< m_0$, it is also true for $m_0$. Assume $n$ is a natural number $\ge m_0$ such that $Q(n)$. This means that $P(m)\ \forall m_o\le m

So we can proof the strong induction principle via the induction principle. However, the normal induction principle itself requires a proof, it that is the proof I wrote in the first paragraph. As mentioned it works for all well-founded sets ($\mathbb N$ is such a set.)