What is $\omega_1^{CK}(\mathsf{Ord})$?

Question

We know that if $\alpha<\omega_1^{CK}$ then there is some recursive $R$ such that $(\omega,R)$ has order type $\alpha$.

Let's consider now the ordinals, $\mathsf{Ord}$ with their natural order. This is a well-ordered class, and it behaves very much like $\omega$ (in fact $\mathsf{Ord}^{V_\omega}=\omega$). We can define new order types on $\mathsf{Ord}$ whose order type is strictly larger.

For example $\leq_0=\lbrace(\alpha,\beta)\mid 0<\alpha\land(\alpha<\beta\lor\beta=0)\rbrace$ would be a well-ordering of $\mathsf{Ord}$ which is isomorphic to $\mathsf{Ord}+1$.

We can do this with any set of ordinals, or even a class of ordinals: put all the limit ordinals strictly above all the successor ordinals (and zero), and in each part order by the natural order. We can even go further and define the following ordering:

• Zero and successor ordinals first, order by the natural order.
• Any limit ordinal is greater than zero and all the successors.
• Given two limit ordinals with different cofinality then the order then by their cofinality.
• Given two limit ordinals with the same cofinality then order them as usually.

And of course we can proceed more and more. And define even greater and more complicated order types (using parameters, of course).

My question is what sort of supremum these class-orders have? But of course this is too broad. Clearly this is going to depend on the universe itself, or rather the model. So let me put some constraints on this question.

Let $(M,\in)$ be a countable transitive model of ZFC, and suppose that $\mathsf{Ord}^M=\alpha$. Can we compute this $\omega_1^{CK}(\mathsf{Ord}^M)$ from $\alpha$ and $M$? Can we at least bound it from below and above (of course $\omega_1$ is an upper bound, but a more reasonable bound that is)?

I feel that my question is still quite broad, but is there anything intelligible we can say on those ordinals? Does the fact that $M$ is countable make any difference in the computation?

Two more points which crossed my mind as relevant, and perhaps helpful, to the above question.

1. What happens if we add large cardinals assumptions into $M$. If for example there is a measurable in $M$, $\omega_1^{CK}(\mathsf{Ord}^M)>\omega_1^{CK}(\mathsf{Ord}^{L^M})$ (to make things interesting $M=L[U]$ maybe)?

2. What happens between extensions which don't add ordinals? In particular what about forcing extensions? Can we change this ordinal by forcing? Or maybe give some intelligible conjecture as to when an inner model of $M$ has the same $\omega_1^{CK}(\mathsf{Ord})$?

Answer 1

Although your notation $\omega_1^{CK}(\text{Ord}^M)$ suggests that you have some sort of generalized computability in mind, I'll take the question as being about all the well-orders of $\text{Ord}^M$ that are parametrically first-order definable over $M$. Such well-orders are elements of the next admissible set $M^+$, so the height of $M^+$ is an upper bound for their order-types. It might well be the least upper bound, but I'm not sure about that.

Answer 2

Bumping an old question, Andreas' bound of the next admissible ordinal is in general not sharp (although Dmytro Taranovsky showed that it sometimes is). The crucial point is not the theory of the model in question, but rather its closure properties - in particular, the bound of the next admissible fails to be sharp whenever $M^\omega\subseteq M$. (It's possible of course that large cardinals will be relevant in case $M^\omega\subseteq M$, but I actually think the failure of sharpness will hold unconditionally.)

Part of the point of this answer is that the notation in the OP winds up being highly misleading. So let me notationally start from scratch:

• I'll write "$\Delta(M)$" for the supremum of the definable-over-$M$ well-orderings of subsets of $M$.

• For $M$ a transitive model of KP + Infinity (= KP$\omega$), I'll write "$Ad(M)$" for the smallest transitive model of KP$\omega$ with $M$ as an element.

• I'll write "$\omega_1^{CK}(M)$" for $Ad(M)\cap Ord$.

---

(This MSE answer of mine contains the argument below in more detail, and this old MO answer of mine is also relevant:)

The key observation is that if $M^\omega\subseteq M$ then any $M$-definable ordering of a subset of $M$ which is ill-founded has a descending sequence in $M$. This means that the set $\mathcal{W}_M$ of formulas-with-parameters-in-$M$ which define in $M$ well-orderings of subsets of $M$ is computable in $Ad(M)$: this is because, given a candidate $\varphi$, we can just search in $Ad(M)$ for either an isomorphism between $\varphi^M$ and some ordinal or a descending sequence through $\varphi^M$ (in fact, all we're really using here is $M^\omega\subseteq Ad(M)$). This means that $$\Delta(M)<\omega_1^{CK}(M)$$ whenever $M$ is sufficiently closed.

As I said above, I strongly suspect that this upper bound is never sharp, but I don't see an argument for that at present. Annoyingly, there seems to be a paucity of candidates for better bounds. The height $\eta_M$ (my notation) of the smallest $E$-closed set containing $M$ as an element is a possible candidate, being in general (even always, I think) smaller than $Ad(M)$ when $M$ is admissible, but the plausibility of $\eta_M=\Delta(M)$ is due entirely to my ignorance of $E$-recursion.