2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ 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$? $\endgroup$ – lyrically wicked Feb 1 '19 at 6:34
  • $\begingroup$ @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 ...) $\endgroup$ – Noah Schweber Feb 1 '19 at 13:59
  • $\begingroup$ 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... $\endgroup$ – Noah Schweber Feb 1 '19 at 14:01
  • $\begingroup$ 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. $\endgroup$ – lyrically wicked Feb 2 '19 at 8:48
  • $\begingroup$ 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. $\endgroup$ – lyrically wicked Feb 2 '19 at 9:17

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.