3
$\begingroup$

Given the Church-Kleene ordinal $\omega^{CK}_1$, the supremum of all recursive ordinals, can we go further and derive $\omega^{CK}_2$, $\omega^{CK}_3$, $\omega^{CK}_\omega$ or $\omega^{CK}_{\omega^{CK}_1}$?

Even beyond that, $\mathcal{O}^+$ is the supremum of all writable ordinals and $\mathcal{O}^{++}$ is the supremum of all eventually writable ordinals, is this also extendable? i.e. can we have $\mathcal{O}^{+++}$ or $\mathcal{O}^{++++++}$?

If they do exist, I'm assuming the supremums of these sequences are less than the first uncountable ordinal $\omega_1$?

Thank you so much!

$\endgroup$
6
$\begingroup$

A good rule of thumb in computability theory is, everything can be relativized. (Before going further, I'll link to this lovely summary of many countable ordinals of computability-theoretic significance, by David Madore; it's not immediately relevant to your question, but in answering your question we'll be inexorably drawn to its themes.)

Let's talk about $\omega_1^{CK}$, since I don't really know anything about writeable ordinals. $\omega_1^{CK}$ has two natural definitions:

  • The first ordinal $\alpha$ with no computable copy.

  • The first ordinal $\alpha>\omega$ such that $L_\alpha\models $KP.

Here "KP" is Kripke-Platek set theory, a weak fragment of ZFC. "$L_\alpha$" denotes the $\alpha$th level of the constructible universe, and an ordinal $\alpha$ is admissible if $L_\alpha\models$KP.

Both of these definitions generalize:

  • Given $r\subseteq\omega$, we let $\omega_1^{CK}(r)$ denote the first ordinal with no $r$-computable copy. (This is usually denoted by "$\omega_1^r$," but I dislike that a bit.)

  • Given an ordinal $\alpha$, we write "$\omega_1^{Ad}(\alpha)$" for the least admissible $>\alpha$. (This is usually denoted by "$\alpha^+$," but that's even worse.) Note that this suggests that we could write "$\omega_1^{Ad}=\omega_1^{CK}$;" I certainly wouldn't object.

It's easy to show that $\omega_1^{CK}(r)$ and $\omega_1^{Ad}(\alpha)$ each exist, regardless of $r$ and $\alpha$. It turns out that they each generalize $\omega_1^{CK}$ in the same way!

The simplest generalization of $\omega_\alpha^{CK}$ is via admissibility:

$\omega_\alpha^{Ad}$ is the $\alpha$th admissible ordinal greater than $\omega$.

Another generalization, a bit more complicated, comes from computability directly:

For $\alpha$ an ordinal, we write $\omega_1^{CK}(\alpha)$ for the least ordinal $\beta$ for which there is some copy of $\alpha$ (= binary relation on $\omega$ with ordertype $\alpha$) which does not compute a copy of $\beta$.

Note that this definition only makes sense for $\alpha$ countable; this can be fixed by looking at forcing extensions in which $\alpha$ is countable. The general theme of computability in generic extensions is a very interesting one to me, and is something I work on.

It turns out that these two ideas are the same! This is due to Sacks, following Kripke and Platek:

$\alpha$ is admissible iff there is some $r\subseteq\omega$ such that $\alpha=\omega_1^{CK}(r)$. In particular, this means that we have $\omega_1^{CK}(\alpha)=\omega_1^{Ad}(\alpha)$ for all (countable) ordinals $\alpha$.

Incidentally, this explains why you've never seen the notation "$\omega_1^{Ad}$" before - there's really no point in having it. But I think it's useful to introduce it early on, in order to keep the distinction clear and make Sacks' result more immediately impressive.

So this shows that not only can we continue to define versions of $\omega_1^{CK}$, but it relativizes robustly. And these relativizations are extremely useful: admissible sets provide contexts for generalized recursion theory ("$\alpha$-recursion theory"), and Sacks' characterization via computability is a powerful tool in their study.


Now what about $\mathcal{O}$?

There's a notational issue here: "$\mathcal{O}$" is more commonly used to describe a specific set of natural numbers .

Well, there's a natural generalization of it, following the second generalization of $\omega_1^{CK}$:

Let $\mathcal{O}_2$ be the least ordinal $\alpha$ for which there is some copy of $\mathcal{O}$ relatively to which $\alpha$ is not writeable.

More generally, for $r\subseteq\omega$ write "$\mathcal{O}(r)$" for the least ordinal not writeable relative to $r$. A good understanding of the ordinal should provide an equivalent characterization of those ordinals of the form $\mathcal{O}(r)$ in terms of the axioms the relevant levels of $L$ should satisfy (and Madore's article mentions several results in this theme).

Similarly, we can generalize $\mathcal{O}^+$ by replacing "writeable" with "eventually writeable."

However, you asked something different: about the transition $\mathcal{O}\rightarrow\mathcal{O}^+$. I'm not sure what should come next, since I don't know what operation corresponds to adding the word "eventually." There is a precedent, though: the relationship between writeability and eventual writeability seems very weakly similar to that between computability and limit computability, which of course is connected to an operation. So I'm optimistic here. But maybe an actual expert can chime in here ...

$\endgroup$
  • $\begingroup$ I love this site. Thank you so much! I'm going to check out the article you linked and I might come back with a tiny question, but this seems like a lot of what I asked in the question! $\endgroup$ – user3684314 Jul 19 '17 at 2:00
  • 1
    $\begingroup$ @user3684314 Glad I could help! The bibliography in the Madore article is especially useful; you should check out the sources it mentions (especially Sacks' "Higher Recursion Theory," Barwise' "Admissible sets and structures," and the volumes "Generalized Recursion Theory I and II," in my opinion). $\endgroup$ – Noah Schweber Jul 19 '17 at 2:07
  • $\begingroup$ Brilliant! I actually have one question so far based on the "Zoo" article, namely (1.22), which describes the countable collapse of $\epsilon_{I+1}$ where $I$ is the first inaccessible cardinal. Wouldn't that be much larger than the Church-Kleene ordinal? $\endgroup$ – user3684314 Jul 19 '17 at 2:20
  • 2
    $\begingroup$ @user3684314 Nope - it's actually much smaller. The collapsing process is one used in proof theory, and produces countable ordinals (even if it starts with ridiculously huge cardinals) - see this wiki summary. $\endgroup$ – Noah Schweber Jul 19 '17 at 2:40
  • 1
    $\begingroup$ No problem @user3684314 , generally $\psi_I(x)$ can be thought of as fixed-points of $f:x\mapsto\Omega_x$, and$$\psi(\varepsilon_{I+1})=\psi(I^{I^{I^{\dots}}})=\psi(\psi_I(I^{I^{I^{\dots}}}))\gg\psi(\psi_I(I))=\psi(\psi_I(\psi_I(\psi_I(\dots))))=\dots\gg\psi(\psi_I(0))$$To give you an idea of how it works. $\endgroup$ – Simply Beautiful Art Sep 29 '17 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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