4

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?

Robert Shore
  • 23,332
JCAL
  • 234
  • 1
  • 12
  • 1
    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. – Aditya Guha Roy Mar 25 '21 at 00:47

2 Answers2

4

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)".

Robert Shore
  • 23,332
Asinomás
  • 105,651
  • 1
    It’s really not so weird: when doing transfinite induction one not infrequently finds that the base case need not be handled separately. – Brian M. Scott Mar 25 '21 at 00:48
  • That makes sense but I have never seen transfinite induction. – Asinomás Mar 25 '21 at 00:54
  • 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? – JCAL Mar 25 '21 at 18:26
  • @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. – Asinomás Mar 25 '21 at 21:08
  • @Asinomás I find you are the first one to say that you need to prove the base case in the same way it is proved with normal induction. Whereas tao and other answers seem to suggest P(0) is true so you don't need to prove it. I'm struggling with it and wonder if you can take a look https://math.stackexchange.com/q/4691291/291153 – eugene May 03 '23 at 05:59
  • your question seems to be about the proof of strong induction ( something I don't have experience with ), while this question is moreso about the application of it. – Asinomás May 03 '23 at 11:49
1

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.

Robert Shore
  • 23,332