$ \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.


2 Answers 2


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)$.

  • $\begingroup$ Sorry for my VERY late response. I wasn't on the site for a VERY long time. This is very clear, at least in showing that $ \varphi _ \omega ( 0 ) $ is a lower bound. Together with the upper bound proposed in the answer by @NoahSchweber, it resolves the problem. $\endgroup$ Nov 14, 2023 at 15:27
  • $\begingroup$ As I'm not much familiar with some of the details involved, I'd like to ask whether there is a "nice" known ordinal notation for all the ordinals less than $ \varphi _ \omega ( 0 ) $. By "nice" I mean something like "given by composition of finitely many nice functions", where nice could be something like primitive recursive. It's rather loose, what I'm asking; but I don't see a better way of formulating a question that helps me understand the ordinals up to $ \varphi _ \omega ( 0 ) $. $\endgroup$ Nov 14, 2023 at 15:33
  • $\begingroup$ @MohsenShahriari Since Noah Schweber mentioned "at a glance, each application of primitive recursion is only going to go 'one level up' ", it may not be the case that there are finitely many functions in $\mathcal{PR}_\omega$ that span $\varphi_\omega(0)$ in this way, if each nice function is eventually dominated by a finite level of the Veblen hierarchy. More specifically I might guess that any function in $\mathcal{PR}_\omega$ whose definition consists of at most $n$ applications of the formation rules will be eventually dominated by $\varphi_n$, but I may need to do more work to prove this. $\endgroup$
    – C7X
    Nov 16, 2023 at 6:54
  • 1
    $\begingroup$ @MohsenShahriari The Veblen hierarchy itself up to $\varphi_\omega(0)$ may be one of the most intuitive. There are some results known about the ordinals $\varphi_n(0)$ for $n<\omega$ specifically (such as those in "Generalized fusible numbers and their ordinals"), but these might not give as much insight into the structure of $\varphi_\omega(0)$ as the Veblen function itself. One possibly helpful fact for intuition is that $\varphi_{n+1}(\alpha+1)=\textrm{sup}\{\varphi_n^k(\varphi_{n+1}(\alpha)):k<\omega\}$, where superscript denotes iterated application. $\endgroup$
    – C7X
    Nov 18, 2023 at 1:51
  • 1
    $\begingroup$ I am also aware of a system based on Beklemishev's worm game claimed to be capable of representing any ordinal $<\varphi_\omega(0)$, however I could not find a proof of the correspondence. $\endgroup$
    – C7X
    Nov 18, 2023 at 1:52

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.

  • $\begingroup$ Thanks for your kind answer. While I still struggle with understanding several parts of it, it seems that the observations still leave open the question of equality of the supremum of reachable ordinals and the smallest non-reachable one. Is there a way for attacking that part of the problem as well? $\endgroup$ Jun 3, 2021 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.