The highest ordinal that can’t be obtained from Kleene’s O with oracles

computabilityoraclesordinalsset-theoryturing-machines

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?

Best Answer

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).

Related Solutions

Is it possible to construct a model of oracle Turing machines that correspond to $\omega_n^\text{CK}$, where $n$ is greater than $1$

Throughout, by "structure" I mean "countable structure in a computable language." I'm also assuming you're comfortable both with Turing reducibility $\le_T$ - which lets us avoid unnecessary verbiage about machines and oracles - and with the idea of reals coding copies of structures (see SSequence's answer, specifically the $\omega\cdot2$ example).

We begin with the computability side. For $r$ a real, we let $\omega_1^{CK}(r)$ be the smallest ordinal with no $r$-computable copy; equivalently, the supremum of the ordinals which do have $r$-computable copies. For a structure $\mathcal{A}$ we let $\omega_1^{CK}(\mathcal{A})$ be the smallest ordinal not computed by some$^1$ copy of $\mathcal{A}$; precisely, $$\omega_1^{CK}(\mathcal{A})=\min\{\omega_1^{CK}(r):r\mbox{ codes a copy of $\mathcal{A}$}\}.$$
- "$\omega_1^{CK}(r)$" is not how that appears in the literature - rather, you'll see "$\omega_1^r$" - but I strongly prefer it, since it avoids clashing with set-theoretic notation. Note also that we can conflate a real $r\subseteq\omega$ with the structure $\hat{r}$ consisting of the natural numbers with successor and a unary predicate for $r$, and it's easy to check that $\omega_1^{CK}(r)=\omega_1^{CK}(\hat{r})$, so everything lines up nicely.
Next, we look at the admissibility side. For $\alpha$ an arbitrary ordinal, we let $\omega_\alpha^{ad}$ denote the $\alpha$th admissible ordinal: that is, the $\alpha$th ordinal whose corresponding level of $L$ satisfies KP. Note that this definition has nothing to do with computability theory on the face of it (and in fact, doesn't even require $\alpha$ to be countable!). We'll also write "$\omega_1^{ad}(\beta)$" for the first admissible ordinal $>\beta$; in particular, $\omega_1^{ad}(\omega_\alpha^{ad})=\omega_{\alpha+1}^{ad}$.
- Nobody uses this notation, since by Sacks' result it's completely redundant. However, distinguishing at this stage in the game between admissibility concerns and computability concerns is I think very helpful, so I hope you'll forgive me the introduction of soon-to-be-stupid notation.
Now Sacks' result (plus a bit of thought) shows that $$\omega_1^{CK}(\alpha)=\omega_1^{ad}(\alpha)\mbox{ for every countable ordinal $\alpha$}.$$ This is why you never see the "$ad$" notation: it's made completely irrelevant! In particular, "$\omega_\alpha^{CK}$" is just our "$\omega_\alpha^{ad}$."
- Moreover, Sacks' result immediately implies that $\omega_1^{CK}(\mathcal{A})$, being the minimum of a set of admissible ordinals,is itself admissible.
- Also, via forcing we can make sense of this for even uncountable $\alpha$. But that's really a side issue.

$^1$Note the careful quantification over copies here (and the implicit focus on "optimally simple" copies) in our definition of $\omega_1^{CK}(\mathcal{A})$. This is fundamental: different copies of the same structure can behave very differently, and we need to address this if our definitions are to be interesting at all.

Specifically, we can have very simple structures coded by very complicated reals: e.g. "swapping" $2n$ and $2n+1$ whenever $n\in 0'$ gives a copy of $\omega$ which computes $0'$, and more generally we can get copies of $\omega$ of arbitrarily high complexity. In fact, this (almost) always happens. So in order to say anything interesting, we need to talk about what all copies of a given structure can do.

Note: this is what Wojowu's comment "Results due to Sacks imply that with such an oracle we can compute all ordinals below $\omega_2^{CK}$, and for suitable choice of this oracle [typo removed] no larger ordinals will be computable with this oracle." Obviously some copies of $\omega_2^{CK}$, when used as oracles, will let us compute a ton of extra junk; the point is that nothing beyond $\omega_2^{CK}$ is necessarily computable from a copy of $\omega_1^{CK}$.

What we're ultimately getting at here is the idea of reducibilities between structures. Here we're looking just at Muchnik (weak) reducibility: $\mathcal{A}\le_w\mathcal{B}$ if every real coding a copy of $\mathcal{B}$ computes some real coding a copy of $\mathcal{A}$. There are other reducibilities too - most immediately, Medvedev (strong) reducibility - but for these sorts of questions we're really in the Muchnik realm, at least for now.

EDIT: An important point here which I think will substantially clarify things is that Muchnik reducibility extends $\le$ - if $\mathcal{A}\ge_w\alpha$ and $\beta<\alpha$ then $\mathcal{A}\ge_w\beta$. In particular this means that $\omega_1^{CK}(\mathcal{A})$ is both the least ordinal without a copy computable from every copy of $\mathcal{A}$, and the supremum of the ordinals which do have copies computable from every copy of $\mathcal{A}$.

EDIT THE SECOND: And here's a way of constructing such a "sufficiently simple" copy of $\omega_1^{CK}$: a copy of $\omega_1^{CK}$ can be computed straightforwardly from Kleene's $\mathcal{O}$, but$^2$ $\mathcal{O}$ is in $L_{\omega_2^{CK}}$ and so every ordinal with a copy computable from $\mathcal{O}$ is $<\omega_2^{CK}$. All of this requires a bit of familiarity with admissible sets and $L_{\omega_1^{CK}}$ in particular; Sacks' book is as usual a good source on the topic.

Where is the theorem related to the construction of countable admissible ordinals by Turing machines with oracles

S.-D. Friedman's paper mentions Sacks' result on page $265$ (the first page of lecture $3$). It's just a one-line mention, though, so it's not really helpful - and Friedman's bibliography doesn't mention Sacks' paper.

The paper you want is Sacks' Countable admissible ordinals and hyperdegrees - namely, you want the first half of Theorem $4.26$. I don't think it has a name.

Additionally, the paper Note on admissible ordinals by H. Friedman and Jensen contains an alternate forcing-free proof of Sacks' theorem. The volume it's in (Syntax and semantics of infinitary languages) has some delightful material but poorly typeset and a bit hard-to-find.

A couple quick remarks about the result:

The "computability-to-admissibility" half, that $\omega_1^r$ is admissible for all reals $r$, is Exercise VII.$1.13$ in Sacks' higher recursion theory book. It's just the relativized version of showing that $\omega_1^{CK}$ is admissible: you prove that $L_{\omega_1^r}[r]\models$ KP, by exactly the same argument (remember that if $M$ is an admissible set then $L^M=L_{M\cap Ord}$ is also admissible).
There's a quick proof that every successor admissible is the $\omega_1^{CK}$ of some real: namely, if $\beta$ is admissible and $\alpha$ is the next admissible above $\beta$, let $G$ be $Col(\omega,\beta)$-generic over $L_\alpha$. $G$ essentially is an $\omega$-copy of $\beta$, so trivially $\omega_1^G>\beta$; but $Col(\omega,\beta)\in L_\alpha$, set forcing preserves admissibility, and no real in an admissible set computes the height of that admissible set, so we get $\omega_1^G\le\alpha$. This means $\omega_1^G=\alpha$ since $\omega_1^G$ is admissible. So the interesting part is showing that admissible limits of admissibles occur as $\omega_1^{CK}$s.
It's also worth noting that for $\alpha$ admissible, we may indeed need to step outside of $L_\alpha$ to find a real whose $\omega_1^{CK}$ is $\alpha$. In particular, if there is some $r\in L_\alpha$ with $\omega_1^r=\alpha$, then $L_\alpha$ will be locally countable (= $L_\alpha\models$ "every set is countable"). But plenty of countable admissible $\alpha$s don't give rise to locally countable levels of $L$! One way to see that this is plausible is to observe that if $\alpha$ is an admissible limit of admissibles (= "recursively inaccessible"), then every real in $L_\alpha$ is contained in some admissible $L_\beta$ with $\beta<\alpha$ and so no real in $L_\alpha$ can code a copy of $\alpha$, so the "obvious" reason for a level of $L$ to be locally countable doesn't apply to admissible limits of admissibles (although of course many such ordinals do yield locally countable levels of $L$). But there are even successor admissible ordinals not giving rise to locally countable levels of $L$ (take e.g. $\alpha=$ the image of $\omega_1$ under the Mostowski collapse of a countable $M\prec H_{\omega_2}$ and look at the next admissible above $\alpha$).

Best Answer

Related Solutions

Is it possible to construct a model of oracle Turing machines that correspond to $\omega_n^\text{CK}$, where $n$ is greater than $1$

Where is the theorem related to the construction of countable admissible ordinals by Turing machines with oracles

Related Question