1
$\begingroup$

Kleene’s $O$ is a way to use natural numbers as notations for recursive ordinals. $0$ is a notation for $0$. If $i$ is a notation for $\alpha$, then $2^i$ is a notation for $\alpha+1$. And if $\phi_e$ (the $e^{th}$ partial recursive function) is a total recursive function enumerating ordinal notations in strictly increasing order (as ordinals), then $3\cdot 5^e$ is a notation for the least upper bound of the ordinals denoted by the range of $\phi_e$. The least ordinal which cannot be obtained in this way is the Church-Kleene ordinal $\omega_1^{CK}$.

I’m wondering what happens if you modify the definition of Kleene’s $O$ to allow for oracles. Let $A$ be a subset of $\mathbb{N}$. As before, let $0$ be a notation for $0$, and if $i$ is a notation for $\alpha$, then $2^i$ is a notation for $\alpha+1$. But now if $\phi_e^A$ (the the $e^{th}$ partial recursive function with access to $A$ as an oracle) is a total $A$-recursive function enumerating ordinal notations in strictly increasing order (as ordinals), then let $3\cdot 5^e$ be a notation for the least upper bound of the ordinals denoted by the range of $\phi_e$. Let $O_A$ be the set of all ordinal notations obtained in this way.

My question is, what is the least ordinal which does not have a notation in $O_A$ for any set $A$? Is it $\omega_1$, or is there a countable ordinal with this property?

$\endgroup$
  • $\begingroup$ I think similar questions have been posted on Mathoverflow or this site. Unfortunately, I could not find these questions. $\endgroup$ – Hanul Jeon Nov 8 '19 at 9:24
2
$\begingroup$

Every countable ordinal can be so reached.

This is easiest to see by first switching from notations to general computable relations. Trivially the set of countable ordinals which have a copy computable relative to some oracle is all of $\omega_1$ - given an (infinite) ordinal $\alpha<\omega_1$ just take $A$ to be well-ordering of $\omega$ with ordertype $\alpha$.

We can then pass from this to notations by relativizing the proof that every computable ordinal is constructive (= has length $\vert e\vert_\mathcal{O}$ for some $e\in\mathcal{O}$), the details of which can be found in Sacks' book (I believe he gives the relativization as an exercise).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is there a way to find out the smallest ordinal that can’t be reached by a given oracle? $\endgroup$ – Keshav Srinivasan Nov 8 '19 at 14:47
  • $\begingroup$ @KeshavSrinivasan It's the analogue of $\omega_1^{CK}$. These ordinals are inherently hard to describe, but here's one thing we can say: the smallest ordinal with no $A$-computable copy is the smallest $\alpha$ such that $L_\alpha[A]$ satisfies KP + Infinity. (This is usually denoted "$\omega_1^r$" - but I find that confusing since the same notation is used for what $L[r]$ thinks is $\omega_1$.) Sacks proved that every admissible ordinal $>\omega$ arises as such. $\endgroup$ – Noah Schweber Nov 8 '19 at 14:54
  • $\begingroup$ What does $L_\alpha[A]$ mean? $\endgroup$ – Keshav Srinivasan Nov 8 '19 at 14:57
  • $\begingroup$ It's level $\alpha$ of the constructible hierarchy relativized to $A$; Devlin's book has a good treatment. $\endgroup$ – Noah Schweber Nov 8 '19 at 14:58
  • $\begingroup$ And what about the reverse problem? Given a concrete description of a countable ordinal, is there a way to find a “naturally-occurring” oracle that computes it, as opposed to an oracle specially designed from the ordinal itself? $\endgroup$ – Keshav Srinivasan Nov 8 '19 at 15:11

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.