Prove Verification: Proving the Principle of Backwards Induction – Tao Analysis I

Question

In Tao's Analysis I, exercise 2.2.6 asks the reader to prove the following proposition:

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\leqslant n$; this is known as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

This question has been asked before on this site, but some of the proposed proofs are difficult for me to follow. At any rate, I have written my own proof and just wanted some community feedback to confirm its accuracy.

The only axiom necessary to navigate this proof is:

Axion 2.5$\ \ $ (Principle of mathematical induction). Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n\!+\!+)$ is also true. Then $P(n)$ is true for every natural number $n$.

Further, the notation "$n++$" denotes the successor of a particular natural number $n$.

Without further adieu:

---

The overarching structure of this proof is to carry out induction on the variable $n$ using the following statement:

If $P(n) \land ( P(m++)\implies P(m))$, then $\forall k \leq n$, $P(k)$

Base case of $n=1$.

Assume $P(1) \land (P(m++)\implies P(m))$. We need to prove that $\forall k \leq 1$, $P(k)$.

Specializing $1$ to $m++$ means that $m=0$. Therefore, using the assumed truthfulness of the property $P(m++)\implies P(m)$, we have $P(1) \implies P(0)$. Because $P(1)$ was assumed to be true, so, too, is $P(0)$. Therefore, because we are dealing with $\mathbb N$, only $0,1 \leq 1$, and we have proven $\forall k \leq 1$, $P(k)$.

Assumption Step:

Assume that the following statement is true:

If $P(n) \land ( P(m++)\implies P(m))$, then $\forall k \leq n$, $P(k)$

Proving the statmenet for $n++$:

We must prove the follow statement:

If $P(n++) \land (P(m++)\implies P(m))$, then $\forall s \leq n++$, $P(s)$

By assumption, $P(n++)$ is true. Therefore, by the assumed property of $(P(m++)\implies P(m))$, $P(n)$ must also be true.
Due to our previous inductive step (i.e. Assumption Step), we know that if $P(n)$ is true and the property $(P(m++)\implies P(m))$ is true, the statement $\forall k \leq n$, $P(k)$ is true.

Now, if we make a set of all natural numbers that satisfy the condition that $k\leq n$ and compare it to the set of all natural numbers that satisfy the condition that $s\leq n++$, we see that the only difference in elements between these two sets is the element $n++$. So, we still need to demonstrate that $P(n++)$ is true before we can claim that $\forall s \leq n++$, $P(s)$. However, by assumption, we already accept that $P(n++)$ is true.

Therefore, the full implication:

If $P(n++) \land (P(m++)\implies P(m))$, then $\forall s \leq n++$, $P(s)$

is true and the induction is closed.

Cheers~

Answer 1

Your proof is basically correct. A few comments:

• When you write things like $P(n) \land ( P(m++)\implies P(m))$, it's better to make the quantifier explicit, i.e. to write $P(n) \land \forall m( P(m++)\implies P(m))$ instead.
• For the statement you prove using induction, you used "If $P(n) \land ( P(m++)\implies P(m))$, then $\forall k \leq n$, $P(k)$". However, it is slightly cleaner to instead assume $\forall m( P(m++)\implies P(m))$ at the start of the proof, and to prove using induction the following: "If $P(n)$, then $\forall k \leq n$, $P(k)$".
• In comments you mentioned that you avoided starting the base case with $0$ because you wanted to avoid vacuous statements. However, the case for $n=0$ does not actually involve vacuous statements. Indeed, suppose $P(0)$ is true. We want to show $\forall k\leq 0, P(k)$. The only natural number $k$ such that $k \leq 0$ is $k=0$, so we have $P(k)$. This is almost the same reasoning you went through in the $n=1$ case.