Sneaky Recursive Non-Well-Orders

Question

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:

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?

Answer 1

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

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