Skip to main content
3 of 3
added 1544 characters in body
Noah Schweber
  • 20.7k
  • 10
  • 111
  • 332

For each $n\in\omega$ let $(\varphi_i^n)_{i\in\omega}$ be some "reasonable" enumeration of the $n$-ary $PR_\omega$ functions. It's easy to check that the functions $$F_n: (a,b_1,...,b_n)\mapsto \varphi^n_a(b_1,...,b_n)$$ are uniformly-in-$n$ $\Delta_1$-definable over $L_{\omega_1^{CK}}$ (although we're only interested in $F_0$, the right way to prove this is to define all of them simultaneously).

Now looking at $n=1$ specifically, consider the function $$G:\omega\rightarrow\omega_1^{CK}: a\mapsto F_1(a,0).$$ This is $\Delta_1$ over $L_{\omega_1^{CK}}$, so by $\Sigma_1$ Replacement we have $\sup(ran(G))<\omega_1^{CK}$.

(We can recast the above in terms of ordinal notations and $\Sigma^1_1$ bounding, but personally I find that thinking in terms of definability over admissible sets is ultimately simpler.) Morally speaking, any "short" hierarchy of ordinals which only involves simply-defined total operations will fall short of $\omega_1^{CK}$.

Of course I've omitted basically all the details here, since they get rather tedious. The development of hyperarithmetic theory and $\omega_1^{CK}$-recursion theory is treated quite nicely in Sacks' book. The key point is the "closedness" of $\omega_1^{CK}$, either in the sense of $\Sigma^1_1$ bounding or in the sense of admissibility; the appropriate definability of the $PR_\omega$ operations in either case is annoying but not hard (it follows the proof that classical primitive recursive functions are $\Delta_1$ definable).


OK, so what is the supremum in question? The following is a bit speculative:

The relevant thing to look at is the Veblen hierarchy. At a glance, each application of primitive recursion is only going to go "one level up," and so $\phi_\omega(0)$ is a reasonable guess. (Note that $\epsilon_0=\phi_1(0)$, so $\phi_\omega(0)$ is going to be quite large by many standards). But I haven't had time to check the details on this.

I am more confident that the Feferman-Schutte ordinal $\Gamma_0$ is an upper bound. This is because the basic theory of $PR_\omega$-functions - specifically, their totality, appropriately phrased - should be developable in the theory $\mathsf{ATR}_0$. This gives the proof-theoretic ordinal of $\mathsf{ATR}_0$, which is $\Gamma_0$, as an upper bound. Again, this is a very coarse argument which should apply to any "simple" hierarchy of ordinals - but "simple" is more limited here than in the $\omega_1^{CK}$ analysis of course.

Noah Schweber
  • 20.7k
  • 10
  • 111
  • 332