Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Question

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?

Answer 1

I will choose to answer your response to Andres above.

Following what you mean by a recursive sequence, let $(\omega^{ck}_1,<)$ be the chain of given recursive ordinals $\alpha_i<\beta$, $i \in \mathbb N$ with $\beta$ a limit ordinal. We will have $\omega^{ck}_1$ be the supremum of this sequence, where $\omega^{ck}_1$ is the least nonrecursive ordinal of Church-Kleene (CK). If I understand correctly, we will have $\alpha_1 < \alpha_2 < \dots < \alpha_k$ as a strictly increasing computably enumerable sequence with $\alpha+1 \neq \beta$ as you ask.

We now give a computable (recursive) definition of successor ordinal and limit ordinal. 1) Define $|2^i|= \alpha+1$ for successor ordinal, such that we will have $\alpha <_e \alpha +1$ owing to the linear order and $i$ is the index of a partial function $\phi_e(i,n)=1$ if $\alpha <_e \alpha+1$ and $0$ if otherwise. I take as granted that the order relation $<_e$ is computably enumerable but not computable (that is, in the range of a partial recursive function). It is also worth mentioning that $<_e$ is well-founded, or not infinitely descending and hence the chain $(\omega^{ck}_1,<)$ has a minimal element.

2) For limit, let $|3 * 5^e| = lim_k|i_k| = \beta_e$ where $e$ is the code numeral for a partial recursive function $\psi_e$ enumerating each $\alpha_i <_e \beta^e$. However, since $<_e$ is computably enumerable ($xRy$ in the range of a partial recursive function for $R$ a well-ordering) via the linear order, we can use the definition of the computable limit ordinal $\beta$ to show that it is bounded above by the Church-Kleene ordinal, well-founded as a limit for $\forall \alpha(\alpha < \beta)$, and therefore itself a recursive ordinal.

Answer 2

I believe you are asking the following:

Suppose $X$ is a set of (notations for) computable ordinals, such that - when ordered by length - the elements of $X$ form a computable ordinal. Is $\sup(\{\vert x\vert: x\in X\})$ a computable ordinal?

The answer is no. Let $\omega_1^{CK}$ be the least noncomputable ordinal. Then (exercise) $\omega_1^{CK}$ is countable, so we may find ordinals $$\alpha_0<\alpha_1<...$$ such that

• $\alpha_i<\omega_1^{CK}$ for all $i\in\mathbb{N}$, but

• $\sup\{\alpha_i: i\in\mathbb{N}\}=\omega_1^{CK}$.

This is a good exercise, and uses nothing besides the fact that $\omega_1^{CK}$ is countable. (Look up cofinality.) But then $\{\alpha_i: i\in\mathbb{N}\}$ is a counterexample to your question, since each $\alpha_i$ is computable (being $<\omega_1^{CK}$).

---

A crucial piece of this argument is that the set $X$ is not effectively given: if $X$ is a computable set of notations, then unsurprisingly $\sup(\{\vert x\vert: x\in X\})$ is also computable. In fact, by a more technical argument ("$\Sigma^1_1$ bounding") no such $X$ can be $\Sigma^1_1$; we only start finding such $X$ at the $\Pi^1_1$ level.

In the language of $\alpha$-recursion theory, the existence of such an $X$ which is $\Pi^1_1$ is recast as the observation that $L_{\omega_1^{CK}}$ does not satisfy $\Sigma_1$-separation (more jargon-y: "the $\Sigma_1$-projectum of $\omega_1^{CK}$ is $\omega$"), which in turn can be interpreted as saying that $\omega_1^{CK}$ is "barely admissible." Ultimately $\alpha$-recursion theory is the right context for questions about computability-theoretic properties of ordinals, and Sacks' book is the standard starting point.