7
$\begingroup$

I'm considering the natural numbers to be the nonnegative integers. The principle of strong induction can be stated as follows,

"If $P$ is a property such that for any $x$, if $P$ holds for all natural numbers less then $x$, then $P$ holds for $x$ as well, then $P$ holds for all natural numbers $x$."

This doesn't require a base case. My question is why? Shouldn't $P$ hold for $0$ for the induction to work?

$\endgroup$
1

3 Answers 3

5
$\begingroup$

$P$ holds vacuously for every natural number smaller than $0$. Hence by the induction hypothesis, $P$ holds for $0$.

$\endgroup$
2
  • $\begingroup$ This is wrong! You need to show that $P$ holds for $0$ given the inductive hypothesis that it holds for all natural numbers smaller than $0$. So for the $0$ case the inductive hypothesis holds vacuously, but it does not follow from this that $P$ holds for $0$. You still need to demonstrate that! $\endgroup$
    – Bram28
    Jul 13, 2017 at 16:37
  • 1
    $\begingroup$ But if we prove the inductive step i.e., $\forall n\in \mathbb N( \forall k\in \mathbb N(k<n\implies P(k))\implies P(n))$, we have effectively also proven the base case since for $n=0$, the statement is $$\forall k\in \mathbb N(k<0\implies P(k))\implies P(0)$$ which is the same as $\top\implies P(0)$ which indicates that $P(0)$ must hold. $\endgroup$
    – Jamāl
    Feb 11, 2021 at 15:21
3
$\begingroup$

If you know that $P$ holds for $x$ whenever $P$ holds for all $y$ with $y < x$, then the special case for $x = 0$ tells you that $P$ holds for $0$. This is because there are no $y < 0$, and so $P$ holds for all $y$ with $y < 0$ is vacuously true.

$\endgroup$
2
$\begingroup$

Indeed strong induction does not require an explicit base case. However, for the case of $0$ the induction hypothesis is vacuously true, which provides no information. Therefore, the proof for $0$ must effectively by done from scratch.

It might be that the same proof that works for the general case also works for the case $0$, and for that case indeed produces a proof from scratch. Cases where there is really a uniform proof that does not require any special consideration for $0$ are quite rare however.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .