# Is $\omega_1^{CK}$ recursively enumerable?

Using the pairing, replacement and union (to take limits) axioms one can effectively produce some recursive ordinals starting from $\omega$ as $\omega+1$, $\omega\cdot 2$, $\omega^2$, $\omega^\omega$, $\varepsilon_0$, $\varphi_{\gamma}(\beta)$, $\Gamma_{\alpha}$, etc. I'm wondered how far we can go this way, i.e. by successively constructing ordinals from already constructed applying pairing, union and replacement a finite number of times? Can we exhaust $\omega_1^{CK}$ this way? If no, is there a recursive enumeration of $\omega_1^{CK}$?

There is no recursive enumeration of $\omega_1^{CK}$. Indeed, there is no hyperarithmetic (or even $\Sigma^1_1$) way to present $\omega_1^{CK}$! This was proved by Spector.

More generally, if a Turing degree ${\bf a}$ computes a copy of an ordinal $\alpha$ and ${\bf a}$ is hyperarithmetic relative to ${\bf b}$, then ${\bf b}$ also computes a copy of $\alpha$. This general property is called "hyperarithmetic-is-recursive," and turns out to have surprising connections with model theory (at least, its more set-theoretic side). We say that a class of structures $\mathbb{K}$ satisfies hyperarithmetic-is-recursive if whenever a Turing degree ${\bf a}$ is hyperarithmetic in ${\bf b}$ and computes a copy of $\mathcal{A}$, then ${\bf b}$ also computes a copy of $\mathcal{A}$, for all $\mathcal{A}\in\mathbb{K}$. Montalban showed that a first-order theory $T$ is a counterexample to Vaught's conjecture if and only if $T$ satisfies "hyperarithmetic-is-recursive on a cone," a slight weakening of "hyperarithmetic-is-recursive."

With regard to the first part of your question, however, it's not entirely clear to me what process you have in mind; specifically, how Replacement is allowed to be used. In the naive sense, we can automatically reach any countable ordinal which has a copy (= ordering of $\omega$ with appropriate ordertype) definable in set theory with a single application of replacement. $\omega_1^{CK}$, and much more, falls into this category. Here is an explicit definable well-ordering of $\omega$ with ordertype $\omega_1^{CK}$:

• We define Kleene's set $\mathcal{O}$ of ordinal notations as usual.

• We now define a relation $\triangleleft$ on $\mathcal{O}$ as follows: $m\triangleleft n$ iff $m$ is an index for an ordinal which is smaller than the ordinal $n$ is an index for.

• Finally, we let $$M=\{m\in\mathcal{O}: \forall n\in\mathcal{O}(n<m\implies (m\triangleleft n\vee n\triangleleft m))\}$$ be the set of minimal indices for ordinals. Then $M$, ordered by $\triangleleft$, has ordertype $\omega_1^{CK}$.

• Now, since $M$ doesn't actually consist of every natural number, we're not technically done, but this is easily fixed: let $M=\{m_0<m_1<m_2< ...\}$ and let $\triangleleft'$ be defined by $x\triangleleft'y\iff m_x\triangleleft m_y$. Then $\triangleleft'$ is a well-ordering of $\omega$ with ordertype $\omega_1^{CK}$. And this doesn't even scratch the surface of ordinals we can build.

So in the process you describe, you probably want to limit attention somehow to "effective" applications of replacement, and it's not entirely clear to me what this means.

That said, you may be tangentially interested in this paper of Arai, in which he essentially calculates a bound on the $L$-rank of reals (equivalently, hereditarily countable sets) which can be "proved to exist" in ZFC+V=L in a precise sense. I think this overshoots what you want by a huge margin, both because powerset is allowed and because there's no "finite construction" picture going on (as far as I can tell), but you might still find it neat.

• I'm interested what ordinals can be reached without the power set axiom (and so $\omega_1$ is not permitted), as they are, roughly speaking, reachable "from below" in contrast to those defined through a separation from $\omega_1$ and so constructed "from above". In this sense $\omega_1$ is some sort of "inaccessible" ordinal, but are there smaller "inaccessibles"? I thought $\omega_1^{CK}$ is such an example, but it seems your definition doesn't require the power set. – Seriy Mar 19 '18 at 13:37
• As for the process in the question, I had in mind some repeated diagonalization as described here en.wikipedia.org/wiki/…. I haven't adopted the further construction from this article as it needs $\omega_1$, but in this case it seems I wouldn't be able even to reach this latter ordinal collapse. – Seriy Mar 19 '18 at 13:47
• Also I hoped there is some canonical effective enumeration of ordinals which does not require the power set, but it seems it's not the case. – Seriy Mar 19 '18 at 13:50
• @Seriy Yes, powerset is not needed to reach $\omega_1^{CK}$. This excellent note by Madore describes a number of these starting on page $3$, and it's a good exercise to go through at least the smaller ones and prove they exist without invoking powerset. As you go up the hierarchy, you'll need more and more replacement - e.g. the theory KP+Inf can't prove that $\omega_1^{CK}$ exists, but once we add $\Sigma_2$-replacement it can. – Noah Schweber Mar 19 '18 at 13:55
• @Seriy Re: your last statement I'm not quite sure what you mean. Can you elaborate? – Noah Schweber Mar 19 '18 at 13:56