17

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

Asaf Karagila
  • 38,140

2 Answers2

13

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.

Andreas Blass
  • 72,290
  • 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... – Asaf Karagila Dec 17 '12 at 18:38
  • 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. – Asaf Karagila Dec 17 '12 at 21:31
  • 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. – Andreas Blass Dec 18 '12 at 14:48
8

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.

Noah Schweber
  • 18,932
  • 2
    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. – Fedor Pakhomov Dec 10 '19 at 18:25
  • 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). – Fedor Pakhomov Dec 10 '19 at 18:28
  • @FedorPakhomov Oof, I didn't know that! I've changed the notation. As to your initial comment, can that happen? At a glance I don't see how to do it (the obstacle being that ZFC proves that every set-well-ordering is isomorphic to some ordinal, and $M$ is transitive; of course the candidate bad orders can be horribly non-set-like in $M$ this isn't fatal, but it does slow me down). – Noah Schweber Dec 10 '19 at 18:33
  • There are models that are wrong about some class being well-ordered.The most well-known example would be that $L_{\omega_1^{CK}}$ thinks that Gandy order (ill-founded order without hyperarithmetic descending chains) is well-founded. Although it isn't particular interesting since Gandy order is set-size and set-size order couldn't be externally ill-founded for models of theories that unlike KP could prove that any well-ordering is isomorphic to an ordinal. – Fedor Pakhomov Dec 10 '19 at 18:49
  • I do know a construction of a transitive model of $\mathsf{ZFC}$ with internally well-founded, but externally ill-founded class. However it uses theory of ptykes (higher-order operators on well-orderings) and there is just too much to explain about that. – Fedor Pakhomov Dec 10 '19 at 18:50
  • @FedorPakhomov But $L_{\omega_1^{CK}}\not\models$ ZFC, and indeed the missing piece is that KP$\omega$ can't prove that every set-well-ordering is in bijection with an ordinal. – Noah Schweber Dec 10 '19 at 18:50
  • @FedorPakhomov Is there a citation for that construction? I'd be really interested in reading that (I've been vaguely interested in ptykes for a while, motivated by van de Wiele's theorem). – Noah Schweber Dec 10 '19 at 18:51
  • 3
    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. – Fedor Pakhomov Dec 10 '19 at 19:31
  • 1
    With regard to the references. I read about $\beta$-completeness theorem in the draft of Girard's unpublished book http://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. – Fedor Pakhomov Dec 10 '19 at 19:46
  • @FedorPakhomov Thank you very much, that's quite interesting! Quick question - what does "prae" mean? I've not seen that notation before. And I wasn't aware of Girard's book, that's a great resource. – Noah Schweber Dec 10 '19 at 19:48
  • Prae-dilator is an endo-functor acting on the category of linear orders that preserves directed co-limits and pullbacks. (Dilators are the same but for the category of well-orders). – Fedor Pakhomov Dec 10 '19 at 19:51
  • @FedorPakhomov I see, thank you very much! I'll read the relevant parts of Girard's book and post any more questions I have to MO/MSE proper. – Noah Schweber Dec 10 '19 at 20:05
  • 4
    There's also Joel's answer here https://mathoverflow.net/a/270540/109573 – Elliot Glazer Dec 10 '19 at 20:44
  • @ElliotGlazer I wasn't aware of that, thanks! – Noah Schweber Dec 10 '19 at 20:46
  • @FedorPakhomov Coming back to your original comment, I think Andreas' definition does in fact work: he's looking at the supremum of all ordertypes of definable genuine well-orderings. So I don't think there's too much of a problem here. – Noah Schweber Dec 12 '19 at 21:31
  • Yes, right, I have misinterpreted Andreas. – Fedor Pakhomov Dec 12 '19 at 22:05