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](http://en.wikipedia.org/wiki/Kleene%27s_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:


1. $H\_a = \emptyset$ if $a=0$
2. $H\_a = {H\_b}'$ if $a=2^b$
3. $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?
> 
> 
> 



Sneaky Recursive Non-Well-Orders
In the classic paper [Recursive pseudo-well-orderings](http://www.ams.org/journals/tran/1968-131-02/S0002-9947-1968-0244049-7/S0002-9947-1968-0244049-7.pdf), [TAMS 131 (1968), 526–543](http://www.ams.org/journals/tran/1968-131-02/S0002-9947-1968-0244049-7/home.html), Joe Harrison showed that one can in fact do much better: there are computable linear orderings which are not wellordered but have no [hyperarithmetic](http://en.wikipedia.org/wiki/Hyperarithmetical_theory) 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 


* $x \neq 0 \to 0 \prec x$,
* $x \prec 2^x$,
* $\phi\_e(n){\downarrow} \to \phi\_e(n) \prec 3\cdot5^e$, and
* $x \prec y \land y \prec z \to x \prec z$.


Harrison's $\mathcal{O}^\*$ is the intersection of all *hyperarithmetic* sets $X$ with the following properties.


* $0 \in X$.
* If $a \in X$ then $2^a \in X$.
* If $\phi\_e$ is total ${\prec}$-increasing and the range of $\phi\_e$ is contained in $X$, 
then $3\cdot5^e \in X$.


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}$.


