Where to find proofs of the following:

1) proof-theoretic ordinal of $I\Sigma_0$, which is Robinson's Q arithmetic with induction on $\Sigma_0$ formulas, is $\omega^2$?

2) proof-theoretic ordinal of $I\Sigma_0+\exp$, which is $I\Sigma_0$ augmented with the fact that exponentiation is total, is $\omega^3$?

3) proof-theoretic ordinal of $I\Sigma_1$, which is Robinson's Q arithmetic with induction on $\Sigma_1$ formulas, is $\omega^\omega$?

Is there any arithmetic (e.g. Robinson's $Q$ with induction on open formulas) with proof-theoretic ordinal less than $\omega^2$?

  • $\begingroup$ I'm not really sure why this has votes to close as "unclear," it is a little vague but I think is still a reasonable question. $\endgroup$ Jun 24, 2017 at 17:21
  • 7
    $\begingroup$ I think this closure was quite silly. Note that of those voting to close,only one appears to have any background in logic. I'm not sure what was unclear about this question - all terms used are standard in the literature, and the issue (that ordinal analysis is quite odd when the theory gets sufficiently weak) is a perfectly understandable one. We don't demand e.g. that a question on algebraic topology define the fundamental group - so what exactly is unclear, here? I've voted to reopen. $\endgroup$ Jun 25, 2017 at 16:33
  • $\begingroup$ @NoahSchweber Thanks, Noah. I really hoped somebody would be able to help. What I can easily find in the literature is about theories stronger than PA. Wikipedia gives some results on weak theories, but without proper citations. I also read "Weak Systems of Arithmetic" by John Baez [golem.ph.utexas.edu/category/2011/10/weak_systems_of_arithmetic.html], but there is nothing substantial there, either. $\endgroup$ Jun 25, 2017 at 22:49
  • 4
    $\begingroup$ George, this is a nice question. If you end up not receiving an answer after a reasonable amount of time (a week or two?), please consider reposting in on MathOverflow. $\endgroup$ Jun 25, 2017 at 23:47

1 Answer 1


While natural theories extending EFA (also called $\mathsf{I}\Sigma_0$+exp or ERA or EA) appear well-ordered under $\Pi^0_2$ provability, the setting of exact $\Pi^0_2$ ordinal values for theories below PRA is a matter of convention. However, a reasonable convention is obtained using the Hardy hierarchy of functions:

  • Set $h_0(x) = x$
  • $h_{\alpha+1}(x) = h_\alpha(x+1)$
  • $h_{\alpha}(x) = h_{\alpha[x]}(x)$ for limit $\alpha$ where $\alpha[..]$ is a canonical fundamental sequence for $\alpha$. The link defines a canonical choice below $\Gamma_0$, but basically we diagonalize over lower indices of $h$ in a reasonable way.

For a theory $T$ including basic arithmetic:

  • $|T|_{\Pi^0_2}$ = sup($\alpha$: $T$ proves $h_α$ is total).

Note that $|T|_{\Pi^0_2}$ formally depends not only on the ordinal but also on the fundamental sequences (and on the formulas defining them). However, for canonical ordinal notation systems, different natural choices of fundamental sequences appear to be equivalent in that for $T$ extending EFA, they give the same $|T|_{\Pi^0_2}$. The reason is that different reasonable choices will give the same growth rate of $h_{\alpha}(x)$ up to an elementary increase or decrease in the value of $x$.

The remarkable property is that for natural theories extending EFA, $\Pi^0_2$ provability is completely determined (and well-ordered) by $|T|_{\Pi^0_2}$. A caveat is that there are different notions of 'natural' (and counterexamples like EFA+Con(PA)), and also many natural theories are beyond known canonical ordinal notation systems.

Now, $h_{\omega m+n}(x)=2^m (x+n)$, and for appropriate $\alpha$ and $\beta$, $h_{\alpha+\beta}(x) = h_\alpha(h_\beta(x))$, and $h_{\alpha\omega}(x)=h_\alpha^x(x)$ (superscript indicates iteration). (The exact equality depends on the choice of fundamental sequences and that $\alpha+\beta$ (resp. $\alpha\omega$) does not truncate $\alpha$.)
For every $m$, $\mathsf{I}\Delta_0$ (also called $\mathsf{I}\Sigma_0$) proves that $2^m x$ is total, but it does not prove that $2^x x$ is total, so the ordinal is $\omega^2$.

$h_{\omega^2 n}$ approximately corresponds to a stack of $n$ exponentials, which is elementary for a particular $n$ but not as a function of $n$, hence the $\omega^3$ ordinal.

$h_{\omega^n}$ approximately corresponds to the $n$th level (or so) of the Ackermann function and thus provably total in PRA, but $h_{\omega^\omega}$ grows like the full Ackermann function, which is beyond PRA. $\Sigma^0_1$-PA (also called $\mathsf{I}\Sigma_1$) is $\Pi^0_2$ conservative over PRA and thus has the same $\Pi^0_2$ ordinal.

A few notes:

  • $\mathsf{I}\Delta_0$ is already interpretable in Robinson arithmetic Q, and there is no standard assignment of ordinals below that.
  • Since total functions are closed under composition, every $|T|_{\Pi^0_2}$ is a power of $\omega$.
  • If we had set $h_{\alpha+1}(x) = h_\alpha(2^x)$, then $|\mathrm{EFA}|_{\Pi^0_2}$ would be $\omega$, hence the caveat about convention.
  • There also are other approaches to ordinals for weak theories, including by embedding the theory into a second order theory using a free second order variable $X$ and extending induction (and other axioms) to formulas using $X$ as a predicate, and getting the $\Pi^1_1$ ordinal of that theory. I think you would still get the $\omega^2$ and $\omega^3$ (and $\omega^\omega$) ordinals, but I have not seen the proof either.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .