4
$\begingroup$

I'm broadly interested in problems of the form

Characterize those ordinals $\alpha$ which are not computable from any smaller ordinal

for some meaning of "computable." For example, the admissible ordinals arise as such a class: we have $L_\alpha\models\mathsf{KP\omega}$ iff $Col(\omega,\alpha)$ forces "For every $\beta<\alpha$ there is a copy of $\beta$ not computing any copy of $\alpha$." This is basically due to Sacks (+ a simple absoluteness argument).

The above result, however, uses a somewhat odd notion of "computable." Personally I think it's quite natural, but there's definitely a simpler one coming from higher recursion theory:

Say that an ordinal $\gamma>\omega$ is recursively closed iff for every admissible $\alpha<\gamma$ the supremum of the $\alpha$-recursive well-orderings of $\alpha$ is $<\gamma$.

In general recursively closed $\gamma$s need not be admissible (although of course the converse does hold except for $\omega$); see here. An admissible ordinal $\alpha$ is Gandy if the smallest recursively closed $\gamma>\alpha$ is admissible.

My question is whether we can characterize the recursively closed ordinals by a first-order theory, analogously to how we characterized the "generically Muchnik-incomputable-from-below" ordinals at the beginning of this question:

(Main question) Is there a first-order theory $T$ such that for all $\gamma>\omega$ we have $L_\gamma\models T$ iff $\gamma$ is recursively closed?

It would be enough if - uniformly in a non-Gandy admissible ordinal $\alpha$ - there were an $L_\alpha$-definable well-ordering of $\alpha$ of ordertype the supremum of the $\alpha$-recursive well-orderings of $\alpha$. As such, the following arises as a sub-question of the main question:

(Secondary question) Suppose $\alpha$ is a non-Gandy admissible ordinal. Must there be an $L_\alpha$-definable well-ordering of $\alpha$ which is longer than any $\alpha$-recursive well-ordering?

An affirmative answer to the secondary question would not yield an affirmative answer to the main question immediately, due to the lack of uniformity, but it would probably help. I personally suspect that even the secondary question has a negative answer, but I cannot prove it.

Note that the secondary question has a very strong positive answer for the specific case $\alpha=\omega_1$, since every ill-founded relation on $L_{\omega_1}$ has a descending sequence which is an element of $L_{\omega_1}$, and so in general we get a uniformly positive answer for "sufficiently $\omega_1$-like" ordinals - but this still leaves a large gap between "$\omega_1$-like" and Gandy.

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't fully understand the question so I might be missing something. But writing $\beta_\alpha$ to denote the $\alpha$-th ordinal which is admissible (or a limit of those), it seems that by your definition $\beta_{\omega+1}$ would be "recursively closed". Same for $\beta_{\omega \cdot 2+1}$ etc. Is this intended (in the sense that it doesn't matter for the question)? Or perhaps you wanted to replace "iff for every admissible $\alpha<\gamma$" with "iff for every admissible (or limit of admissibles) $\alpha<\gamma$"? $\endgroup$
    – SSequence
    Commented Aug 19, 2020 at 10:55
  • $\begingroup$ Also, given the definition, it seems you want all ordinals (and obviously many more too) of the form $\beta_l$ (with $l$ being a limit ordinal) to be categorized as "recursively closed". $\endgroup$
    – SSequence
    Commented Aug 19, 2020 at 11:21
  • $\begingroup$ Also, regarding your secondary question, I have a (likely) trivial question about terminology. Is "$L_\alpha$-definable well-ordering of $\alpha$" synonymous to "$\alpha$ (or $L_\alpha$?)-arithmetic well-orderings of $\alpha$"? Anyway, one observation is that there exist countable, recursively inaccessible and non-gandy ordinals $\alpha$ such that, even though $\alpha$ is non-gandy, there exists an ordinal $\alpha<p<\alpha^+$ such that the supremum of $p$-computable well-orderings of $\alpha$ would be exactly equal to $\alpha^+$. But I don't know how $L_\alpha$-definable [continued] $\endgroup$
    – SSequence
    Commented Aug 19, 2020 at 12:04
  • $\begingroup$ would relate to any of this, since I don't have any understanding of it. That's why I don't know how this observation relates to the secondary question. But essentially $p$ would only be "slightly" larger than $\alpha$ though (e.g. $p$ would be very small compared $\alpha$-recursive well-orderings of $\alpha$). Note: Instead of posting another comment (with only one sentence), I deleted the last comment and copy-pasted with an added sentence towards the end. $\endgroup$
    – SSequence
    Commented Aug 19, 2020 at 13:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .