4
$\begingroup$

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}$ "?

Addendum: Since for each $\varphi$ of true arithmetic, the statement that

there is a $PA_{\omega}$-proof of $\varphi$ whose height is $< \omega^{2}$

is true, one might think that each of those statements is equivalent to the statement that 0=0, and that the answer to both Q2 and Q1 would be that no additional induction must be added to $PA$.

I intend Q1 and Q2 to be using a stronger notion of “equivalent”, so that answers like this are ruled out.

Improve this question
$\endgroup$
3
  • $\begingroup$ (A) Isn't "recursive $\mathit{PA}_\omega$ proof" redundant since you already defined $\mathit{PA}_\omega$ to use the recursive $\omega$-rule? Did I miss something? • (B) Why is it that every sentence of true arithmetic (sanity check: this is the same as "true sentence of arithmetic", right?) have a $\mathit{PA}_\omega$ proof (let alone one of height $<\omega^2$)? $\endgroup$
    – Gro-Tsen
    Commented Mar 9, 2017 at 15:57
  • 4
    $\begingroup$ Concerning (B): this is Shoenfield's completeness theorem (Shoenfield, J. R., 1959, "On a restricted $\omega$-rule", Bulletin de L'Académie Polonaise Des Sciences: Série des sciences mathématiques, astronomiques, et physiques 7:405–407). Shoenfield's original bound was $\omega^\omega$, but this can be improved to $\omega^2$. For details see Franzén, T., 2004, "Transfinite Progressions: A Second Look at Completeness", Bulletin of Symbolic Logic 10(3):367–389. $\endgroup$
    – Benedict Eastaugh
    Commented Mar 9, 2017 at 16:08
  • $\begingroup$ Concerning (A): There are $PA_{\omega}$-proofs that aren’t recursive: ones with too large of an ordinal height. Also, I recognize that the issue raised in Q1 doesn’t perfectly match up with the title, which doesn't mention the recursive $\omega$-rule. $\endgroup$
    – Haidar
    Commented Mar 10, 2017 at 15:10

0

Reset to default

You must log in to answer this question.