# What is the smallest ordinal not computable by using artihmetical truth as an oracle?

Kleene's $$O$$ is a way to use natural numbers as notations for recursive ordinals. I’m wondering what happens if you modify the definition of Kleene’s $$O$$ to allow for arithmetical truth as an oracle. Let $$T$$ be the set of Godel numbers of true statements in the language of first-order arithmetic. Let $$0$$ be a notation for $$0$$, and if $$i$$ is a notation for $$\alpha$$, then $$2^i$$ is a notation for $$\alpha+1$$. If $$\phi_e^T$$ (the $$e^{th}$$ partial recursive function with access to $$T$$ as an oracle) is a total $$T$$-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_T$$ be the set of all ordinal notations obtained in this way.

My question is, what is the smallest ordinal that does not have a notation in $$O_T$$? I realize that ordinal might be difficult to describe exactly, but can we at least put some upper and lower bounds on how big it is?

• I really recommend reading Sacks' book - many of your questions are directly answered in it, and it's freely and legally available online. – Noah Schweber Nov 8 '19 at 17:20
• @NoahSchweber Thanks, I'll check it out. – Keshav Srinivasan Nov 8 '19 at 17:21

It's a theorem of Spector that every hyperarithmetic ordinal is computable (see Sacks' book). True (first-order) arithmetic is tiny in the hyperarithmetic hierarchy, so it doesn't get us any further than $$\omega_1^{CK}$$.

• In fact, a stronger result is true: $$L_{\omega_1^{CK}}\cap\mathcal{P}(\omega)=HYP$$.

(Incidentally, it's also true that every computable ordinal is polynomial-time computable, so $$\omega_1^{CK}$$ is the first non-polytime-computable ordinal and the first non-hyperarithmetic ordinal. It's a really robust notion!)

Note that as usual, it's far simpler to talk about computable ordinals than notations. There are situations where notations are useful, but in my experience more as a tool than the initial definition.

• What do you mean by talking about computable ordinals rather than notations? How do I phrase my question without talking about notations? – Keshav Srinivasan Nov 8 '19 at 17:21
• @KeshavSrinivasan A computable ordinal is an ordinal which has a computable copy: that is, an ordinal $\alpha$ is computable iff ($\alpha$ is finite or) there is some computable binary relation $R$ on $\omega$ which well-orders $\omega$ with ordertype $\alpha$. Similarly, a hyperarithmetic ordinal is one with a hyperarithmetic copy, etc. The classic text for this topic is Ash/Knight Computable structures and the hyperarithmetic hierarchy - unfortunately that one's harder to find. – Noah Schweber Nov 8 '19 at 17:24
• The fact mentioned in my answer to your other recent question - that "constructive" ordinals (= ordinals with notations) and computable ordinals coincide, and that this relativizes - is the key to switching from notations to general copies. In particular, your question can be rephrased as: "What is the least ordinal with no copy computable from true first-order arithmetic?" – Noah Schweber Nov 8 '19 at 17:25
• Cool, Ash/Knight is the textbook of the logic course I'm taking next semester. – Keshav Srinivasan Nov 8 '19 at 17:27
• Does truth in the language of first-order set theory in the standard model of $ZFC$ get you anywhere higher than the Church-Kleene ordinal? Or is "the standard model of $ZFC$" too vague to answer that? – Keshav Srinivasan Nov 8 '19 at 17:31