How to prove proposition $2.2.14$ in Tao Analysis $I$?

Question

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

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

Base Case: $Q(0)$ is vacuously true since there are not natural numbers less than $0$.

Inductive Step: Suppose $Q(n)$ holds true. Then this means that $P(m)$ is true for all $m_0\leq m<n.$

We have to show that $Q(n++)$ is true, where $n++$ denotes the successor of $n$. This is equivalent to proving that $P(n)$ holds because $P(m)$ is already true for all natural numbers $m_0\leq m<n.$ And this is the part where I am getting stuck because there does not seem to be a clear implication from the induction step that $P(n)$ should be true.

One way to fix this could be to let $Q(n)$ be the property that if $P(m)$ holds for all $m_0\leq m<n$ then $P(n)$ is true, but I am not sure whether this is an appropriate way to define a property.

Answer 1

You've probably figured this out by now but here's my take:

We wanna show $Q(n)$ is true for $n\ge m_0$ given $Q(n)\Rightarrow P(n)$ by induction on $n$.

Let $n\le m_0$. Then $Q(n)$ is vacuously true. These are a bunch of base cases. Now suppose that $Q(n)$ is true for some $n\ge m_0$. Well $Q(n)\Rightarrow P(n)$ so $P(n)$ is true. This means that $P(m')$ is true for $m_0\le m'<n+1$ which is another way of saying $Q(n+1)$. So the induction is closed, and $Q(n)$ for every $n\ge m_0$.

I was confused similarly. The trick is that we need to suppose $Q(n)\Rightarrow P(n)$ because that's what strong induction is all about, and the weak induction to show $Q(n)$ uses that fact but is kinda orthogonal to it.

Answer 2

$Q(m_0)$ is vacuously true.

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

From the implication in the hypothesis, which can be rewritten (with a slight change of notation) as:

"if $P(m)$ is true for all natural numbers $m_0 \leq m < n$, then $P(n)$ is also true."

it follows that $P(n)$ is true. As $P(m)$ is true for $m<n$, one has:

$P(n)$ is true for all $m_0\le m<n+1$

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

Answer 3

Slightly long approach.

I spent some time trying to find an answer to this same question, while there are good answers out there. I still had some questions that I wanted further justification for and I write this answer for others that might stumble on the same search as I did.

I have seen a fair bit of some common errors in many answers, one being that $m=0$ has been used in the base case of induction proofs and not $m=m_0$.

Motivation for this late post.

Most of the answers I have seen used Terence's hint of defining $Q(n)$ to be the property that $P(m)$ is true for all $m_0\leq m < n$. For clarity transcribing proposition 2.2.14 in logic symbol it takes the form

$$\left(\forall m\geq m_0 \left[(\forall m_0\leq m' < m\; P(m')) \Rightarrow P(m)\right]\right) \Rightarrow \forall m\geq m_0\; P(m)\tag{*}\label{*}$$

Many for the answers I have seen the proofs end up taking the form

$$\left(\forall m\geq m_0 \left[(\forall m_0\leq m' < m\; P(m')) \Rightarrow P(m)\right]\right) \Rightarrow \forall m\geq m_0\; Q(m)$$

Which can be rewritten in terms of our definition of $Q(n)$ as

$$\left(\forall m\geq m_0 \left[(Q(m) \Rightarrow P(m)\right]\right) \Rightarrow \forall m\geq m_0\; Q(m)\label{1}\tag{1}$$

And I think this is exactly what the hint is implying (or so I conjecture). But I think there is a crucial justification missing to keep the tone of the book up until this point. In Daniel J. Velleman's book "How to prove it: A structured approach." (3rd edition ), in chapter 6.4 exercise (1), he ask the reader to justify strong induction and in the first part of the exercise he ask the reader to show the following. (little changed to fit Terence's definition.)

$$\forall m\geq m_0 P(m) \iff \forall n\geq m_0 Q(n)\tag{2}\label{2}$$

So if we approach the proof by (\ref{1}) after proving (\ref{2}), it would the the same as proving (\ref{*}). But why would we rather want to use the right hand side of (\ref{2}) rather than the left ? I will elaborate on that in the next section.

Difference in induction hypotheses.

For a implication such as (\ref{1}) for example, we start out with supposing the left hand of the implication (the antecedent) to be true and then use the most suitable proofing method to prove the right hand side of the implication (the consequence).

In (\ref{1}) the most suitable approach for the right hand side is proof by mathematical induction, proving $\forall m\leq m_0 Q(n)$ by standard induction amounts to proving $Q(m_0)$ (base case) and $(Q(m)\Rightarrow Q(m++))$. The left hand side of (\ref{1}) is really beneficial since that helps in proving $(Q(m)\Rightarrow Q(m++))$.

We can show that $(Q(m)\Rightarrow P(m))\Rightarrow Q(m++)$, our induction hypothesis of proving $\forall m\leq m_0 Q(n)$ would be something along the lines of

Suppose inductively that $Q(m)$ is true for some arbitrary natural number $m\geq m_0$, we aim to show that $Q(m++)$ is true.

Here our goal becomes to show that $Q(m++)$ or rather $(\forall m_0\leq m' < m++\; P(m'))$ is true, we will do this by showing that $(Q(m)\Rightarrow P(m))\Rightarrow Q(m++)$. Essentially the inductive hypothesis gives us by definition of $Q(m)$ that $(\forall m_0\leq m' < m\; P(m'))$ which is just one lower than what we are trying to prove.

Had we tried to prove $\forall m\geq m_0\; P(m)$ instead as the right hand side of (\ref{1}), then our induction hypothesis would be along the lines of

Suppose inductively that $P(m)$ is true for a arbitrary natural number $m\geq m_0$, we aim to show $P(m++)$ is true.

This inductive hypothesis gives us that $P('m)$ is true but we can't really use the original hypothesis $\left(\forall m\geq m_0 \left[(Q(m) \Rightarrow P(m)\right]\right)$ much since that would require us to show that $Q(m++)$ to infer (by modus ponens) that $P(m++)$ is true. For that we would need to know that $P(m')$ holds true for each natural number $m'$ greater than or equal to $m_0$ but less than $m++$. Our inductive hypothesis simply doesn't give as much information as the one obtained from $\forall m\geq m_0 Q(m)$.

Tl;dr: the proof

I do apologise for the length, I write in this way since many reading this book might be having their first exposure to some proofing techniques thus I feel it justified.

Some what of a lemma,

Now we aim to prove (\ref{2}), $(\Rightarrow)$ Suppose that $\forall m\geq m_0\;P(m)$. Let $n$ be a arbitrary natural number such that $n\geq m_0$, we aim to prove $Q(n)$ to be true which by definition amount to proving that $\forall m_0\leq m' < n\; P(m')$ is true, which follows trivially since by assumption $P(k)$ is true for all natural numbers $k\geq m_0$, thus $Q(n)$ is true.

Suppose that $\forall n\geq m_0\; Q(n)$, and let $m$ be a arbitrary natural number such that $m\geq m_0$. We aim to show that $P(m)$ is true, since $m\geq m_0$ and $m++ > m$ (this can be proven) then by transitivity $m++ > m_0$ thus by our hypothesis $Q(m++)$ and by definition of $Q(m++)$ we can infer that $P(m)$ is true. $$\tag*{$\blacksquare$}$$

The main proof.

We we aim to prove proposition 2.2.14, we do so by proving (\ref{1}) using many of the facts we have already laid out.

Suppose $\left(\forall m\geq m_0 \left[(Q(m) \Rightarrow P(m)\right]\right)$, that is for each $m\geq m_0$ that if $Q(m)$ is true then $P(m)$ is true. Now we employ mathematical induction in our goal of proving that $\forall n\geq m_0\; Q(n)$, for the base case let $n=m_0$ we then aim to prove that $Q(m_0)$ is true. By definition we aim to show $\forall m_0\geq m' < m_0\; P(m')$, by proposition. 2.2.13 (Trichotomy of order for natural numbers) there can be no natural number such that either $m_0 < m'$ or $m_0 =m$ and at the same time $m'<m_0$ this this is vacuously true, thus $Q(m_0)$ is vacuously true.

Now suppose inductively that $Q(m)$ is true for a arbitrary natural number $m\geq m_0$, we aim to show that $Q(m++)$ is true. Since $Q(m)$ holds then $P(m')$ for each natural number $m'$ less than or equal to $m_0$ and less than $m$, and by our assumption $\left(\forall m\geq m_0 \left[(Q(m) \Rightarrow P(m)\right]\right)$ we can infer that $P(m)$ is true. Thus $P(m')$ hold for each natural number $m'$ such that $m_0\geq m' \leq m$ or rather $m_0\geq m' < m++$ which is the definition of $Q(m++)$, therefore we have closed the induction.

Since we have proven $\left(\forall m\geq m_0 \left[(Q(m) \Rightarrow P(m)\right]\right) \Rightarrow \forall n\geq m_0\; Q(n)$ and $\forall m\geq m_0 P(m) \iff \forall n\geq m_0 Q(n)$, we have equivalently proven (\ref{*}) $$\tag*{$\blacksquare$}$$

Conclusion.

In essence this what a very long winded explanation for how I think the hint was supposed to be used (and why), along with the justification of (\ref{2}) that I felt was missing this was motivated by the aforementioned exercise in "How to prove it: A structured approach." (perhaps it is obvious but I wanted to keep the tone of the book).This is very much open to critique since I am very much a self taught novice and appreciate all feedback.

Answer 4

I think that a rewriting of the proposition will help in resolving the problem. What Tao actually meant was:

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

Thus the fact that $P(n)$ holds is automatically implied by the definition of $P(n)$. What that means is that whenever we say $P(n)$ holds for some $n\geq m_0$ then it is equivalent to saying that $P(m)$ holds for all natural numbers $m_0\leq m<n$ and $P(n)$.

This is what I think, but maybe I am wrong.