Prove Proposition 2.2.14.
Hint: define $Q(n)$ to be the property that $P(m)$ is true for all $m_{0}\le m<n$; note that $Q(n)$ is vacuously true when $n\le m_{0}$.
Proposition 2.2.14 (strong principle of induction).
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\ge m_{0}$, we have the following implication: if $P(m\prime)$ is true for all natural numbers $m_{0}\le m\prime<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\ge m_{0}$.
Let $Q(n)$ be the statement that $P(m)$ is true for all $m_{0}\le m<n$. The figure below illustrates the relationship between $Q(n)$ and $P(m)$.
If we can prove that $Q(n)$ is true for all natural numbers $n$, that would mean $P(m)$ is true for all natural numbers $m\ge m_{0}$.
We'll use induction to show $Q(n)$ is true for all natural numbers $n$. We need to prove the base case $Q(0)$ and the induction step $Q(n)\implies Q(n++)$.
Before proceeding, we'll note the following property of $P$ assumed by Proposition 2.2.14.
$$ P(m')\text{ where }m_{0}\le m'<m\implies P(m) \tag{i} $$
Base Case
The base case $Q(0)$ is the statement that $P(m)$ is true for all $m_{0}\le m<0$. This is vacuously true since there are no natural numbers less than 0.
Induction Step
We assume $Q(n)$ as the induction hypothesis, and aim to show $Q(n++)$.
$Q(n)$ true means $P(m)$ is true for all $m_{0}\le m<n$. By assumption (i) this means $P(n)$ is also true. And so we have $P(m)$ is true for $m_{0}\le m\le n$. This means $P(m)$ is true for $m_{0}\le m<n++$. This is equivalent to $Q(n++)$.
By showing the base case and the induction step, we have shown that $Q(n)$ is true for all natural numbers $n$. That is, $P(m)$ is true for all natural numbers $m\ge m_{0}$.
We should justify $m\le n\implies m<n++$. By Definition 2.2.11, $m\le n$ means $n=m+x$ for some natural number $x$. By the substitution axiom of equality $n++=(m+x)++$, which by Lemma 2.2.3 is $n++=m+(x++)$. For the purpose of contradiction let's assume $n++=m$. Definition 2.2.1 gives us $m+0=m+(x++)$. By Proposition 2.2.6 (cancellation law) we have $0=x++$, which contradicts Axiom 2.3. And so $n++\ne m$. By Definition 2.2.11, both $n++=m+(x++)$ and $n++\ne m$ means $m<n++$.
