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

316 Views Asked by At

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

1

There are 1 best solutions below

12
On BEST ANSWER

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