4
$\begingroup$

Terrence Tao formulates strong induction as follows: "(Strong principle of induction). Let $m_o$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number 𝑚. 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' \lt 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$. "

Since we are assuming that $P(m')$ is true for all $m_0 \leq m' \lt m$. Where in this statement does it suggest to prove the base case first? To me all its suggesting is to simply suppose $P(m')$ is true for all $m_0 \leq m' \lt m$ without proving a base case?

$\endgroup$
1
  • 1
    $\begingroup$ one classic example for understanding the various ingredients in this description of strong form of mathematical induction is the fundamental theorem of arithmetic which says that every positive integer $n \ge 2$ can be written as a product of primes which is also unique up to rearrangement; here you have to verify the result for $n=2$ as the base case, and then it is easy to see that if we consider the result to be true for each $k \in \{2,3,......, m \}$ for some $m$ then $m+1$ is either a prime or divisible by a prime; using the (strong) induction hypothesis then proves the claim. $\endgroup$ Mar 25, 2021 at 0:47

2 Answers 2

4
$\begingroup$

Well, it seems to be a bit weird. But he is saying that the base case comes in when you prove the inductive condition when $m=m_0$. Which is a bit strange because in this case the hypothesis is vacuous, so essentially you have to prove the base case. So the author covers this point in the part " (In particular, this means that $P(m_0)$ is true since in this case, the hypothesis is vacuous)".

$\endgroup$
4
  • 1
    $\begingroup$ It’s really not so weird: when doing transfinite induction one not infrequently finds that the base case need not be handled separately. $\endgroup$ Mar 25, 2021 at 0:48
  • $\begingroup$ That makes sense but I have never seen transfinite induction. $\endgroup$
    – Asinomás
    Mar 25, 2021 at 0:54
  • $\begingroup$ So in general we never have to prove the base case in Tao’s strong induction because it will be vacuously true everytime? Or is it just vacuously true in this particular statement? $\endgroup$
    – JCAL
    Mar 25, 2021 at 18:26
  • $\begingroup$ @JCAL no, it means that the first inductive step is the same thing as the base case, because you are going from the empty set to the set containing only $m_0$. So you need to prove the base case in the same way it is proved with normal induction. $\endgroup$
    – Asinomás
    Mar 25, 2021 at 21:08
1
$\begingroup$

This is often a useful approach for using induction to prove a statement's contrapositive. Assume toward a contradiction that $P(m)$ is false for some $m$. Then there must be a least $m$ for which it is false. Tao's implication, though, demonstrates that if $P(m')$ is true for all smaller $m'$, then it must also be true for $P(m)$, which means that $m$ was not in fact the smallest possible counterexample, establishing a contradiction.

Thus, the set of counterexamples to $P(m)$ has no least element and therefore must be empty.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.