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.


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?

  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Jul 5, 2010 at 17:43

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

  • 3
    $\begingroup$ 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. $\endgroup$ Commented Jul 5, 2010 at 18:27
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jul 5, 2010 at 18:48
  • $\begingroup$ 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. $\endgroup$ Commented Jul 30, 2010 at 9:23
  • $\begingroup$ That's an excellent question Andrej. I don't know off the top of my head. $\endgroup$ Commented Jul 30, 2010 at 11:45
  • $\begingroup$ A neat way to generate these wellorders is to consider non-wellfounded models of enough of set theory but I can't remember how at the moment. As I remember the idea was to ensure that every (index for) recursive wellordering was a recursive well ordering in the non-wellfounded model but the non-wellfounded model also had further recursive well-orderings. However, something isn't quite right with what I said or I'm missing a piece and am curious if anyone remembers how this is supposed to be done. $\endgroup$ Commented Dec 15, 2016 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.