6
$\begingroup$

Ordinals are order types of well-ordered sets. Proper classes can be well-ordered too, though, the most famous example being the class of all ordinals under the standard ordering. So my question is, what order-types can well-ordered proper classes have? If we let $\Omega$ be the order type of the ordinals, how much bigger than $\Omega$ can we go?

I’m guessing that the order types of well-ordered proper classes cannot be put in one-to-one correspondence with the class of all sets, just as the order types of well-ordered countable sets cannot be put in one-to-one correspondence with the set of natural numbers.

EDIT: I am asking my question in the context of Morse-Kelly set theory.

$\endgroup$
3
  • 1
    $\begingroup$ Your question is unclear. Well-ordered by what? What is your foundational system? NBG? MK? $\endgroup$
    – user21820
    Commented Dec 10, 2019 at 16:07
  • 2
    $\begingroup$ @user21820 I edited my question to specify MK. And by a well-ordered proper class I mean a proper class $X$ together with a class relation, i.e. a proper class of ordered pairs of elements of $X$, which is a well-ordering. $\endgroup$ Commented Dec 10, 2019 at 16:12
  • $\begingroup$ Ok. It's now clear. $\endgroup$
    – user21820
    Commented Dec 10, 2019 at 16:13

1 Answer 1

6
$\begingroup$

To make things clearer I'm going to rephrase the question as follows (it's not hard to translate between this question, which is asked in the ZFC context, and your question as you've phrased it):

Suppose $M$ is a transitive model of ZFC. Let $\alpha_M$ be the supremum - calculated in $V$ - of the ordertypes of the definable (-in-the-sense-of-$M$) well-orderings of subsets (-in-the-sense-of-$V$) of $M$. What can we say about $\alpha_M$?

(This is closely related to this old Mathoverflow question.)

A good first observation is the following:

Let $N$ be the least admissible set above $M$ - that is, $N$ is the smallest transitive model of Kripke-Platek set theory with $M\in N$. Then $\alpha_M\le N\cap Ord$.

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

This is a more-mysterious-looking special case of a general fact: if $A$ is an admissible set and $S$ is a structure in $A$, then every $S$-definable well-ordering of a subset of $S$ is an element of $A$.


OK, now is that sharp? Let's especially focus on the case when $M=L_\gamma$ for some ordinal $\gamma$; in this case we have $\alpha_M$ is just the least admissible ordinal $>\gamma$, which I'll call $\omega_1^{CK}(\gamma)$, where an ordinal $\gamma$ is admissible if $L_\gamma$ is an admissible set. (The standard notation is, sadly, "$\gamma^+$." I know, I know, ...)

It's worth pointing out at this point that our experiences from classical computability theory are wildly misleading here. Specifically, we classically have that $\omega_1^{CK}$ (= the least admissible ordinal $>\omega$) is the supremum of the classically-computable ordinals. This suggests that in general we should have that $\omega_1^{CK}(\gamma)$ should be the supremum of the "$\gamma$-computable" ordinals, that is, of the ordinals which are (the ordertype of) a well-ordering of $\gamma$ which is $\Sigma_1$-definable over $L_\gamma$. (At least, for "reasonably closed" $\gamma$ - say, admissible $\gamma$. Note that if $M\models ZFC$ then $M\cap Ord$ is trivially admissible, and indeed much more, so this isn't really a meaningful restriction in our context.)

This is very false in general, however; see e.g. this old Mathoverflow answer of mine. The takeaway from this is that the next admissible is generally really really big - in particular, we should be very suspicious of the upper bound above!

Indeed, the upper bound above is generally not sharp:

We have $$\alpha_{L_{\omega_1}}<\omega_1^{CK}(\omega_1).$$

(Incidentally, the ordinal $\omega_1^{CK}$ is also called "$\omega_{\omega_1+1}^{CK}$.")

The proof is via a nice trick: if $w$ is a non-well-ordering in $L_{\omega_1}$, then there is a descending sequence through $w$ which is also in $L_{\omega_1}$ (Mostowski absoluteness + regularity of $\omega_1$). This means that in $L_{\omega_1^{CK}(\omega_1)}$ we can computably tell whether a formula $\varphi$ with parameters in $L_{\omega_1}$ defines (in $L_{\omega_1}$) a well-ordering: search simultaneously for descending sequences through $\varphi^{L_{\omega_1}}$ and for isomorphisms between $\varphi^{L_{\omega_1}}$ and some ordinal. This lets us build a copy of $\alpha_{L_{\omega_1}}$ inside $L_{\omega_1^{CK}(\omega_1)}$.


More generally, if $M$ is a transitive model of ZFC with $M^\omega\subseteq M$, then:

  • $\alpha_M<\omega_1^{CK}(M)$, and

  • more generally the supremum of the $\Sigma_k$-definable well-orderings of $M$ (in the sense of $M$) has a copy which is $\Sigma_{k+1}$-definable over $M$.

In general, I suspect that both these phenomena hold for all models of ZFC, but I don't see it immediately.


So what is a good upper bound? Well, unfortunately there aren't really many natural ordinals below the next admissible but above all the "small $\omega_1^{CK}$ analogues." So I don't really have any good candidates.

$\endgroup$
8
  • $\begingroup$ So how does this result translate to my question, which isn’t about set models of ZFC, but about what’s actually true in the standard model of ZFC, which is a class model? $\endgroup$ Commented Dec 10, 2019 at 17:47
  • $\begingroup$ @KeshavSrinivasan Yes, I'm aware. Per my first line, "local" results of this type translate nicely to "global" results in the MK context - in fact, we often gain nuance when this happens since MK really only lets us talk about "one level up" from $V$. Essentially what the above says is that in a very strong way the collection of all classes cannot form an "admissible structure above $V$" - the ordinals so produceable are just too small. But the "flatness" of MK makes it hard to say more. $\endgroup$ Commented Dec 10, 2019 at 17:52
  • $\begingroup$ So is this basically a way of putting a (qualitative, if not quantitative) upper bound on the order types of well-ordered proper classes? And if classes aren’t enough to produce an admissible structure above $V$, how many layers do we need to produce such a structure? Second-level classes, third-level classes, omega-level classes, or what? $\endgroup$ Commented Dec 10, 2019 at 17:56
  • $\begingroup$ Also, what is the answer to my question about whether the order-types of well-ordered proper classes can be put in one-to-one correspondence with the class of all sets? $\endgroup$ Commented Dec 10, 2019 at 17:57
  • $\begingroup$ I'm not sure what you mean by "qualitative" - I'd rather say, "not (in general) sharp." Unfortunately I think one of the takeaways from the argument above is that there's not going to be a snappy description of the relevant ordinal. $\endgroup$ Commented Dec 10, 2019 at 18:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .