Tao Analysis I - 2.2.6

Exercise 2.2.6

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m ≤ n$; this is known as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

The proposal seems intuitively correct and obvious, so the challenge is to prove it using only the building blocks provided by the text up to this point.

In case it isn't obvious, let's illustrate it. If the property $P(5)$ is true, the statement $P(m++) \implies P(m)$ tells us that $P(4)$ is also true. Now we know $P(4)$ is true, we can use $P(m++) \implies P(m)$ again to tell us $P(3)$ is true. We can keep going until we show $P(0)$ is true. So $P(0 \leq m \leq 5)$ is true.

Approach

We might be tempted to use soem form of induction that works backwards, but we can't do that. That is what we're being asked to prove, and we can only use the principle of induction as defined in Axiom 2.5, which goes forward, not backwards. 

As with the previous exercise, we transform the problem from one about $P(m)$ to one which is about $n$ by formulating a statement $Q(n)$. 

$$Q(n) : P(n) \implies P(m \leq n)$$

That is, $Q(n)$ says if $P(n)$ is true, then $P(m)$ is true for all natural numbers up to and including $n$.

 

Induction Proof

Now we can use standard induction on $n$, which we hope will show $Q(n)$ is true for all natural numbers $n$. Before we dive in, let's write out the known facts for clarity.

$$P(m++) \implies P(m)$$

$$P(n) \; \text{is true}$$

Inductive Hypothesis: $Q(n)$ is true.

Base Case: Consider $n=0$, which means

$$\begin{align}Q(0) &: P(0) \implies P(m \leq 0) \\ \\ Q(0) &: P(0) \implies P(0)\end{align}$$

$P(m \leq 0)$ is equivalent to $P(0)$ beccause only $m=0$ satisfies the inequality. 

$Q(0)$ is clearly true because $P(0) \implies P(0)$ is always true ... even if $P(n=0)$ were false, which it is not here.

Inductive Step: We need to show $Q(n) \implies Q(n++)$.

Let's start with $Q(n)$.

$$Q(n) : P(n) \implies P(m \leq n)$$

But we're given $P(n++) \implies P(n)$ so

$$P(n++) \implies P(n) \implies P(m \leq n)$$

We're almost there. $A \implies B$ is equivalent to $A \implies (B \land A)$. In plain English this is saying the implication of $A$ includes $A$. This gives us

$$\begin{align}P(n++) &\implies P(m \leq n) \land P(n++) \\ \\ P(n++) &\implies P(m \leq n++)\end{align}$$

This is $Q(n++)$.

By showing the base case $Q(0)$, and that $Q(n) \implies Q(n++)$, by the induction principle we have shown $Q(n)$ is true for all natural numbers $n$.

Translating back from $Q$ to $P$, we have $P(n) \implies P(m \leq n)$ if $P(n)$ is true, and $P(m++) \implies P(m)$. $\square$