Skip to main content
More readable with parentheses
Source Link
john
  • 101
  • 2

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

$$\forall x (\forall y (y < x \rightarrow \varphi y) \rightarrow \varphi x) \rightarrow \forall z \varphi z$$$$\forall x (\forall y (y < x \rightarrow \varphi (y)) \rightarrow \varphi (x)) \rightarrow \forall z~ \varphi (z)$$

holds, but weak induction

$$\forall x (\varphi x \rightarrow \varphi x^+) \rightarrow \varphi 0 \rightarrow \forall z \varphi z$$$$\forall x (\varphi (x) \rightarrow \varphi (x^+)) \rightarrow \varphi (0) \rightarrow \forall z ~\varphi (z)$$

does not. For example, consider $\varphi x \equiv x < \omega$$\varphi (x) \equiv x < \omega$.

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

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

holds, but weak induction

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

does not. For example, consider $\varphi x \equiv x < \omega$.

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

$$\forall x (\forall y (y < x \rightarrow \varphi (y)) \rightarrow \varphi (x)) \rightarrow \forall z~ \varphi (z)$$

holds, but weak induction

$$\forall x (\varphi (x) \rightarrow \varphi (x^+)) \rightarrow \varphi (0) \rightarrow \forall z ~\varphi (z)$$

does not. For example, consider $\varphi (x) \equiv x < \omega$.

added 53 characters in body
Source Link
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$$$$\forall x (\forall y (y < x \rightarrow \varphi y) \rightarrow \varphi x) \rightarrow \forall z \varphi z$$

holds, but weak induction

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

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

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$.

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

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

holds, but weak induction

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

does not. For example, consider $\varphi x \equiv x < \omega$.

Source Link
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$.

Post Made Community Wiki by user76284