I have no idea how to prove it by using only what the book has talked about so far.
Can anyone help? The proof shouldn't be using set theory as set theory is only mentioned in the following chapter. The proof should only make use of the addition of natural numbers, order properties of natural numbers, the trichotomy of order for natural numbers and principle of induction.
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 ≥ m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0 ≤ 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 ≥ m_0$.
Exercise 2.2.5. Prove Proposition 2.2.14. (Hint: define $Q(n)$ to be the property that $P(m)$ is true for all $m_0 ≤ m < n$; note that $Q(n)$ is vacuously true when $n < m_0$.)
Thanks!
Best Answer
Proof: Let $n\in \mathbb{N}$ and let $Q(n)$ be the property that $P(m)$ is true for all $m_0 \le m < n$ for $n\ge m_0$. Using induction on $n$, for the base case $n = 0$, we want to show that $Q(0)$ is true. However, we know that $0\le m_0\ \forall\ m_0 \in \mathbb{N}$. Thus, either $0 = m_0$ or $0<m_0$ and so we split into cases. If $n = 0 < m_0$, the statement $P(m)\ \forall\ m_0\le m < n$ is vacuously true (since the hypothesis applies for $n \ge m_0$) and thus $Q(0)$ is true in this case. For the second case, if $n = 0 =m_0$, then the statement $P(m)\ \forall\ m_0\le m < n$ is also vacuously true since there is no $m' \in \mathbb{N}$ such that $0 \le m' <0$. Hence, $Q(0)$ is true for this case and that completes the base case of the induction.
Now suppose inductively that for some $n\ge m_0$, $Q(n)$ is true, i.e $P(m)\ \forall\ m_0\le m < n$ is true. We need to show that $Q(n{+\!+})$ is true.
By the definition of $P$ in the hypothesis, $P(n)$ is also true (because $Q(n)$ is true). Since $n<n{+\!+}$, then $P(m)\ \forall\ m_0\le m \le n < n{+\!+}$ is true so $P(m)\ \forall\ m_0\le m < n{+\!+}$ is true which in turn implies that $Q(n{+\!+})$ is true. Which closes the induction and hence we can conclude that $Q(n)\ \forall n$ is true.
However, $Q(n)$ true implies $P(m)\ \forall\ m_0\le m<n$ is true for all $n\ge m_0$ and by the definition of $P$, $P(n)$ is also true for all $n\ge m_0$ which concludes the proof. $\square$