Can you solve any induction problem with base case 0

inductionproof-explanationsolution-verification

A book I'm reading introduces a dummy principle called the "Weak Principle of Mathematical Induction", which is simply the Principle of Mathematical Induction, with the base case $n_0$ fixed at $0$. The book claims that any problem solvable by the Principle of Mathematical Induction is also solvable by the Weak Principle of Mathematical Induction. It provides the following question:

enter image description here

A lot of problems solved by induction are presented as:

For all $n \geq x$, show P(n)

Traditional induction would start at the base case $n_0 = x$, and only apply P to values $n \geq x$ to show that $P(n) \rightarrow P(n + 1)$ proves that $P(n)$ holds for all $n \geq x$.

However, this Weak Principle seems very general to me actually in that speaks in terms of all $n$, not limited to $n > 0$, which confuses me. At first, I thought the way to get around this was that if a given problem states that $P$ should only be applied to values $n > 0$, then maybe $P(0)$ is vacuously true, just as $P(x) \rightarrow P(x + 1)$ where $x \leq 0$ would be. But I don't think that's the correct approach.

The only thing I can think of is that the answer relies on the idea of re-indexing that this answer explains, to basically re-index any induction problem such that the base case is $0$. Then furthermore $P(n) \rightarrow P(n + 1)$ is:

  • Is always true for $n \geq 0$, assuming the problem is solvable by traditional induction
  • Is vacuously true for for $P(n)$ that is false, i.e., $n$ that $P$ is not meant to be applied to, given the problem statement

Does this approach make sense? I'd appreciate thoughts and perspectives on this. If this is the right approach, then I think I need to understand re-indexing a bit more. The example in the answer I linked to above makes sense because it is so simple…but it is hard to see that it always works with very complicated predicates, i.e., that involve summations etc.

Best Answer

First of all, there is an implicit assumption in your Weak Principle of Induction that $P(n)$ is a predicate defined on the natural numbers (integers $n \ge 0$). Likely if you carefully read the context where you found this, it will actually say somewhere that they are dealing with predicates defined on integers greater than or equal to the base case. So when it says "for all $n$" it actually means "for all integers $n \ge 0$".

Second, note that your Weak Principle explicitly states "$P(0)$ is true" as one of the hypotheses. So it is not a case that "$P(0)$ is vacuously true". That $P(0)$ is true is something you have to show explicitly for your predicate before you can apply this "Weak Principle".

As Gerry Myerson has pointed out, the equivalence is just a matter of re-indexing. If all you knew was the weak principle, and you have a predicate $P(n)$ defined on all integers $n \ge x$ where $x$ is some arbitrary integer. And if you can prove both that $P(x)$ is true, and that for all $n \ge x, P(n) \implies P(n+1)$, then you can show $P(n)$ is true for all $n \ge x$ as follows:

  • Define the predicate $Q(m) = P(m + x), m\ge 0$
  • $Q(0) = P(x)$. Since $P(x)$ is true, so is $Q(0)$.
  • $Q(m) \equiv P(m + x) \implies P((m + x) + 1) \equiv Q(m + 1)$, so $Q(m) \implies Q(m+1)$ for all $m \ge 0$.
  • By the weak principle, $Q(m)$ is true for all $m\ge 0$.
  • That is, $P(m + x)$ is true for all $m \ge 0$.
  • Setting $n = m + x, P(n)$ is true for all $n \ge x$.

There is a stronger version of induction. That version is probably where you got the idea of $P(0)$ being "vacuously true". That version (for natural numbers) is

If $P(n)$ is defined for $n \in \Bbb N$, and if $\forall n\in \Bbb N, (\forall m < n, P(m)) \implies P(n)$, then $\forall n \in \Bbb N, P(n)$.

This is stronger than the versions you have been discussing, since there are predicates $P$ for which just knowing $P(n-1)$ is not enough to show $P(n)$, but for which knowing $P(m)$ for every $m < n$ is enough to show $P(n)$. Such predicates can be proven always true from this version of induction, but not using the versions you gave.

You may note that there is no explicit mention of a base case in this version. But this version still has a base case. It is just that the induction case implies the base case, so it doesn't need to be mentioned separately. Since there is no $m < 0$ in $\Bbb N$, the statement $\forall m < 0, P(m)$ is "vacuously" true. And therefore if the induction case has been shown true, $P(0)$ must also be true.

Note that it is "$\forall m < 0, P(m)$" that is "vacuously true" (true because there is no $m < 0$ rather than any property of $P$), not $P(0)$, for which the phrase "vacuously true" has no definition. $P(0)$ is just a consequence of the vacuous truth.

Related Question