1
$\begingroup$

The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive paper on them in 1968, showing that any such linear order is either well-ordered or has order type $\omega_1^{CK}(1+\eta)+\alpha$ for some computable ordinal $\alpha$, where $\eta$ is the order type of the rationals.

As a result, any computable linear order with an initial segment of order type $\omega_1^{CK}(1+\eta+1)$ cannot be without hyperarithmetical descending chains. But my question is, does there exist a computable linear order with an initial segment of order type $\omega_1^{CK}(1+\eta+1)$ and no computable descending chains? If there’s more than one, what are all the possible order types of such a linear order?

Improve this question
$\endgroup$
3
  • $\begingroup$ The first sentence of your second paragraph is wrong: remember that $1+\eta+1$ is isomorphic to an initial segment of $1+\eta$, and so a Harrison order does have an initial segment of type $\omega_1^{CK}(1+\eta+1)$. $\endgroup$
    – Noah Schweber
    Commented Jun 10, 2023 at 17:24
  • $\begingroup$ In particular, $\eta+1+\eta\cong\eta$. $\endgroup$
    – Noah Schweber
    Commented Jun 10, 2023 at 17:31
  • $\begingroup$ @NoahSchweber Hmm, then I think I should reformulate my question in some way. What I really want the initial segment to be is a path through $O^*$, the pseudo-ordinal nonstandard extension of Kleene’s $O$ obtained by intersecting all hyperarithmetical sets satisfying the defining conditions of Kleene’s $O$. Tell me this: does a path through $O^*$ have any properties characterizing it that other linear orders of order type $\omega_1^{CK}(1+\eta+1)$ do not? Maybe being $\Sigma^1_1$-complete? $\endgroup$
    – Keshav Srinivasan
    Commented Jun 10, 2023 at 17:34

0

Reset to default

You must log in to answer this question.