Is this proof of Proposition 2.2.14(Strong principle of induction) ok or not in Terence Tao's "Analysis I"?

350 Views Asked by At

I am reading "Analysis I" by Terence Tao.

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 \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.$

Is the following proof of Proposition 2.2.14(Strong principle of induction) ok or not?

Proof:

Let $Q(n)$ be the property that $P(m)$ holds for all $m_0 \leq m < n.$

$Q(0)$ is vacuously true.

Assume that $Q(n)$ is true.

This means that $P(m)$ is true for all $m_0 \leq m < n$.

If $n++ \leq m_0$, then $Q(n++)$ is vacuously true.

If $m_0 < n++$, then $m_0 \leq n$.

By the assumption of "Strong principle of induction", $P(n)$ is true.

So, $P(m)$ is true for all $m_0 \leq m \leq n$.

And $m \leq n \Leftrightarrow m < n++$.

So, $P(m)$ is true for all $m_0 \leq m < n++$.

So, $Q(n++)$ is true.

By "principle of mathematical induction", $Q(n)$ is true for every natural number $n$.

Let $m$ be a natural number such that $m_0 \leq m$.

Then, $Q(m++)$ is true and $m_0 \leq m < m++$.

So, $P(m)$ is true.

1

There are 1 best solutions below

0
On

Alternative route.

Assume that the statement: "$P(m)$ is true for all natural numbers $m\geq m_0$" is false.

Then there must be a minimal natural number $m_1\geq m_0$ such that $P(m_1)$ is false.

The minimality of $m_1$ assures that for every natural number $m'$ that satisfies $m_0\leq m'<m_1$ the statement $P(m')$ is true.

This however implies that $P(m_1)$ is true.

A contradiction is found which means that our assumption must be false.

So we conclude that the statement "$P(m)$ is true for all natural numbers $m\geq m_0$" is not a false statement (hence is a true statement).