1
$\begingroup$

The notion of a “computable pseudo-ordinal”, i.e. a computable linearly ordered set 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.

My question is, what are the possible order types of a computable linear order with no computable enumerable descending chains? I’m guessing that any such linear order either has no hyperarithmetical descending chains or has order type $\omega_1^{CK}(1+\eta+1)+something$, I’m just not sure what the “something” is.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Since every infinite c.e. set has an infinite computable subset, "no c.e. descending chain" is the same as "no computable descending chain." And almost every linear order which has a computable copy in the first place has a computable copy with no descending chain. For example, it's a standard finite injury construction (in Ash/Knight I think) to build a computable copy of $\omega+\omega^*$ with no computable descending sequence.

(On the other hand there are non-examples; for instance, every computable copy of $\mathbb{Q}$ or $\mathbb{Z}$ will have a computable descending sequence.)


Incidentally, you may be interested in Watnik's A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings. Watnik classifies the computable linear orders $L$ which have a computable copy $M\cong L$ with no computable descending or ascending sequence. (Note that Watnik talks about subsets of $\mathbb{Q}$ as concrete examples of linear orders.)

$\endgroup$
2
  • $\begingroup$ Let me ask you this: suppose we restrict our attention to linear orders with order type of the form $\omega_1^{CK}(1+\eta+1)+something$. Does that constrain how many order types you can get, or can the “something” be almost anything? I’m just trying to make an analogy with the Harrison result. $\endgroup$ Commented Jun 6, 2023 at 7:00
  • $\begingroup$ I posted my follow up question on MathOverflow: mathoverflow.net/q/448551/5017 $\endgroup$ Commented Jun 10, 2023 at 17:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .