5
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ 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}$. $\endgroup$
    – Wojowu
    Mar 2, 2020 at 9:44
  • 3
    $\begingroup$ Indeed, since we can always kill time by enumerating successors while we wait for a given recursive function to converge. $\endgroup$ Mar 2, 2020 at 13:03
  • $\begingroup$ @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]? $\endgroup$
    – SSequence
    Mar 2, 2020 at 13:16
  • 1
    $\begingroup$ @Wojowu In fact, we can bring this down to polynomial-time computability (or indeed even less!) - $\omega_1^{CK}$ is unspeakably robust. $\endgroup$ Mar 2, 2020 at 18:26

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very nice answer! I have to admit though that I am finding it quite difficult to understand the details in your answer due to my lack of understanding. But anyway, the answer to question is still quite useful/informative regardless. [and sry if you have flood of notifications ..... the 5 min. edit time-limit is difficult for me to manage] $\endgroup$
    – SSequence
    Mar 4, 2020 at 18:22

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.