3
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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