mjhjmtu

I recently learned about complete strong induction. I am familiar with both strong induction and ordinary induction and make sense. But what particularly confuses me is why we do not to explicit the base cases for complete induction. They seem crucial for modus ponens to work and thus, actually show the stand alone proposition $p(n)$ to be true.

The claim for complete induction seems to be the following:

if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)

These are my thoughts:

In induction we actually do two things (to show $ P(n) $ for all $ n in mathbb N$) :

1. show P(0)


2. show implication $ P(n-1) implies P(n) $
   

or for strong induction

1. show P(0)


2. show implication $ forall m, m < n, P(m) implies P(n) $
   

However, in complete induction we only show:

1. $ forall m, m < n, P(m) implies P(n) $

now that I’ve thought of it more carefully, what bothers me is that in the inductive step we actually only show an implication is true, not that $P(n)$ is true. Intuitively, $P(n)$ ends up true because of Modus Ponens (MP), which forcibly requires checking some set of base cases, say $P(0)$.

What concerns me is the following: ff we show $ forall m, m < n, P(m) implies P(n) $ then we shown the implication is true, and not necessarily anything else. If $n=0$ then $ forall m, m < n, P(m) implies P(n) $ is False. So sure, the implication is (vacuously) true, but that doesn’t necessarily say $P(0)$ is true stand alone (which is what induction ultimately cares about!).

My assumption is that the claim the wikipedia article does is that (somehow) whatever proof for $ forall m, m < n, P(m) implies P(n) $ that we have must also be a stand alone proof for $P(0)$. I guess I could abstractly believe that’s true (mostly on faith), but it seems rather odd to me. I’ve never seen False implies $P(n)$ implies $P(n)$. It’s nearly like the truth table for implication is built so that if you only know the antecedent is False, then you can’t decide if the consequent is true. Which makes sense. A false starting point should intuitively get you no where or get you everywhere (by principle of explosion).

So my question is, whats going on? Is it just that the proof for $ forall m, m < n, P(m) implies P(n) $ can also be plugged in for a proof for $P(0)$ and then $P(0)$ is true? Or am I missing something?

I have a feeling that this being so abstract makes it hard to be believable and a concrete example of how $ forall m, m < n, P(m) implies P(n) $ automagically makes $P(0)$ (the base cases) true would be really valuable.

Another useful source:

https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction

if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)

Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:

$$P(m) text holds for any m<0 tag1$$

So, if you have shown that:

$$textfor any n: text if P(m) text holds for any m<n, text then P(n) tag2$$

then in particular you have shown that:

$$text if P(m) text holds for any m<0, text then P(0) tag2'$$

and so we get

$$P(0)$$

by Modus Ponens on $(1)$ and $(2')$

So, there is indeed no need to prove an explicit base case.

That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!

In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.

A valid proof by complete induction includes a uniform proof for all $k$ of the inferences listed below. As such it include a (vacuous) proof of the base case $color#c00,P(0).,$ Examine the schema carefully to see it.

$qquadqquadqquad beginalign
Rightarrow,color#c00 P(0)\
P(0)Rightarrow, P(1)\
P(0),P(1)Rightarrow, P(2)\
vdotsqquad \
P(0),P(1),ldots,P(k-1),Rightarrow,P(k)\
endalign$

Remark $ $ Its contrapositive form (infinite descent) is clearer: if given a counterexample $lnot P(n)$ we can prove there exists a smaller counterexample $lnot P(k), k < n,,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $,Bbb N,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal one ("minimal criminal"), contra the proof yields a smaller one.

if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)

It's not clear exactly how one ought to interpret "$P(m), m<n implies P(n)$",
but I think we have agreed that the following formula
(shown in the answer by José Carlos Santos)
represents the induction step according to the article:
$$((forall min0,1,2,ldots,n-1) P(m))implies P(n).$$

You seem to be looking at this and saying that for the case $n = 0,$
it is equivalent to $$bot implies P(n),$$
using $bot$ as a symbol for something that is always false.
This implication is vacuously true.
But in fact, a statement of the form
$$ (forall min emptyset) P(m) $$
is also vacuously true. That is, it is true because there is no value of $m$ that can make it false.
This may be a little more obvious if you write it this way:
$$ (forall m)(m in emptyset implies P(m)). $$

So what the induction step of complete induction actually says in the case $n = 0$ is that
$$topimplies P(0),$$
where $top$ is always true. If you prove that $topimplies P(0),$ you have proved $P(0).$

You might question whether the Wikipedia article does a good job of explaining itself, and I would sympathize. It's only an encyclopedia article, however;
a self-evident justification for everything may be too much too ask.
(Useful inline citations for details such as this are not too much to ask, however, and there is a notice at the top of that section of the article requesting them.)

You did not describe strong induction correctly; there's a quantifier missing. The second step should be:

$$bigl((forall min0,1,2,ldots,n-1):P(m)bigr)implies P(n).tag1$$

So, you prove that if $P(0)$, $P(1)$, …, $P(n-1)$, then $P(n)$ holds too. Why should this work? Suppose that you have proved $P(0)$ and also that $(1)$ holds. Then:

• Since $P(0)$ holds, $P(1)$ holds, by $(1)$.


• Since $P(0)$ and $P(1)$ hold, $P(2)$ holds, by $(1)$.


• Since $P(0)$, $P(1)$, and $P(2)$ hold, $P(3)$ holds, by $(1)$.

And so on…