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$) :
- show P(0)
- show implication $ P(n-1) \implies P(n) $
or for strong induction
- show P(0)
- show implication $ \forall m, m < n, P(m) \implies P(n) $
However, in complete induction we only show:
- $ \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