Ordinal numbers reachable by primitive recursive ordinal functions in omega

Question

$ \def \PRo {{\mathcal { PR } _ \omega}} $ The class of primitive recursive ordinal functions in the constant omega function (henceforth denoted by $ \PRo $) are defined by Jensen and Karp (1971) as the smallest class of functions mapping finite tuples of ordinals to ordinals, which contains the constant omega function, the constant zero function, the successor function, the order testing function and all projections, and is closed under substitution and primitive recursion. More precisely, we have the following.

All the initial functions of the following forms are in $ \PRo $:

• $ \Omega ( \alpha ) = \omega $
• $ Z ( \alpha ) = 0 $
• $ S ( \alpha ) = \alpha + 1 $
• $ C ( \alpha , \beta , \gamma , \delta ) = \begin {cases} \alpha & \gamma < \delta \\ \beta & \gamma \ge \delta \end {cases} $
• $ P ^ n _ m ( \alpha _ 1 , \dots , \alpha _ n ) = \alpha _ m $, for all positive integers $ n $ and $ m $ with $ m \le n $

Every function defined by means of the following rules using previously constructed functions in $ \PRo $ is itself in $ \PRo $:

• $ f ( \alpha _ 1 , \dots , \alpha _ m , \beta _ 1 , \dots , \beta _ n ) = g \big( h ( \alpha _ 1 , \dots , \alpha _ m ) , \beta _ 1 , \dots , \beta _ n \big) $
• $ f ( \alpha _ 1 , \dots , \alpha _ m , \beta _ 1 , \dots , \beta _ n ) = g \big( \alpha _ 1 , \dots , \alpha _ m , h ( \alpha _ 1 , \dots , \alpha _ m ) , \beta _ 1 , \dots , \beta _ n \big) $
• $ f ( \alpha _ 1 , \dots , \alpha _ m , \beta ) = g \big( \alpha _ 1 , \dots , \alpha _ m , \sup _ { \gamma < \beta } f ( \alpha _ 1 , \dots , \alpha _ m , \gamma ) \big) $

Let's say an ordinal number $ \alpha $ is $ \PRo $-reachable whenever there is a unary function $ f $ in $ \PRo $ such that $ f ( 0 ) = \alpha $.

My question is how to characterize the $ \PRo $-reachable ordinal numbers. What is the supremum of the $ \PRo $-reachable ordinals? What is the least ordinal not $ \PRo $-reachable? Do they coincide (i.e. is the class of $ \PRo $-reachable ordinals downward closed)?

I have only the simple observation that each $ \PRo $-reachable ordinal must be countable, and as there are only countably many functions in $ \PRo $, not all countable ordinals are $ \PRo $-reachable. I also suspect that there is a connection with $ \omega _ 1 ^ { \text { CK } } $, as $ \PRo $ is recursively defined, but this feeling is a loose one.

---

Jensen, Ronald B.; Karp, Carol, Primitive recursive set functions, Axiomatic Set Theory, Proc. Sympos. Pure Math. 13, Part I, 143-176 (1971). ZBL0221.02027.

Answer 1

According to Jeremy Avigad's "An ordinal analysis of admissible set theory using recursion on ordinal notations" (corollary 4.2), if $\alpha$ is closed under the primitive recursive ordinal functions, $\alpha=\omega$ or $\alpha$ is an output of the Veblen function $\varphi_\omega$. But to get a result about the $\mathcal{PR}_\omega$-reachable ordinals, we need a few more things:

Avigad's formulation of the prim. rec. ordinal functions is a bit different than the one in this question. However, they are equivalent, since both schemes used are equivalent: The composition schemes are equivalent, since Avigad's $f(\vec x)=h(g_1(\vec x),\ldots,g_k(\vec x))$ corresponds to the following repeated application of your question's composition scheme:

$$\begin{eqnarray*}&&h_0=h \\ &&\textrm{For }0<i\le k\textrm{, }h_i(y_1,\ldots,y_k)=h_{i-1}(y_1,\ldots,y_{i-1},g_i(P^i_i(y_1,\ldots,y_i)),y_{i+1},\ldots,y_k) \\ &&f(\vec x)=h_k(x)\end{eqnarray*}$$

And the primitive recursion schemes are equivalent, since $\textrm{sup}_{\gamma<\beta}f(\alpha_1,\ldots,\alpha_m,\gamma)$ is equivalent to Avigad's $\bigcup\{f(u,\vec x)\mid u\in z\}$ (I believe there is a typo in the original - $x$ instead of $\vec x$.) Also, while in this question we have a constant function outputting $\omega$, in Avigad's paper we do not, and in fact $\omega$ is closed under Avigad's prim. rec. ordinal functions.

We can convert this result about closure under prim. rec. ordinal functions into one about $\mathcal{PR}_\omega$-reachability, since if there are prim. rec. ordinal functions $h$, $g$ such that $h(g(0))=\alpha$ for some ordinal $\alpha$, we have a prim. rec. ordinal function with $f(0)=\alpha$ by composition. Also if $\alpha=\omega$, while it's closed under Avigad's prim. rec. ordinal functions, $\mathcal{PR}_\omega$-reachability includes the function $\Omega$, so the least ordinal that's not $\mathcal{PR}_\omega$-reachable is $\varphi_\omega(0)$.

Answer 2

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.

Answer 3

I assume that the answer is contained in Rathjen's article https://www.jstor.org/stable/2275441 The first prim recursively closed ordinal is therefore $\varphi\omega0$. Best, Andreas Weiermann