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

Solution 1:

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