One of the nice features of the first admissible ordinal after $\omega$, i.e. $\omega_1^{CK}$, is that it is the collection of ordinals whose order type is that of a computable well-ordering on $\omega$.

Is a similar thing true for all other admissible sets? Specifically suppose $\alpha$ is an admissible ordinal, $\alpha^+$ is the next admissible after $\alpha$ and $\alpha \leq \gamma < \alpha^+$. Is there always an $\alpha$-computable well-ordering on $\alpha$ of order type $\gamma$?

If so can someone also provide a reference for the result?


Surprisingly, no there isn't! See also this paper.

Roughly, if $\alpha$ is sufficiently stable, then the next admissible is much greater than the supremum of the $\alpha$-computable well-orderings of $\alpha$.

Specifically, the relevant fact is:

If $R$ is an illfounded binary relation on $\omega_1$ in $L_{\omega_1}$, then there is an infinite $R$-descending sequence $\sigma$ with $\sigma\in L_{\omega_1}$.

Quick Lowenheim-Skolem arguments show that if $\alpha$ is "sufficiently like" $\omega_1$ (I think $++$-stable is enough), the same is true: if $R$ is an illfounded binary relation on $\alpha$ in $L_{\alpha}$, then there is an infinite $R$-descending sequence $\sigma$ with $\sigma\in L_\alpha$. It's now not hard to show that for such an $\alpha$, the supremum of the order types of $\alpha$-computable well-orderings of $\alpha$ (I'm denoting this by "$\omega_1^G(\alpha)$" in a paper I'm writing - I don't think there's standard notation) is not admissible (hence is $<\alpha^+$).

  • $\begingroup$ The standard terms seems to be "Gandy ordinals" (for those which satisfy the condition demanded by OP). And $++$-stability (plus local countability), is, indeed, sufficient to not to be Gandy: see theorems 6.4 and 6.6 in Simpson's nicely written "Short Course on Admissible Recursion Theory" (in Fenstad, Gandy & Sacks, eds., Generalized Recursion Theory II (Oslo 1977), North-Holland 1978, pages 355‒390). $\endgroup$ – Gro-Tsen Jul 27 '17 at 2:16
  • $\begingroup$ The smallest non-Gandy ordinal $\sigma^1_1$ is also equal to the supremum $\omega_1^{\mathsf{E}_1^\#}$ of the order types on $\omega$ recursive in the nondeterministic version $\mathsf{E}_1^\#$ of the Tugué functional $\mathsf{E}_1$: I can provide a reference for this fact if somebody is interested. $\endgroup$ – Gro-Tsen Jul 27 '17 at 2:25
  • $\begingroup$ @Gro-Tsen Re: terminology, I meant that there seems to be no term for the supremum of the $\alpha$-computable well-orderings of $\alpha$. $\endgroup$ – Noah Schweber Jul 27 '17 at 4:08
  • $\begingroup$ I understand; I was simply trying to get the term "Gandy ordinal" to appear alongside your answer because putting a name on things can help with searches, whether OP's or future people who might find this question this way. Although it must be said that this particular term's standardness seems pretty much limited to the one Abramson&Sacks paper you linked to. $\endgroup$ – Gro-Tsen Jul 27 '17 at 9:16

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.