# Strong induction in first order logic

I'm a bit confused with the first-order statement which defines the strong induction in the answer to this question Strong induction and vacuous truth:

$$(\forall n)[(\forall m)(m < n \rightarrow P(m)) \rightarrow P(n)] \rightarrow (\forall n)P(n)$$

It made sense to me when I first looked at it, but then I played with some examples and realized that even if $$P(m)$$ was false, we would have that this statement $$(\forall n)[\forall m(m < n \rightarrow P(m)) \rightarrow P(n)]$$ would be true vacuously, since $$m < n \rightarrow P(m)$$ would be false. Therefore as I understand since that is true, then we can conclude that $$(\forall n)P(n)$$.

I know for sure that I'm missing something, so that's why I'm writing this question - to figure out what I'm missing and why my conclusions are wrong.

• Which $m$? The variable $m$ is universally quantified: it does not denote a particular natural number. In English the expression simply says that if $P(n)$ is true whenever $P(m)$ is true for all $m<n$, then $P(n)$ is true for all $n$. (Here $m$ and $n$ are understood to range only over $\Bbb N$.) Aug 26 '20 at 16:49
• I'm sorry, I just wanted to say that if for any $n$, $P(m)$ doesn't hold for each $m$, where $m < n$, the statement $(\forall n)[(\forall m)(m < n \rightarrow P(m)) \rightarrow P(n)]$ is going to be true. Is it even possible? I also think that I probably don't understand something in this first-order logic statement, but I can't realize what I don't understand. Everything seems reasonable Aug 26 '20 at 16:57

It's good to work through twisty logical examples like this!

When $$n=0$$ (and $$m$$ is a nonnegative integer):

• The inequality $$m<0$$ is vacuously false.
• Thus the implication $$m<0 \to P(m)$$ is vacuously true.
• Since $$m$$ was arbitrary, the universal statement $$\forall m (m<0 \to P(m))$$ is true.
• Therefore the implication $$\forall m (m<0 \to P(m)) \to P(0)$$ is equivalent to $$P(0)$$ itself.

In other words, $$P(0)$$ being true is one of the necessary hypotheses to be checked during strong induction.

Related comment: other than providing a practice problem for those learning logic, the fact that this particular phrasing of strong induction is so confusing is great evidence that it's a terrible way to phrase strong induction. We writers of math get fooled sometimes into thinking that the goal of writing math is to use as few symbols as possible; that's incorrect—the goal of writing math is to communicate. Having the $$m=0$$ case separate (just including $$P(0)$$ in the hypotheses) is much clearer for the reader than making them go through this exercise.

• Thank you, this is useful and now I think I understand this better, but my question was a little different. In fact, I was worried about that first-order statement, namely if $m < n \rightarrow P(m)$ is false at least for one $m$ for each $n$, then $(\forall m)(m < n \rightarrow P(m))$ is false and, therefore, $(\forall n)[(\forall m)(m < n \rightarrow P(m)) \rightarrow P(n)]$ is vacuously true. Does it mean that $(\forall n)(P(n))$ is true? Aug 26 '20 at 17:17
• If it were indeed the case that for every $n$ there existed an $m$ for which $m<n \to P(m)$ is false, then your inference would be correct—the principle of strong induction would imply that $\forall n P(n)$ is true. However, this situation is impossible, since there cannot exist such an $m$ when $n=0$. Aug 26 '20 at 17:50
• I see, this first order statement drives me crazy. Before it I felt comfortable working with implications, quantifiers etc. So I made a conclusion for myself that a text definition of a strong induction (with base case) is much more convenient and have no confusing points. It just says that for all $m < n$ we know $P(m)$ holds, then we should show that $P(n)$ also holds and that's it. Anyway, thank you for your help. That was useful! Aug 26 '20 at 18:06