Skip to main content
added 3 characters in body
Source Link

It is not true that inductionInduction and strong induction, or what I would prefer to call the least number principle, are not equivalent formula by formula relative to, say, the standard algebraic axioms $\text{PA}^-$ underlying PA expressing that the structure is a discretely ordered semiring whose least element is $0$. However, induction for the class of all $\Sigma_n$ formulas is equivalent to the least number principle for the class of all $\Sigma_n$ formulas for each $n$.

Let me give a few details.

For a formula $\phi(x)$ define $$I(\phi) := (\phi(0) \& (\forall x)(\phi(x) \to \phi(x+1))) \to (\forall x)\phi(x)$$

while $$L(\phi) := (\exists x) \neg \phi(x) \to (\exists y)(\neg \phi(y) \& (\forall z < y) \phi(z))$$

It is easy to see that $\text{PA}^- \vdash L(\phi) \to I(\phi)$ while $\text{PA}^- \vdash I(\tilde{\phi}) \to B(\phi)$ where $\tilde{\phi}(x) := (\forall y \leq x) \phi(y)$.

If $\phi$ is of class $\Sigma_n$ (expressible as a formula with $n$ alternations of unbounded quantifiers starting with $\exists$ and then a string of bounded quantifiers followed by a quantifier free formula) then while $\tilde{\phi}$ not explicitly $\Sigma_n$, it is equivalent to a $\Sigma_n$ formula. Thus, relative to $\text{PA}^-$, we have a level by level equivalence of these principles.

It is fairly easy to see by considering structures that are not well-ordered that no formula by formula equivalence can be expected.

It is not true that induction and strong induction, or what I would prefer to call the least number principle, are equivalent relative to, say, the standard algebraic axioms $\text{PA}^-$ underlying PA expressing that the structure is a discretely ordered semiring whose least element is $0$. However, induction for the class of all $\Sigma_n$ formulas is equivalent to the least number principle for the class of all $\Sigma_n$ formulas for each $n$.

Let me give a few details.

For a formula $\phi(x)$ define $$I(\phi) := (\phi(0) \& (\forall x)(\phi(x) \to \phi(x+1))) \to (\forall x)\phi(x)$$

while $$L(\phi) := (\exists x) \neg \phi(x) \to (\exists y)(\neg \phi(y) \& (\forall z < y) \phi(z))$$

It is easy to see that $\text{PA}^- \vdash L(\phi) \to I(\phi)$ while $\text{PA}^- \vdash I(\tilde{\phi}) \to B(\phi)$ where $\tilde{\phi}(x) := (\forall y \leq x) \phi(y)$.

If $\phi$ is of class $\Sigma_n$ (expressible as a formula with $n$ alternations of unbounded quantifiers starting with $\exists$ and then a string of bounded quantifiers followed by a quantifier free formula) then while $\tilde{\phi}$ not explicitly $\Sigma_n$, it is equivalent to a $\Sigma_n$ formula. Thus, relative to $\text{PA}^-$, we have a level by level equivalence of these principles.

It is fairly easy to see by considering structures that are not well-ordered that no formula by formula equivalence can be expected.

Induction and strong induction, or what I would prefer to call the least number principle, are not equivalent formula by formula relative to, say, the standard algebraic axioms $\text{PA}^-$ underlying PA expressing that the structure is a discretely ordered semiring whose least element is $0$. However, induction for the class of all $\Sigma_n$ formulas is equivalent to the least number principle for the class of all $\Sigma_n$ formulas for each $n$.

Let me give a few details.

For a formula $\phi(x)$ define $$I(\phi) := (\phi(0) \& (\forall x)(\phi(x) \to \phi(x+1))) \to (\forall x)\phi(x)$$

while $$L(\phi) := (\exists x) \neg \phi(x) \to (\exists y)(\neg \phi(y) \& (\forall z < y) \phi(z))$$

It is easy to see that $\text{PA}^- \vdash L(\phi) \to I(\phi)$ while $\text{PA}^- \vdash I(\tilde{\phi}) \to B(\phi)$ where $\tilde{\phi}(x) := (\forall y \leq x) \phi(y)$.

If $\phi$ is of class $\Sigma_n$ (expressible as a formula with $n$ alternations of unbounded quantifiers starting with $\exists$ and then a string of bounded quantifiers followed by a quantifier free formula) then while $\tilde{\phi}$ not explicitly $\Sigma_n$, it is equivalent to a $\Sigma_n$ formula. Thus, relative to $\text{PA}^-$, we have a level by level equivalence of these principles.

It is fairly easy to see by considering structures that are not well-ordered that no formula by formula equivalence can be expected.

Post Made Community Wiki
Source Link

It is not true that induction and strong induction, or what I would prefer to call the least number principle, are equivalent relative to, say, the standard algebraic axioms $\text{PA}^-$ underlying PA expressing that the structure is a discretely ordered semiring whose least element is $0$. However, induction for the class of all $\Sigma_n$ formulas is equivalent to the least number principle for the class of all $\Sigma_n$ formulas for each $n$.

Let me give a few details.

For a formula $\phi(x)$ define $$I(\phi) := (\phi(0) \& (\forall x)(\phi(x) \to \phi(x+1))) \to (\forall x)\phi(x)$$

while $$L(\phi) := (\exists x) \neg \phi(x) \to (\exists y)(\neg \phi(y) \& (\forall z < y) \phi(z))$$

It is easy to see that $\text{PA}^- \vdash L(\phi) \to I(\phi)$ while $\text{PA}^- \vdash I(\tilde{\phi}) \to B(\phi)$ where $\tilde{\phi}(x) := (\forall y \leq x) \phi(y)$.

If $\phi$ is of class $\Sigma_n$ (expressible as a formula with $n$ alternations of unbounded quantifiers starting with $\exists$ and then a string of bounded quantifiers followed by a quantifier free formula) then while $\tilde{\phi}$ not explicitly $\Sigma_n$, it is equivalent to a $\Sigma_n$ formula. Thus, relative to $\text{PA}^-$, we have a level by level equivalence of these principles.

It is fairly easy to see by considering structures that are not well-ordered that no formula by formula equivalence can be expected.