Proof of Strong principle of Induction (T. Tao Analysis I)

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!

Solution 1:

Theorem. (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')$ is true for all natural numbers $m_0 \le 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 \ge m_0$.

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$

Solution 2:

Let's state the theorems properly:

Theorem $1$ (Induction): Let $P(n)$ be a formula of natural numbers, assume $P(0)$ and $$\forall n\in \mathbb{N}\ \ \ P(n)\implies P(n+1) $$ Then $\forall n\in \mathbb{N} \ \ P(n)$.

and:

Theorem $2$ (Strong Induction): Let $Q(n)$ be a formula of natural numbers, assume $Q(0)$ and $$\forall n\in \mathbb{N}\ \ \ \left(\forall k\leq n \ \ \ Q(k)\right)\implies Q(n+1) $$ Then $\forall n\in \mathbb{N} \ \ P(n)$.

Here you can replace $0$ by some $m_0$ and anything does not change. The question is how can we prove the Strong induction using only Induction. First I will state that Theorem 1 can be proved easily depending in the chosen definition of the set of natural numbers $\mathbb{N}$. Now let us prove the second theorem:

Given a formula $Q$ for natural numbers, assume $Q(0)$ and $$\forall n\in \mathbb{N}\ \ \ \ \ \ \left(\forall k\leq n \ \ \ Q(k)\right)\implies Q(n+1) \tag{*}$$

now consider $P(n)$ the following formula: $$\forall k\leq n \ \ \ Q(k) $$

• It's clear that $P(0)$ is true because it's equivalent to $Q(0)$
• Now given an natural number $n$, first we have (very obvious): $$\left(\forall k\leq n \ \ \ Q(k)\right)\implies \left(\forall k\leq n \ \ \ Q(k)\right) $$ and second we have from $(*)$: $$\left(\forall k\leq n \ \ \ Q(k)\right)\implies Q(n+1)$$ combining this two relations we have: $$\left(\forall k\leq n \ \ \ Q(k)\right)\implies \left(\forall k\leq n+1 \ \ \ Q(k)\right) $$ which in its turn signifies that: $$P(n)\implies P(n+1) $$

From these two conditions we can apply theorem 1 and we conclude that $\forall n\in \mathbb{N} P(n)$, or in other terms :$$\forall n\in \mathbb{N} \left(\forall k\leq n \ \ \ Q(k)\right)$$

and this implies that: $$\forall n\in \mathbb{N}\ \ \ \ Q(n)$$ and the proof terminates.