0
$\begingroup$

So I began to read Terry Tao's "Analysis 1" and I got confused by his strong induction formulation. The way he puts it is: "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$. " Now I didn't understood his explanation why it means $P(m_0)$ is true. Can you please clarify it for me ?

$\endgroup$
2
  • $\begingroup$ If the predicate holds after some stage, it must hold after the initial stage. I think this is what it means. $\endgroup$ Jul 30 '18 at 17:44
  • $\begingroup$ $P(m_0)$ is the base case in either of the examples. Nothing stands without the base. When someone asks you why you think what you think, you'll tell him there is a based argument pro, not just insinuation. $\endgroup$
    – Invisible
    Jan 10 '20 at 0:38
4
$\begingroup$

It's just that if you take $m=m_0$, then there is no $m'$ with $m_0\leq m' <m$ (because this inequality becomes $m_0\leq m' <m_0$). That means $P(m')$ is true for all such $m'$ that exist.

That's why he says "the hypothesis is vacuous."

$\endgroup$
2
  • $\begingroup$ Now I understand, thanks for the explanation and answer. $\endgroup$ Jul 30 '18 at 17:48
  • $\begingroup$ I will accept your answer as soon as it will be possible. $\endgroup$ Jul 30 '18 at 17:49

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.