Background
An ordinal $\alpha$ is called a recursive ordinal if there is a recursive well-order $R$ on $\mathbb{N}$ such that ordertype($\mathbb{N},R) = \alpha$. For example, $\omega\cdot 2$ is a recursive ordinal because the ordering of $\mathbb{N}$ as 0, 2, 4, 6, 8, … 1, 3, 5, 7, … is computable and has order type $\omega\cdot 2$.
Kleene encoded the recursive ordinals in the natural numbers in a nifty way which is described at the Wikipedia page on Kleene's O. Now Kleene's $\mathcal{O}$ is a fairly powerful set — given a Turing machine index for a linear order, $\mathcal{O}$ can decide whether that ordering is a well-ordering or not.
Using Kleene's $\mathcal{O}$, it is possible to describe how to iterate the Turing jump through the recursive ordinals. For each natural number $a\in\mathcal{O}$, we can define a set $H_a$ recursively as follows:
- $H_a = \emptyset$ if $a=0$
- $H_a = {H_b}'$ if $a=2^b$
- $H_a = \{\langle n, x \rangle | x \in H_{\phi_e(n)} \}$ if $a = {3\cdot 5^e}$
For each $a\in \mathcal{O}$, we have $H_a$ <$_T \ \mathcal{O}$ (strict inequality), and no $H_a$ is powerful enough to decide which recursive orders are well-orders.
Question
Among recursive non-well-orders, some hide their descending chains better than others do.
For example, if we only wanted to flag the non-well-orders sporting a recursive descending chain, the full power of $\mathcal{O}$ would not be necessary — $\emptyset'''$ would do $(\exists e [ \phi_e$ is total and $\forall n [\ \phi_e(n+1)$ <$_R\ \phi_e(n)\ ]]$?). Thus there is a recursive linear non-well-order with no recursive descending chain.
In fact (by similar reasoning), for each $a \in \mathcal{O}$ there must be a recursive linear non-well-order with no recursive-in-$H_a$ descending chain.
I wonder whether we could effectively construct these sneaky recursive non-well-orders.
Is there a recursive function $f$ such that whenever $a\in\mathcal{O}$, $f(a)$ is a Turing index for a linear non-well-order with no $H_a$ -computable descending chain?
Best Answer
In the classic paper Recursive pseudo-well-orderings, TAMS 131 (1968), 526–543, Joe Harrison showed that one can in fact do much better: there are computable linear orderings which are not wellordered but have no hyperarithmetic descending sequences. An index for such a linear ordering satisfies your requirements simultaneously for all $a \in \mathcal{O}$.
Here is a sketch of Harrison's argument. First note that the ordering of $\mathcal{O}$ has a c.e. extension ${\prec}$ to all of $\mathbb{N}$, namely the smallest relation such that
Harrison's $\mathcal{O}^*$ is the intersection of all hyperarithmetic sets $X$ with the following properties.
Since Kleene's $\mathcal{O}$ is the intersection of all sets $X$ with the above properties, we have $\mathcal{O} \subseteq \mathcal{O}^*$. Also, every property of $\mathcal{O}$ translates to a property of $\mathcal{O}^*$ by restricting all second-order quantifiers to range over hyperarithmetic reals, provided that all axioms used in the proof of the property remain valid when all quantifiers are replaced in the same way. Since $\Sigma^1_1$ dependent choice holds in the hyperarithmetic world, this includes a lot of properties of $\mathcal{O}$ including the fact that the initial intervals $I_n = \{x : x \prec n\}$ are computable linear orderings that have no hyperarithmetic descending sequences.
Harrison shows that $\mathcal{O}^*$ is (complete) $\Sigma^1_1$. Since $\mathcal{O} \subseteq \mathcal{O}^*$ is complete $\Pi^1_1$, we must have some $n \in \mathcal{O}^* \setminus \mathcal{O}$. Then the initial interval $I_n = \{x : x \prec n\}$ is a computable non-wellfounded linear ordering without hyperarithmetic descending sequences. In fact, one can show that $\mathcal{O} \cap I_n$ is a path through $\mathcal{O}$ and that $I_n$ has order-type $\omega_1^{CK}(1+\eta) + \alpha$ where $\eta$ is the order type of the rationals and $\alpha < \omega_1^{CK}$.