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?

  • $\begingroup$ I really recommend reading Sacks' book - many of your questions are directly answered in it, and it's freely and legally available online. $\endgroup$ – Noah Schweber Nov 8 '19 at 17:20
  • $\begingroup$ @NoahSchweber Thanks, I'll check it out. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ What do you mean by talking about computable ordinals rather than notations? How do I phrase my question without talking about notations? $\endgroup$ – Keshav Srinivasan Nov 8 '19 at 17:21
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Nov 8 '19 at 17:24
  • $\begingroup$ 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?" $\endgroup$ – Noah Schweber Nov 8 '19 at 17:25
  • $\begingroup$ Cool, Ash/Knight is the textbook of the logic course I'm taking next semester. $\endgroup$ – Keshav Srinivasan Nov 8 '19 at 17:27
  • $\begingroup$ 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? $\endgroup$ – Keshav Srinivasan Nov 8 '19 at 17:31

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.