Skip to main content
1 of 3
user76284
  • 2.2k
  • 15
  • 24

They are not always equivalent. Consider the ordinal numbers. Strong induction

$$\forall x (\forall y (y < x \rightarrow P y) \rightarrow P x) \rightarrow \forall z P z$$

holds, but weak induction

$$\forall x (P x \rightarrow P x^+) \rightarrow P 0 \rightarrow \forall z P z$$

does not. For example, consider $P x = x < \omega$.

user76284
  • 2.2k
  • 15
  • 24