Recursively Enumerable Ordinals

Question

Is there an explicit enumeration of the Church-Kleene ordinal $\omega_1^{CK}$? A general explanation of what it means for an ordinal to be computable and/or recursively enumerable could be helpful too.

Answer 1

No, $\omega_1^{CK}$ is not remotely close to computable. It turns out that it isn't even hyperarithmetic.

Precisely, we say that a linear order $\alpha$ has a computable copy if there is a computable binary relation $\triangleleft$ on $\omega$ such that $(\omega,\triangleleft)$ is a linear order isomorphic to $\alpha$. Note that this $\triangleleft$ will not be unique: a given linear order may have many different "computable copies." Of course "computable" here can be replaced with any other complexity notion - e.g. hyperarithmetic - and similarly we can talk about computable copies of structures in general (e.g. groups, rings, fields, ...) by looking at things other than just binary relations. We can also relativize, and talk about structures with copies computable (or hyperarithmetic, or etc.) relative to a given real.

We often abuse terminology and talk about "computable ordinals" (or groups, or rings, or ...) to refer to ordinals which have computable copies.

• Incidentally, it's a good exercise at this point to prove that every linear order which has a c.e. copy has a computable copy, and indeed every c.e. copy of a linear order is literally computable - this isn't true in general structures. (HINT: it's not even true for partial orders in general ...)

Surprisingly, for ordinals computability is a very coarse notion: Spector proved that an ordinal $\alpha$ (thought of as a linear ordering) has a hyperarithmetic copy iff it has a computable copy. So $\omega_1^{CK}$ isn't just noncomputable, it's extremely far from computable.

A good source for this is Ash/Knight's book Computable structures and the hyperarithmetic hierarchy.

---

This is all also tied to another more technical notion of $\omega_1^{CK}$ being "hard to enumerate," namely admissibility:

Suppose $r$ is a real and $\omega_1^{CK}(r)$ is the least ordinal with no $r$-computable copy. Then the level $$L_{\omega_1^{CK}(r)}$$ of the constructible universe satisfies Kripke-Platek set theory (+ infinity) - or more snappily, is $\Sigma_1$-admissible.

EDIT: it's worth noting that there is a converse here, namely that for countable $\alpha$ we have that $\alpha$ is admissible (= $L_\alpha\models$ KP+inf) iff $\alpha=\omega_1^{CK}(r)$ for some $r$. However, note that this does not mean that $r\in L_\alpha$ in such a case (take e.g. $\alpha$ to be an admissible limit of admissibles); we only have the weaker fact that $L_\alpha[r]$ also satisfies KP+inf.

In particular, there is no $\Sigma_1$-over-$L_{\omega_1^{CK}}$ cofinal function from $\omega$ to $\omega_1^{CK}$. And all the usual ways of climbing up ordinals are much much simpler than that. So you really have to break out some big guns to climb up to $\omega_1^{CK}$ from below.

Details of all this can be found in Sacks' book Higher recursion theory.