Strong induction and vacuous truth

Question

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.

Answer 1

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.

Answer 2

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.