# Strong induction and vacuous truth

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.

• 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. Jan 2, 2019 at 9:29
• @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)$? Jan 2, 2019 at 9:32

## 2 Answers

$$(∀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.

• 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. Jan 2, 2019 at 11:36

In strong induction, you show that each instance of $$P(n)$$ can be reduced to one or more cases $$P(m)$$ with $$m, 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, 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, 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.