0

I want to prove that strong induction implies regular induction. Is my attempt correct:

Let $J\subseteq\mathbb{N}$ be a set such that $1\in J$ and $k\in J$ for all $k<n$ implies $n\in J$. Consider the set $S=\{n\in\mathbb{N}\mid n\in J\text{ and }(k<n\to k\in J)\}$. Clearly $1\in S$ so suppose $n\in S$. Then, let $i<n+1$. Clearly either $i=n$ or $i<n$. Either way, since $k<n$ implies $k\in J$, we see that $i\in J$ but then by our assumption at the beginning it follows that $n+1\in J$ which by regular induction implies $J=\mathbb{N}$.

Andrés E. Caicedo
  • 79,201
Adam
  • 742
  • In your question title you want to show that strong induction implies "regular" induction, but the argument in the body seems to be proving that regular induction implies strong induction. Is that the intention? – hmakholm left over Monica Sep 03 '18 at 22:11
  • I was taught that $(1\in H\wedge (n\in H\to (n+1)\in H))\to H=\mathbb{N}$ is strong induction. – Adam Sep 03 '18 at 22:13
  • x @Adam: The usual meaning of the words "strong induction" is $[\forall n : (\forall k<m: k\in H)\to n\in H] \to H=\mathbb N$. (This is a stronger claim because it is easier to use, because the induction hypothesis tells you more in the induction step than the induction hypothesis in regular induction does). – hmakholm left over Monica Sep 03 '18 at 22:26
  • Beware that the usual $n\in H\to n+1\in H$ induction is "regular" only in the sense of being the induction usually taught first. "Regular" is not a technical term here, and in particular not related to "regularity" (as in the set-theoretical axiom of regularity). – hmakholm left over Monica Sep 03 '18 at 22:35

0 Answers0