2
$\begingroup$

Few days I asked this question (https://math.stackexchange.com/questions/2907733/simple-ordinal-question) on MSE. Summary of the question is that I defined a certain function over ordinals $x \mapsto \beta_x$ (where $x<\omega_1$) and asked about its relation to the function $x \mapsto \omega^{CK}_x$. And it seems they are "nearly" the same (I mean the values, not the definitions) with the former function being continuous while the latter function is discontinuous (it does obey continuity condition on some limit values). In particular, $\omega^{CK}_1=\beta_0$ and $\omega^{CK}_2=\beta_1$.

Since asking that question, another question has come to my mind. Before getting into detail I will just briefly state the statement of question: "Can we rigorously define an ordinal $\gamma$ which (intuitively) is to $\omega_1$ what $\omega^{CK}_2$ is to $\omega^{CK}_1$?"

Here is the main motivation for the question. The (fictional) idea is that suppose completely "fictitiously" that we indeed have some well-order (of $\mathbb{N}$) with order-type $\omega_1$. Now suppose someone asked me whether this given $\gamma$ (which we are trying to describe rigorously) is greater than say $\omega{_1}^{\omega_1}$? My answer would be yes. And my "reasoning" would be that if somehow one just had access to the fictitious well-order just described, then using that hypothetical orcale function there also exists an ordinary program that describes the well-order (of $\mathbb{N}$) with order-type $\omega{_1}^{\omega_1}$. By the same reasoning $\gamma$ has to be greater than, say, the first fixed point of $x \mapsto (\omega_1)^x$. And so on...

I hope the drift of the question is clear at this point. The question is that what would be a reasonable rigorous definition of $\gamma$ that also corresponds well with this intuition.

Edit: Based upon suggestion in comments, I posted the side question separately: Relation of $\omega_{\omega_1+1}^{CK}$ to some other ordinals

$\endgroup$
5
  • $\begingroup$ Does "ORM" stand for "ordinal register machine"? $\endgroup$ Sep 10 '18 at 18:58
  • $\begingroup$ @NoahSchweber Yes indeed $\endgroup$
    – SSequence
    Sep 10 '18 at 18:59
  • $\begingroup$ I think that your final side question should be asked separately - ORMs are complicated enough that an answer to the main question doesn't really subsume the side question. $\endgroup$ Sep 10 '18 at 19:31
  • $\begingroup$ @NoahSchweber Alright I will do it when I get enough time. Just one small question though. Should the correct symbol be $\omega^{CK}_{\omega_1+1}$ for what I called $\gamma$ in this question? (and just in case the answer is "no" ... what would the correct symbol be?) $\endgroup$
    – SSequence
    Sep 10 '18 at 20:20
  • $\begingroup$ Yes, I'll add that to my answer. $\endgroup$ Sep 10 '18 at 20:21
6
$\begingroup$

This is actually much simpler than you may suspect: $\omega_\alpha^{CK}$ is well-defined for every ordinal $\alpha$, not just the countable ones, if we use the set-theoretic as opposed to computability-theoretic definition. Specifically, we define $\omega_\alpha^{CK}$ as the unique ordinal $\eta$ such that

  • $L_\eta\models$ KP (that is, $\eta$ is admissible)

and

  • $\{\gamma<\eta: L_\gamma\models\mbox{ KP}\}$ has ordertype $\alpha$.

That is, $\omega_\alpha^{CK}$ is the $\alpha$th admissible ordinal. The agreement with the computability-theoretic definition at countable levels is a theorem of Sacks: specifically, a countable ordinal is admissible iff it is the least ordinal with no $r$-computable copy for some real $r$.

For example, it's easy to check that in fact $$\omega_1=\omega^{CK}_{\omega_1}$$ that is, $\omega_1$ is a fixed point of the "admissible-counting" function. (It's definitely not the least fixed point, of course.) This means that the ordinal you refer to - if you accept my claim above, that this is really what you want - would be denoted by "$\omega_{\omega_1+1}^{CK}$."


Via forcing, we can give a computability-theoretic interpretation of $\omega_\alpha^{CK}$ even when $\alpha$ is uncountable (CAVEAT: this is my own work, so you should take my approval of it with a grain of salt):

  • Say that an ordinal $\gamma$ is generically Church-Kleene if in some generic extension of the universe in which $\gamma$ is countable, there is some real $r$ such that $\gamma$ is the least ordinal with no $r$-computable copy.

    • By Shoenfield's absoluteness theorem, we can replace "some generic extension" with "every generic extension" above; in particular, this means that this agrees with the usual notion when $\gamma$ is countable.
  • Then we can prove - by "genericizing" Sacks' theorem - that $\omega^{CK}_\alpha$ is exactly the $\alpha$th generically Church-Kleene ordinal; that is, $\omega_\alpha^{CK}$ is the unique generically Church-Kleene ordinal such that the set of smaller generically Church-Kleene ordinals has ordertype $\alpha$.

It's worth contrasting this with the perspective given by admissible recursion theory: in general, the supremum of the $\alpha$-recursive well-orderings of $\alpha$ is vastly smaller than the next admissible above $\alpha$. This is true, for example, when $\alpha=\omega_1$. Ordinals where this doesn't happen are called Gandy ordinals, and in a precise sense, most ordinals - even most countable ordinals - are not Gandy.

$\endgroup$
2
  • $\begingroup$ Incidentally, I am slightly uncomfortable citing myself here. I do think it's justified via non-negligible relevance, but if others feel that this is self-promotion I'm happy to delete it. $\endgroup$ Sep 10 '18 at 18:55
  • $\begingroup$ No, please don't delete it. If a self-citation is indeed appropriate to an answer, then it should be usable with impunity. (Of course, there will be many who come to MO to self-cite without realizing or admitting to oneself that it is inappropriate.) $\endgroup$
    – Todd Trimble
    Sep 11 '18 at 14:10

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.