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

Wikipedia contains the following information in the article "Admissible ordinal":

By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles. [Reference: Friedman, Sy D. (1985), "Fine structure theory and its applications"]

I have found the referenced paper, but I cannot seem to find any reference to this theorem there.

Question: where can I find this theorem? What is its name (or identifier)?

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.

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$$! In particular, 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$$. 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}$$).

• There is one detail here that I want to clarify: assuming that $\alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_\alpha$ of Turing machines is equipped with an oracle for a copy of $\omega_{\alpha}^{\text{CK}}$, can we assume that for any ordinal $\beta < \omega_{\alpha+1}^{\text{CK}}$, there exists the corresponding machine that belongs to $F_\alpha$ and computes $\beta$? – lyrically wicked Feb 1 '19 at 6:34
• @lyricallywicked You seem to be conflating $\omega_{\alpha+1}^{CK}$ (the $(\alpha+1)$th admissible ordinal) and $\omega_1^\alpha$ (the first admissible ordinal $>\alpha$). For example, taking $\alpha=\omega+17$, the first admissible above $\alpha$ is just $\omega_1^{CK}$ but $\omega_{\alpha+1}^{CK}$ is quite huge; this is analogous to $\vert\omega_1+17\vert<\aleph_{\omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...) – Noah Schweber Feb 1 '19 at 13:59
• The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $\alpha$, and $\beta<\omega_1^{CK}(\alpha)$ (that is, $\beta$ is less than the first admissible $>\alpha$). Then must we have $r\ge_Ts$ for some real $s$ coding a copy of $\beta$? ("$a\ge_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $\Phi_e^b=a$.") The answer to this is yes: we clearly have $\omega_1^{CK}(r)>\alpha$, and by the first part of Sacks' theorem we know that $\omega_1^{CK}(r)$ is admissible, so $\omega_1^{CK}(r)>\beta$. Now use the definition... – Noah Schweber Feb 1 '19 at 14:01
• 1/3: no, I am not conflating, your first assumption was right: when I write $\omega_{\alpha+1}^{\text{CK}}$, I mean the $(\alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE. – lyrically wicked Feb 2 '19 at 8:48
• 2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $\omega_1^{\text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $\beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $\beta_1$ equal to $\omega_2^{\text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $\omega_2^{\text{CK}}$, the ordinal $\omega_{\alpha+1}^{\text{CK}}$ could be produced by a similar process. – lyrically wicked Feb 2 '19 at 9:17