0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$.) $\endgroup$ Aug 26 '20 at 16:49
  • $\begingroup$ 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 $\endgroup$ Aug 26 '20 at 16:57
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Aug 26 '20 at 17:17
  • $\begingroup$ 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$. $\endgroup$ Aug 26 '20 at 17:50
  • $\begingroup$ 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! $\endgroup$ Aug 26 '20 at 18:06

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.