Skip to main content
2 of 3
edited tags
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

the strength of saying "each sentence of true arithmetic has a recursive proof"

Let $PA_{\omega}$ be just like $PA$ except that $PA_{\omega}$-proofs can use any number of applications of the recursive $\omega$-rule.

The recursive $\omega$-rule allows the following:

For each formula $\varphi$ with one free variable, if there is a unary total recursive function $f$ such that $\forall n \in N$, $f(n)$ is the code of a proof of $\varphi(\overline{n})$, then we may conclude $\forall x \ \varphi(x)$.


Each sentence of true arithmetic has a recursive $PA_{\omega}$-proof of height $<\omega^{2}$. Saying that the proof is recursive means that it can be coded by a total recursive function.

Assuming a canonical encoding of ordinals,

Q1: How much transfinite induction must be added to $PA$ so that for each sentence $\varphi$ of true arithmetic, the resulting system proves something equivalent to "there is a recursive $PA_{\omega}$-proof of $\varphi$"?

Q2: How much transfinite induction must be added to $PA$ so that for each sentence $\varphi$ of true arithmetic, the resulting system proves something equivalent to "there is a recursive $PA_{\omega}$-proof of $\varphi$ whose height is $< \omega^{2}$ "?

Haidar
  • 449
  • 2
  • 8