8
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ " I am familiar with both strong induction and ordinary induction" Complete strong induction is strong induction. $\endgroup$ – fleablood Oct 9 '18 at 16:00
  • $\begingroup$ @fleablood yea, of course because of $P(m), m<n$, but I'd never seen before that the base cases were "automatically true" given a correct inductive step. As far as I've seen it must be show they are true, because of the Modus Ponens (MP) argument I sketched in my question. $\endgroup$ – Charlie Parker Oct 9 '18 at 16:03
  • 1
    $\begingroup$ Your statement "If n=0 then $P(m),m<n\implies P(n)$ is false" is incorrect (when interpreted properly); in fact, $P(m),m<0\implies P(0)$ vacuously true (since there can't be a counterexample). $\endgroup$ – Noah Schweber Oct 9 '18 at 16:15
  • 2
    $\begingroup$ There is some heavy abuse of commas going on in the formalism here. When one knows what's supposed to be going on, one can reconstruct which meaning each of the commas is trying to express. To a reader who doesn't already know what is going on, it must be completely opaque. $\endgroup$ – Henning Makholm Oct 9 '18 at 20:53
  • 1
    $\begingroup$ I'm no expert but it looks like we're carefully discriminating between a) p is true if there's a preceding example, and b) p is true if there's no preceding counterexample. $\endgroup$ – samerivertwice Oct 10 '18 at 1:54
11
$\begingroup$

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 \tag{1}$$

So, if you have shown that:

$$\text{for any } n: \text{ if } P(m) \text{ holds for any } m<n, \text{ then } P(n) \tag{2}$$

then in particular you have shown that:

$$\text{ if } P(m) \text{ holds for any } m<0, \text{ then } P(0) \tag{2'}$$

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.

$\endgroup$
  • $\begingroup$ yea I think I came to this realization. $P(m)$ holds for $m<0$ holds true vacuously on its own. I think in fact is more clear if we write that out as an explicit implication $q(0) := \forall m (m<0 \to P(m) )$. Then $q(0)$ is true because $m<0$ is false. $\endgroup$ – Charlie Parker Oct 10 '18 at 1:05
  • 1
    $\begingroup$ @CharlieParker Right! Glad you realized this yourself :) $\endgroup$ – Bram28 Oct 10 '18 at 1:09
  • 1
    $\begingroup$ Actually, I wish I did...someone pointed out that my interpretation of $\forall m (m < n \land P(m) )$ was incorrect and that the correct thing was to consider $\forall m (m < n \to P(m) )$. Then I realized the rest by myself...I have no idea why I thought the logical AND was the interpretation. Probably because of my horrible use of comma's. Thanks to everyone! :) $\endgroup$ – Charlie Parker Oct 10 '18 at 1:12
  • 1
    $\begingroup$ @CharlieParker: Yes if you want to understand the logical structure you should always express it (whether explicitly or mentally) in logical form. Commas or other English syntax will hinder. Also, don't forget brackets to make clear what is quantified. Strong induction for a property $P$ is that from "$\forall n \in \mathbb{N}\ ( \forall m \in \mathbb{N}\ ( m<n \to P(m) ) \to P(n) )$" you can deduce "$\forall n \in \mathbb{N}\ ( P(n) )$". $\endgroup$ – user21820 Oct 10 '18 at 7:47
  • $\begingroup$ Where you write $(2')$ does this mean: "There does not exist $m<0$ such that $\lnot P(m)$ then..."? As opposed to "$\exists m<0:P(m)$ then...", from which the conclusion would not follow? $\endgroup$ – samerivertwice Oct 10 '18 at 17:05
13
$\begingroup$

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.

$$\begin{align} \Rightarrow\,\color{#c00}{ P(0)}\\ P(0)\Rightarrow\, P(1)\\ P(0),P(1)\Rightarrow\, P(2)\\ \vdots\qquad\ \ \ \ \\ P(0),P(1),\ldots,P(k-1)\,\Rightarrow\,P(k)\\ \end{align}\qquad\qquad\qquad\qquad\ \ $$

While a valid inductive proof necessarily implies a proof of $\,\color{#c00}{P(0)},\,$ this may not occur explicitly. Rather, it may be a special case of a much more general implication derived in the proof. For example, in many such proofs the natural base case(s) is not a single number but rather a much larger set. Let's examine a simple induction where the base cases are all odd naturals.

If $n\ge\color{#c00}1$ is an integer then $\,n = 2^{\large i} j\, $ for some odd $j$ and some integer $i\ge 0.\,$ For if $n$ is odd then $n = 2^0 n,\,$ else $\,n = 2k\,$ for $\,1 \le k < n\,$ so induction $\,\Rightarrow k = 2^{\large i} j,\,$ so $\, n = 2k = 2^{\large i+1} j.\ \ $ QED

Here the base case $\color{#c00}{P(1)}$ is not explicitly proved. Instead it is a special case of the more general inference that $\,n\,$ odd $\,\Rightarrow\, n = 2^0 n.\,$ In such factorization (decomposition) problems the natural base cases are all irreducibles (and units) - not only the $\rm\color{#c00}{least}$ natural in the statement, e.g. in the proof of existence of prime factorizations of integers $\,n > 1,\,$ with base cases being all primes.

Remark $\ $ Ditto for its contrapositive form infinite descent: $\, $ 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.

$\endgroup$
  • $\begingroup$ what if the inductive step (that only proves the implcation $\forall m (m<n\ to P(m)) \to P(n)$ assume implicitly $n \not = 0$ by saying assume $m < n$ or pick an element from the non-empty set? I think in those cases then you wouldn't actually have the base case for free: "In this method it is, however, vital to ensure that the proof of P(m) does not implicitly assume that m > 0, e.g. by saying "choose an arbitrary n < m" or assuming that a set of m elements has an element." quoting wikipedia: en.wikipedia.org/wiki/… $\endgroup$ – Charlie Parker Oct 10 '18 at 0:59
  • $\begingroup$ @CharlieParker I recommend that you focus on some specific examples in your question. Then it will be much easier to be precise. $\endgroup$ – Bill Dubuque Oct 10 '18 at 1:17
  • $\begingroup$ @CharlieParker I added a couple specific examples that show clearly that the base case may not be explicitly proved in the induction. $\endgroup$ – Bill Dubuque Oct 10 '18 at 15:18
  • $\begingroup$ Bill, do you have an example? I don't. It's just theoretical/abstract right now. I agree a concrete example would be fantastic! $\endgroup$ – Charlie Parker Oct 10 '18 at 17:06
  • $\begingroup$ @CharlieParker As I said, I just added some examples to my answer - see above. $\endgroup$ – Bill Dubuque Oct 10 '18 at 17:43
5
$\begingroup$

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 m\in\{0,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 m\in \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 $$\top\implies P(0),$$ where $\top$ is always true. If you prove that $\top\implies 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.)

$\endgroup$
  • $\begingroup$ This seems to be the core of the OP's misunderstanding; other answers seem to skip over why P(0) is true and take it for granted. $\endgroup$ – Yakk Oct 9 '18 at 18:01
  • $\begingroup$ Yea, I've realized that was key, the correct thing to consider $\forall m (m < n \to P(m) )$. After thats cleared up it becomes much easier. $\endgroup$ – Charlie Parker Oct 10 '18 at 1:07
4
$\begingroup$

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

$$\bigl((\forall m\in\{0,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…

$\endgroup$
  • $\begingroup$ doesn't change anything about my confusion because I was always assuming $m<n$ meant $\forall m, m<n$, since $n$ was a free variable. I've fixed it I guess. $\endgroup$ – Charlie Parker Oct 9 '18 at 16:15
  • 3
    $\begingroup$ the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) \implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically? $\endgroup$ – Charlie Parker Oct 9 '18 at 16:18
  • 1
    $\begingroup$ Jose, if you see the Wikipedia and Quora link I gave it claims complete strong induction does NOT explicitly need the base cases proven. Which is what I'm puzzled about. $\endgroup$ – Charlie Parker Oct 9 '18 at 16:24
  • 1
    $\begingroup$ "the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't? $\endgroup$ – fleablood Oct 9 '18 at 16:52
  • 2
    $\begingroup$ @fleablood In one form of strong induction, the base case is a special case of the induction hypothesis. See Bill Dubuque’s answer. Or am I misunderstanding what the argument is about? $\endgroup$ – spaceisdarkgreen Oct 9 '18 at 17:04
3
$\begingroup$

You write:

If $n=0$ then $ \forall m, m < n, P(m) \implies P(n) $ is False.

This is where you are wrong. As you noticed, $ \forall m, m < 0, P(0)$ is (vacuously) true. But that does not mean that the above statement is false, indeed

$\forall m, m < 0, P(m) \implies P(0)\quad $ is equivalent to $\quad P(0)$.

(If you doubt this: $\mathrm{true}\rightarrow x \iff \neg \mathrm{true} \lor x \iff \mathrm{false} \lor x \iff x$.)

So in complete induction you actually have to show $P(0)$, there is just no reason to list it separately from the implications that you have to show.

Stated differently: In complete induction, for each $n$ you show $P(n)$, but you are allowed to use all $P(m)$ for $m < n$ in the proof of $P(n)$. For $n=0$ this does not allow you anything new as there is no $m<0$.

$\endgroup$
0
$\begingroup$

I think I finally understand my confusions after reading the Wikipedia article more carefully and getting my notation right. First recall what the inductive step (that we have to prove) is in induction:

$$ \varphi(n) := \forall m (m < n \to P(m)) \to P(n) $$

what complete strong induction claims to my understanding is that the proof of the inductive step includes the base case automatically because the argument also holds for the base cases, $P(0)$ for example. So now define:

$$ q(n) := \forall m (m < n \to P(m)) $$ $$ p(n) := P(n) $$ so:

$$ \varphi(n) = q(n) \to p(n) $$

if we assume we prove the inductive step and that argument holds for every $n$ including the base case then we have:

$$ \varphi(0) = q(0) \to p(0) $$

is true as a whole. However, if we carefully examine what $q(0)$ is we notice that it's a tautology, i.e.

$$ q(0) = \forall m (m < 0 \to P(m))$$

because $m < 0$ is False because $m \in \mathbb N = \{ 0,1,2,3,\dots\}$ (i.e. $0<0$,$1<0,2<0\cdots$ is always false), so $(m < 0 \to P(m))$ is True for all values of m in consideration. So now we know $\varphi(0) = q(0) \to p(0)$ is True and $q(0)$ is True as a stand alone logical sentence (this is not usually true). So we have:

$$ q(0)$$ $$ q(0) \to p(0)$$

and it follows by modus ponens (MP):

$$ p(0) $$

which eventually results in the cascading of logical implications usual to induction.

Note however that the inductive step, depending on the content of the proof might or might NOT prove the base case automatically. For example, Wikipedia made a good job of outlining why we need to be careful:

In this method it is, however, vital to ensure that the proof of P(m) does not implicitly assume that m > 0, e.g. by saying "choose an arbitrary n < m" or assuming that a set of m elements has an element.

The second case that talks about sets is important to note because we also have structural induction and the argument might depend on selecting an element from a set, which is possible only if the set is non-empty to start with.

So, if you're unsure, prove the base cases, but you can do complete induction if you're sure your proof does include $m=0$ as well as $m>0$.

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