# How far does this restricted definition on $\mathcal{O}$ goes?

$$\mathcal{O}$$ notation describes an onto function $$f:\mathcal{O} \rightarrow \omega_{CK}$$. In calculating all values $$n \in \mathbb{N}$$ such that $$f(n)=\alpha$$, when $$\alpha$$ is a limit, all indexes $$e$$ of ordinary programs are considered such that $$\phi_e(i)=n_i$$ (with $$i \in \mathbb{N}$$). The values $$n_i$$ must satisfy the condition that $$f(n_i)=\alpha_i$$ with the $$\alpha_i$$'s forming a (fundamental) sequence for $$\alpha$$.

I am just interested in the variation where we don't consider indexes of normal programs but instead consider indexes of primitive recursive functions/programs (given a suitable indexing for them).

(Q1) How far would such a variation go? That is, what is the smallest ordinal it can't represent.

(Q2) Consider the notation system (described by a 1-1 function $$g:\beta \rightarrow \mathbb{N}$$) assigning a unique number to each ordinal in which on limit values $$\alpha<\beta$$ we seek the p.r. function with smallest index $$e$$ satisfying $$\phi_e(i)=g(\alpha_i)$$ where the $$\alpha_i$$'s must form a (fundamental) sequence for $$\alpha$$.

At what value $$\beta$$ would such a system stop?

I don't have proficiency with the underlying theory so if the question seems posed in a strange manner then that might be the reason.

• If I recall correctly, every computable ordinal is an order type of a primitive recursive well-order. So the primitive recursive variant also goes all the way up to $\omega_1^{CK}$. Mar 2, 2020 at 9:44
• Indeed, since we can always kill time by enumerating successors while we wait for a given recursive function to converge. Mar 2, 2020 at 13:03
• @DanTuretsky I have a small additional question. Would the system such as one in (Q2) also go to $\omega_{CK}$ [both for p.r. and ordinary programs]? Mar 2, 2020 at 13:16
• @Wojowu In fact, we can bring this down to polynomial-time computability (or indeed even less!) - $\omega_1^{CK}$ is unspeakably robust. Mar 2, 2020 at 18:26

For Q2, the answer is $$\omega^2$$, for both recursive and primitive recursive notations. It's not hard to see that every ordinal below $$\omega^2$$ can be reached.
To show that $$\omega^2$$ cannot be reached, the argument is the same for both primitive recursive and full recursive. For each $$a$$, we construct a $$b$$ ensuring that $$a$$ is not a notation of this sort for $$\omega^2$$. We will construct $$b$$ knowing its own index. For recursive notations, this is an application of the recursion theorem. For p.r. notations, even though we don't have the recursion theorem, this is still possible so long as we're willing to specify an a priori p.r. bound on the runtime. Since we intend to kill time by enumerating successors, an exponential bound will be fine.
Our first goal is to arrange that $$b$$ codes $$\gamma+\omega$$, where $$\gamma$$ is greatest such that some $$c < b$$ with $$c <_\mathcal{O} a$$ codes $$\gamma$$. So we unwrap the notation $$a$$ while enumerating successors. As soon as we see some $$c < b$$ with $$c <_{\mathcal O} a$$ and $$|c|$$ larger than any of the others yet seen, a c.e. event, we include $$c$$ in the sequence we're enumerating.
As soon as we see $$b <_\mathcal{O} a$$, we do something to ensure that $$b$$ is not a valid notation, e.g. break the monotonicity of our sequence.
If $$a$$ is a notation for $$\omega^2$$ with $$b \not <_\mathcal{O} a$$, then $$\gamma+\omega < |a|$$, and $$b$$ is the least notation for $$\gamma+\omega$$ (for any smaller notation would be included in the definition of $$\gamma$$, contradicting our choice of $$\gamma$$). So if $$a$$ is a notation of the desired sort for $$\omega^2$$, then $$b <_\mathcal{O} a$$. But then $$b$$ is not a notation, by construction, so $$a$$ is not a notation.