2
$\begingroup$

I was pondering a bit more about this question regarding being able to "omit" the base case in a proof by strong induction due to vacuous truth. The post states:

Strong induction proves a sequence of statements $P(0), P(1), …$ by proving the implication

"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."

for every nonnegative integer $n$. There is no need for a separate base case, because the $n=0$ instance of the implication is the base case, vacuously.

However, if we consider $n=0$, we would have that the statement is vacuously true, which I would take to mean that the implication is true regardless of the validity of $P(0)$. However, clearly it's necessary for $P(0)$ to hold for an induction proof to be valid. So I'm confused on how, by omitting the base case, $n=0$ isn't just a tautology, making the implication true regardless of whether $P(0)$ actually holds.

$\endgroup$
2
  • 2
    $\begingroup$ For $n=0$, the premise ''If P(m) is true for all nonneg. integers m less than 0'' is vacuously true. But its an implication and so you need to prove that P(0) is true. $\endgroup$ – Wuestenfux Jan 2 '19 at 9:29
  • 2
    $\begingroup$ @Wuestenfux Ah, so it isn't the implication that's vacuously true, it's the premise is vacuously true, so since $T \Rightarrow P(0) \Leftrightarrow P(0)$, it precisely boils down to proving $P(0)$? $\endgroup$ – rb612 Jan 2 '19 at 9:32
4
$\begingroup$

Strong (or : complete) induction is :

$(∀n)[(∀m)(m < n \to P(m)) \to P(n)] \to (∀n) P(n)$.

So, in order to conclude with $(∀n) P(n)$ we have to show that : $(∀n)[(∀m)(m < n \to P(m)) \to P(n)]$ holds.

If I understand well, your concern is with $n=0$.

In that case, we have :

$(∀m)(m < 0 \to P(m)) \to P(0)$.

But $(m < 0 \to P(m))$ is vacuously true (there are no $m < 0$). Thus, the conditional amounts to : $\text T \to P(0)$ and there is only one possibility to satisfies it : when $P(0)$ is true.

$\endgroup$
1
  • $\begingroup$ To the proposer: So the assertion that $[\forall m\ge 0\;(m<n\to P(m))]\to P(n)$ holds for all $n\ge 0,$ does imply that the "base-case" $P(0)$ is true. $\endgroup$ – DanielWainfleet Jan 2 '19 at 11:36
1
$\begingroup$

In strong induction, you show that each instance of $P(n)$ can be reduced to one or more cases $P(m)$ with $m<n$, so if all smaller cases are known to be true then case $n$ follows. The distinction from normal induction is that you don't necessarily know what values of $m$ $P(n)$ will reduce to, in particular it is not necessarily $m=n-1$, so you need to know all previous cases. A simple example is to prove that every integer at least $2$ is a product of primes: for a given integer $n\geq 2$, either $n$ is prime (so trivially true) or $n$ is a product of two integers $a,b\geq 2$. Now $a,b<n$, so both are products of primes, and we're done.

In this case there is no need for a separate base case. If $n=2$, what happens is that there are no integers $a,b$ with $2\leq a,b<n$, so the second case above can't happen and $n$ must be prime. Here your reduction to smaller $m$ happens to include a proof of the base case.

However, normally what happens is that the reduction to smaller case(s) doesn't work for the smallest value of $n$, and you do need a separate base case. For example, you might be trying to prove the same statement for $n\geq 1$, and then you need to deal with $n=1$ (the empty product) separately, since the statement that $n$ is prime or can be written as the product of two smaller positive integers doesn't hold for $n=1$.

For any strong induction one of these two things happens. If the proof of the reduction breaks down for $n=0$ (or whatever the minimum $n$ is), you have to do the base case separately; if it doesn't, this gives a reason why $P(0)$ is vacuously true.

$\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.