15
$\begingroup$

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})$?

$\endgroup$
12
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Andreas, is there anything large cardinals can do to affect the outcome? For example if $M\models\exists 0^\#$, or has a proper class of superhuge cardinals? I suppose that from that we can define more orderings... $\endgroup$ – Asaf Karagila Dec 17 '12 at 18:38
  • $\begingroup$ Also you are spot on the first-order definable [with parameters] over $M$. I borrowed the notation because I found it somewhat relevant, $\omega_1^{CK}$ is the $\omega_1^{CK}(\mathsf{Ord}^{V_\omega})$ of the theory ZFC-Infinity+$\lnot$Infinity. $\endgroup$ – Asaf Karagila Dec 17 '12 at 21:31
  • $\begingroup$ As far as I can see, the next admissible set remains an upper bound, no matter what large-cardinal axioms $M$ satisfies. What that next admissible set is depends, of course, on $M$, and I'd expect it may depend on other things than just large-cardinal properties. $\endgroup$ – Andreas Blass Dec 18 '12 at 14:48
6
$\begingroup$

Bumping an old question, I believe that Andreas' bound of the next admissible ordinal is in general (and I suspect always) not sharp. 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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I think that in general (not assuming $M^\omega\subseteq M$) there are problems with the definition that Andreas Blass has gave. Namely, $M$ might think that some class is well-ordered, although from external point of view it isn't well-ordered (which would make $\omega_1^{CK}(M)$ ill-founded). So the natural condition here is to only consider $M$ such that $M\models L\text{ is a class well-ordering}$ implies $WO(L^M)$. But for $M$ of this sort the property to be $M$-definable well-ordering will be $\Delta_0$ in $Ad(M)$. And your argument will work for them in the same manner. $\endgroup$ – Fedor Pakhomov Dec 10 '19 at 18:25
  • $\begingroup$ I would suggest to rename $\mathsf{KPi}$ to $\mathsf{KP}\omega$. At least in proof-theory people usually denote $\mathsf{KPi}$ the theory $\mathsf{KP}+\text{every set lies in a transitive model of }\mathsf{KP}$ (i here stands for (recursively) inaccessible). $\endgroup$ – Fedor Pakhomov Dec 10 '19 at 18:28
  • 1
    $\begingroup$ I meant that the theory of ptykes is too complicated to outline. Actually now I figured out that this could be done just using dilators; I outline the argument assuming some familiarity with the theory. Using Girard's completeness theorem for $\beta$-logic it is possible to construct a prae-dilator $F$ s.t. $F(\alpha)$ is w.o. iff there are no transitive models of $\mathsf{ZFC}$ of the height $\le \alpha$. Notice that $F$ is a dilator in the least transitive model $M\models\mathsf{ZFC}$. Thus $M\models WO(F(On))$. However, externally $F(On^M)=(F(On))^M$ is ill-founded. $\endgroup$ – Fedor Pakhomov Dec 10 '19 at 19:31
  • 1
    $\begingroup$ With regard to the references. I read about $\beta$-completeness theorem in the draft of Girard's unpublished book girard.perso.math.cnrs.fr/Archives4.html (Chapter 10). Maybe there is a better reference, but I don't know about that. $F$ in the argument above is the dilator corresponding to the canonical $\beta$-proof of the sequent $\mathsf{ZFC}'\Rightarrow$. Theory $\mathsf{ZFC}'$ here is an alternative presentation of $\mathsf{ZFC}$ given in a two sorted language with a separate sort for ordinals. $\endgroup$ – Fedor Pakhomov Dec 10 '19 at 19:46
  • 3
    $\begingroup$ There's also Joel's answer here mathoverflow.net/a/270540/109573 $\endgroup$ – Elliot Glazer Dec 10 '19 at 20:44

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.