# What is the highest ordinal that can’t be obtained from Kleene’s O with oracles?

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?

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

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).
• @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. – Noah Schweber Nov 8 '19 at 14:54
• What does $L_\alpha[A]$ mean? – Keshav Srinivasan Nov 8 '19 at 14:57
• It's level $\alpha$ of the constructible hierarchy relativized to $A$; Devlin's book has a good treatment. – Noah Schweber Nov 8 '19 at 14:58