9
$\begingroup$

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?

$\endgroup$

2 Answers 2

8
$\begingroup$

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

$\endgroup$
4
  • $\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, 2017 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, 2017 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$ Jul 27, 2017 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, 2017 at 9:16
2
$\begingroup$

I don't know whether it would be of enough interest, but here is a relatively simple method for seeing why it must not be true. I posted almost the same method in a question last year (which I later deleted because there was an incorrect assumption in the question).

The method only uses natural numbers. The natural numbers are supposed to represent index of ordinal programs. Let $\lambda$ be the supremum of clocking positions (empty input). We are interested in all ordinals of the form $\beta_i$ such that: (i) $\beta_i$ is addmissible (or limit of admissibles) (ii) the "count" of clocking positions below $\beta_i$ is also equal to $\beta_i$.

Now we simply have a (ordinal) counter $s$ which starts from $0$ and keeps on increasing. At each value of the form $\beta_s$ we have the set $A_s \subseteq \mathbb{N}$ (with $A_0=\mathbb{N}$). Interpreting each $e \in A_s$ as an index of a program from $\beta_s$ to $\{0,1\}$, to form $A_{s+1}$, we remove all those indexes which represent total $\beta_s$-computable functions [total over the domain $\beta_s$] calculating linear-orders (that aren't well-orders). At limit values of $s$, we have $A_s$ formed as intersection of all $A_i$'s where $i<s$. Also, by construction we have $A_i \supseteq A_j$ whenever $i<j$, meaning any element that is removed once from the list is removed permanently.

The main thing to note is that for each value $\beta_i$ we have $sup(\beta_i \mbox{-} \mathrm{computable})$ equal to $sup(\beta_i \mbox{-} \mathrm{zeroComputable})$. Here by latter I mean the supremum of $\beta_i$-computable well-orders without any parameters. Finally, when we have $\beta_{n}=\lambda$ we must have $A_n=A_{n+1}$ [because otherwise we would have a program, on empty input, clocking above $\lambda$]. But now if $\lambda$ was a good ordinal then there would be a $\lambda^+$-computable function from $\alpha<\lambda^+$ [e.g. $\alpha=\lambda+\omega$] to $\lambda^+$ with co-finality $\lambda^+$. If we write the bad ordinals enumerated by this method above as $b_i$ then there one thing that we note is that $b_\omega \neq sup\{b_i|i < \omega\}$.


One slight generalization of this method would be to consider all programs (with parameters) as each suitable stage (ignoring the condition of clocking positions mentioned above). But then we wouldn't have the set $A_s$ as just containing natural numbers, but instead $A_s$ would keep growing as $s$ increases. One benefit of such a method would be that it would show any sufficiently closed ordinal to be bad. For example, on top of $\lambda$ the method would also show $\omega_1$ to be bad.

$\endgroup$
2
  • $\begingroup$ "Interpreting each $e \in A_s$ as an index of a program from $\beta_s$ to $\{0,1\}$, to form $A_{s+1}$, we remove all those indexes which represent total $\beta_s$-computable functions [total over the domain $\beta_s$] calculating linear-orders (that aren't well-orders)." Linear-orders/well-orders on $\beta_s$ that is. $\endgroup$
    – SSequence
    Feb 28, 2020 at 7:40
  • $\begingroup$ Summarizing the argument in the first part of answer in two lines: If there were no bad admissibles then there would exist a $\lambda^+$- computable function from $\lambda+\omega$ to $\lambda^+$ (with cofinality $\lambda^+$) violating the admissibility of $\lambda^+$. In particular, the last statement is implied by $\lambda$ being a good admissible. Hence we must conclude that $\lambda$ is bad. $\endgroup$
    – SSequence
    Feb 29, 2020 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.