What's the strength of weakening induction in PA by relativizing it to naturals?

25 Views Asked by At

If we weaken induction in PA to the following scheme:

$\forall m [\phi(0) \land \forall n < m (\phi(n) \to \phi(n+1)) \to \forall n \leq m (\phi(n))]$

Where $\phi$ is any formula in the language of PA.

Then how much that would weaken PA?

1

There are 1 best solutions below

0
On BEST ANSWER

This is equivalent to the usual induction scheme. Indeed, suppose a formula $\phi$ satisfies $\phi(0)$ and $\forall n(\phi(n)\to\phi(n+1))$. Given any $m$, then, $\phi(0)$ and $\forall n<m(\phi(n)\to\phi(n+1))$ are true, and therefore by your scheme, $\forall n\leq m(\phi(n))$. In particular, $\phi(m)$ is true. Since $m$ was arbitrary, we conclude $\forall m(\phi(m))$.