# Sneaky Recursive Non-Well-Orders

## 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?

-
Minor typo: you mean $\omega\cdot 2$ rather than $2\omega$, since the latter is equal to $\omega$ under the usual ordinal arithmetic, which takes $\alpha\beta$ to mean $\beta$ copies of $\alpha$. – Joel David Hamkins Jul 5 '10 at 17:43

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

-
Here's an alternative argument for the same result. It is a known result (of Spector and Gandy, if I remember correctly) that a universal quantifier over hyperarithmetic reals amounts to an existential quantifier over arbitrary reals (not counting number quantifiers). So the set of codes of recursive linear orders with no hyperarithmetic descending sequence is $\Sigma^1_1$. But the set of codes of recursive well-orders is complete $\Pi^1_1$. Therefore the two sets differ. – Andreas Blass Jul 5 '10 at 18:27
Andreas, this is how Harrison shows that $\mathcal{O}^*$ is $\Sigma^1_1$. It appears that this argument was known to Feferman and Spector (maybe Gandy too) prior to Harrison's thesis (under Feferman). It's not clear to me how much about $\mathcal{O}^*$ was known before Harrison, though he is credited for much of what is known. – François G. Dorais Jul 5 '10 at 18:48
Any idea what $\mathcal{O}^{*}$ amounts to inside the effective topos? I convinced myself once that $\mathcal{O}$ is the object of trichotomous ordinals, i.e., irreflexive, transitive partial orders which satisfy an induction principle. – Andrej Bauer Jul 30 '10 at 9:23
That's an excellent question Andrej. I don't know off the top of my head. – François G. Dorais Jul 30 '10 at 11:45