# How far to find a well-order?

Consider a transitive set $$M$$. Let's call the well-ordering number for $$M$$ the smallest ordinal $$\alpha$$ so that $$L_\alpha(M)$$ contains as an element a well-order of $$M$$, and denote it as $$\upsilon = \upsilon(M)$$. My question is which ordinals are the $$\upsilon(M)$$ for some $$M$$.

This is phrased in a general format, and maybe it's helpful to narrow in on the specific case I have in mind. My primary interest is when $$M$$ is a countable model of ZFC. The best possible answer would be to completely characterize such $$\upsilon(M)$$, but that's likely difficult. The main thing I'd like to know (but haven't been able to figure out on my own) is what small ordinals are possible. Of course $$\upsilon(M) = 1$$ is possible—see below—but what about other finite ordinals? Or, say, $$\omega+1$$?

Here's some easy observations:

• It's possible that $$\upsilon(M)$$ is undefined, i.e. $$L(M)$$ thinks that $$M$$ cannot be well-ordered. For example, if $$\lambda$$ is an $$I_0$$ cardinal then $$M = V_\lambda$$ is like this.

• $$\upsilon(M)$$ cannot be a limit ordinal, just from the definition of the $$L(M)$$ hierarchy.

• $$\upsilon(M) = 1$$ is possible, which happens just in case $$M$$ has a definable well-order.

• It's possible $$\upsilon(M)$$ is defined and $$>1$$. Suppose $$M$$ is countable in $$L$$. Then a condensation argument yields that $$L_\alpha(M)$$ sees that $$M$$ is countable for some large enough countable $$\alpha$$, giving an upper bound on $$\upsilon(M)$$. If $$M$$ doesn't have definable well-order, then $$\upsilon(M) > 1$$. But I don't see how to turn this into a more precise calculation.

If there is a transitive set model $$M$$ of ZFC, then all finite successor ordinals $$n+1$$ and all $$\omega+n+1$$ are $$\upsilon(M)$$ for some such $$M$$, and also many other ordinals:

Claim: Let $$\Omega,\alpha<\omega_1^L$$ be such that $$L_\Omega\models\mathrm{ZFC}$$ and $$0<\alpha$$ and there is a surjection $$f:\omega\to\Omega+\alpha$$ in $$L_{\Omega+\alpha+1}$$. Then there is a transitive model $$M\models\mathrm{ZFC}$$ of height $$\Omega$$ such that $$\upsilon(M)=\alpha+1$$; moreover, in $$L_{\alpha+1}(M)$$ there is a surjection $$g:\omega\to M$$.

Remark: Note there calso be $$\beta<\alpha$$ such that $$L_{\Omega+\beta+1}$$ has a surjection $$f':\omega\to\Omega+\beta$$, and hence a surjection $$f'':\omega\to\Omega=\mathrm{OR}\cap M$$, but there won't be any wellorder of $$M$$ in $$\mathcal{J}_{\Omega+\beta+1}$$. The claim gives in particular that if there is a transitive $$M\models\mathrm{ZFC}$$ then all finite ordinals, $$\omega+1$$, and many "small" successor ordinals are $$\upsilon(M)$$ for some $$M$$. (E.g. if $$\Omega$$ is least such that $$L_\Omega\models\mathrm{ZFC}$$ then for each of these "small" ordinals $$\alpha$$ we can find an $$M$$ of height $$\Omega$$ with $$\upsilon(M)=\alpha+1$$, and also for cofinally many $$\alpha<\omega_1^L$$ there is $$M$$ of height $$\Omega$$ with $$\upsilon(M)=\alpha+1$$. On the other hand, if there is say a transitive model $$M$$ of ZFC of cardinal height $$\kappa$$, then $$L_\kappa$$ also models ZFC, and for whatever ordinal $$\alpha>0$$, we get that $$L_{\kappa+\alpha}\models$$$$\kappa$$ is a cardinal'', and by taking the $$\Sigma_{n+1}$$-hull in $$L_{\kappa+\alpha}$$ of the single parameter $$\kappa$$, we get $$L_{\bar{\kappa}+\bar{\alpha}}$$ modelling the same about $$\bar{\kappa}$$, and $$L_{\bar{\kappa}}\models\mathrm{ZFC}$$, and there is a surjection $$f:\omega\to\bar{\kappa}+\bar{\alpha}$$ in $$L_{\bar{\kappa}+\bar{\alpha}+1}$$.)

Proof: I'm going to work with the $$\mathcal{J}$$-hierarchy, not the $$L$$-hierarchy, since particularly for dealing with successor levels, the $$\mathcal{J}$$-hierarchy is smoother. This doesn't affect the outcome, because we will have $$\mathcal{P}(M)\cap\mathcal{J}_\alpha(M)=\mathcal{P}(M)\cap L_\alpha(M)$$ for each ordinal $$\alpha$$, and hence they agree about when a wellorder of $$M$$ is constructed. (It is easy enough to see that in fact $$L_\alpha(M)\subseteq \mathcal{J}_\alpha(M)$$ for each $$\alpha$$; for the converse, one must code $$\mathcal{J}_\alpha(M)$$ over $$L_\alpha(M)$$, uniformly enough in $$\alpha$$.) If one prefers to work only with the $$L$$-hierarchy, one should be able to translate everything that follows into it (swapping $$\mathcal{J}_\beta$$ for $$L_\beta$$ and $$\mathcal{J}_\beta(M)$$ for $$L_\beta(M)$$), but then the proof would directly involve more coding work. Recall that if $$\beta$$ is sufficiently closed then $$\mathcal{J}_\beta=L_\beta$$; this holds in particular for $$\Omega$$, since $$L_\Omega\models\mathrm{ZFC}$$.

The plan is to obtain $$M$$ as a class generic extension of $$\mathcal{J}_\Omega$$, via generic $$G$$, setting $$M=\bigcup_{\alpha<\Omega}\mathcal{J}_\Omega[G\upharpoonright\alpha]$$ (in particular, $$G$$ itself is not included as a predicate of $$M$$), and with enough symmetry that by taking $$G$$ generic over $$\mathcal{J}_{\Omega+\alpha}$$, $$\mathcal{J}_\alpha(M)$$ cannot have a wellorder of $$M$$; but using that $$\mathcal{J}_{\Omega+\alpha+1}$$ has a surjection $$f:\omega\to \mathcal{J}_{\Omega+\alpha}$$, we will take $$G\in \mathcal{J}_{\Omega+\alpha+1}$$, and we therefore get a surjection $$g:\omega\to M$$ in $$\mathcal{J}_{\alpha+1}(M)$$. It will be similar to the standard construction of models of ZF + $$\neg\mathrm{AC}$$ of the form $$\mathrm{HOD}(\mathbb{R}^*)^{V[G]}$$, for some reasonably symmetric set of reals $$\mathbb{R}^*$$, and some generic $$G$$ for some homogeneous forcing. But it is finer in detail, since we are aiming for choice to fail right up to some point, and then to hold right after that.

So, work for the moment in $$\mathcal{J}_\Omega$$; we specify the forcing. For $$\kappa$$ regular let $$\mathbb{P}_\kappa$$ be the forcing to add a subset of $$\kappa$$ via conditions $$f:\beta\to 2$$ for $$\beta<\kappa$$, and let $$\mathbb{P}$$ be the class product of all such $$\mathbb{P}_\kappa$$, with set-sized supports in the indices $$\kappa$$. (That is, conditions are functions $$f:R\to V$$ where $$R$$ is a set of regular cardinals and $$f(\kappa)\in\mathbb{P}_\kappa$$ for each $$\kappa\in R$$, and the ordering is by extension.) Note that for each regular $$\gamma$$, we can factor $$\mathbb{P}$$ as $$(\mathbb{P}\upharpoonright\gamma)\times(\mathbb{P}\upharpoonright[\gamma,\infty))$$, and $$\mathbb{P}\upharpoonright[\gamma,\infty)$$ is $${<\gamma}$$-closed.

Using the enumeration $$f:\omega\to \mathcal{J}_{\Omega+\alpha}$$ in $$\mathcal{J}_{\Omega+\alpha+1}$$, let $$G\in \mathcal{J}_{\Omega+\alpha+1}$$ be such that $$G$$ is $$(\mathcal{J}_{\Omega+\alpha},\mathbb{P})$$-generic (here I mean generic for all dense sets which are elements of $$\mathcal{J}_{\Omega+\alpha}$$; recall $$\alpha>0$$, so this includes all dense sets which are definable from parameters over $$\mathcal{J}_\Omega$$.) Let $$M$$ be defined as indicated above. Then $$M\models\mathrm{ZFC}$$.

Because we have a surjection $$h:\omega\to L_{\Omega}$$ with $$h\in\mathcal{J}_{\Omega+\alpha+1}$$, and $$G\in\mathcal{J}_{\Omega+\alpha+1}$$, we get a surjection $$g:\omega\to M$$ with $$g\in \mathcal{J}_{\Omega+\alpha+1}\subseteq \mathcal{J}_{\alpha+1}(M)$$.

So we just need to see there is no wellorder of $$M$$ in $$\mathcal{J}_\alpha(M)$$. This takes some work regarding the forcing details, but other than that, it is like in the constructions of models of $$\neg\mathrm{AC}$$ like mentioned above.

One first needs to work through the forcing details, to see level-by-level that $$\mathcal{J}_{\Omega+\beta}$$ has names for all elements of $$\mathcal{J}_\beta(M)$$, and the forcing relation is level-by-level and quantifier-by-quantifier appropriately definable. (Such level-by-level forcing calculations are commonly used in inner model theory, so there are some papers where they can be found). Here is a sketch of what we need in this case. At the level of $$\mathcal{J}_\Omega$$ and $$M$$ itself, note that all elements of $$M$$ have names in $$\mathcal{J}_\Omega$$, and the $$\Sigma_n$$-forcing relation is $$\Sigma_{n+k}$$, for some fixed $$k$$, uniformly in $$n$$. Then proceed inductively on $$\beta>0$$. Define canonical names for elements of $$\mathcal{J}_\beta(M)$$, corresponding to how things are defined in the $$\mathcal{J}$$-hierarchy; these are natural kinds of symmetric names. E.g. the subsets of $$M$$ which are in $$\mathcal{J}_1(M)$$ are just those which are definable from parameters over $$M$$, so we can take names for such sets as being tuples $$\sigma=(\varphi,\tau)$$ where $$\tau\in\mathcal{J}_\Omega$$ is a $$\mathbb{P}$$-name and $$\varphi$$ is a formula, and then this name gets interpreted as $$\sigma_G=\{y\in M\bigm|M\models\varphi(y,\tau_G)\}$$. These canonical names should, moreover, each have a certain support in $$\mathcal{J}_\Omega$$, corresponding to some bound on the parameters in $$M$$ needed to define the object in the generic extension $$\mathcal{J}_\beta(M)$$. That is, if a set $$A\subseteq M$$ is defined over $$M$$ from $$x\in M$$, then we can say that $$\gamma$$ is the support of $$A$$, where $$\gamma$$ is least with $$x\in V_\gamma^M$$. Higher up, if $$A\in\mathcal{J}_{\beta+1}(M)$$ is defined over $$\mathcal{J}_\beta(M)$$ from parameters $$x_1,\ldots,x_n\in\mathcal{J}_\beta(M)$$, then these $$x_i$$'s already have some supports $$\gamma_i<\Omega$$, then their supremum gives a support for $$A$$. The canonical names are just codes for these kinds of definitions of objects from finitely many ordinals and elements of $$M$$, and hence can also be assigned some support $$<\Omega$$. For $$\beta>0$$, the $$\Sigma_n$$-forcing relation over $$\mathcal{J}_{\Omega+\beta}$$ (for $$\Sigma_n$$ facts about $$\mathcal{J}_\beta(M)$$) will be $$\Sigma_{n+k}$$-definable over $$\mathcal{J}_{\Omega+\beta}$$ in the parameter $$\Omega$$, with some fixed $$k$$, uniformly in $$\beta$$. (Actually you can state it much more precisely than this, but one has to think a bit about what exactly the "$$\Sigma_n$$ forcing relation" should mean.))

Now suppose for a contradiction that we have a wellorder $$<^*$$ of $$M$$ in $$\mathcal{J}_\alpha(M)$$. Then we get a canonical name $$\tau\in\mathcal{J}_{\Omega+\alpha}$$ such that $$\tau_G={<^*}$$ (and here note the canonical name $$\tau$$ gets interpreted naturally in the $$\mathcal{J}_\beta(M)$$ hierarchy). Since $$M\models\mathrm{ZFC}$$, from $$<^*$$, it is easy to recover a surjection $$g:\Omega\to M$$ (consider the $$<^*$$-least wellorder of $$V_\alpha^M$$, for each $$\alpha<\Omega$$, and use these wellorders (which are each in $$M$$) to define $$g$$). So we get such a $$g\in\mathcal{J}_\alpha(M)$$. Let $$\gamma<\Omega$$ be a support for $$g$$. Then $$g$$ is defined over some $$\mathcal{J}_\beta(M)$$, where $$\beta<\alpha$$, from ordinal parameters and parameters in $$V_\gamma^M\subseteq \mathcal{J}_\Omega[G\upharpoonright\xi]$$ for some $$\xi<\Omega$$. Let $$X=G_\kappa$$ be the generic subset of some $$\mathcal{J}_\Omega$$-regular $$\kappa\geq\xi$$. Then $$X\in M$$ but $$X\notin\mathcal{J}_{\Omega+\alpha}[G\upharpoonright\xi]=\mathcal{J}_\alpha(\mathcal{J}_\Omega[G\upharpoonright\xi])$$, since $$G$$ is $$\mathcal{J}_{\Omega+\alpha}$$-generic. Let $$\zeta<\Omega$$ be such that $$X=g(\zeta)$$. Now noting that $$\mathbb{P}\upharpoonright[\xi,\Omega)$$ is sufficiently homogeneous, we see that $$X$$ is actually definable over $$\mathcal{J}_{\Omega+\beta}[G\upharpoonright\xi]$$, hence $$X\in\mathcal{J}_{\Omega+\alpha}[G\upharpoonright\xi]$$, a contradiction.

• This is really fantastic. Thank you! – Kameryn Williams Apr 24 at 0:22
• This argument can also be used to show that a proper class of ordinals are of the form $\upsilon(M)$ if there is a proper class of inaccessibles: Work in $L$ and let $\alpha$ be given. One can find a regular $\kappa$ and $\kappa<\Omega<\Omega+\alpha\leq\mu<\kappa^+$ so that $L_\Omega\models\mathrm{ZFC}$, $\Omega$ is still a cardinal in $L_\mu$ and $L_\mu^{<\kappa}\subseteq L_\mu$. This is enough to construct a $G$ in $L$ that is $(\mathbb P\upharpoonright [\kappa,\infty))^{L_\Omega}$-generic over $L_\mu$ and take $M=L_\Omega[G]$. Then $\alpha<\upsilon(M)<\kappa^+$. – Andreas Lietz Apr 25 at 22:11
• @KamerynWilliams No worries :) I think it’s a very good question. – Farmer S Apr 27 at 10:25
• @AndreasLietz Good point! Do we want $\Omega$ inaccessible in $L_\mu$ (which of course we also can get)? – Farmer S Apr 27 at 10:26
• @FarmerS Yes you are right, we definately want that! – Andreas Lietz Apr 27 at 11:12

Here's a quick "coarse" observation: certainly arbitrarily large countable values of $$v$$ are possible.

Let $$A$$ be a countable constructible transitive model of $$\mathsf{ZF'+\neg AC}$$, where $$\mathsf{ZF'}$$ is a "sufficiently strong" finite fragment of $$\mathsf{ZF}$$, and $$\alpha\in A$$ such that $$M=(V_\alpha)^A$$ is not well-orderable in $$A$$. Then since $$A$$ is countable and constructible we have $$v(M)<\omega_1$$; on the other hand, by the absoluteness of the $$L$$-hierarchy we get $$v(M)>A\cap\mathsf{Ord}$$ since for each $$\beta\in A\cap\mathsf{Ord}$$ we have $$L_\beta(M)=L_\beta(M)^A\subseteq A$$. The result then follows by picking "tall" $$A$$s.

And of course we can extend this past $$\omega_1$$ as long as we can find taller models of $$\mathsf{ZF+\neg AC}$$. In the other direction, by a Lowenheim-Skolem argument the set of cardinalities of values of $$v$$ is closed downwards in the infinite cardinals.

Separately, re: the use of $$I_0$$ note that "$$v$$ is not total" is equivalent to "There is an inner model of $$\mathsf{ZF+\neg AC}$$" so large cardinals aren't necessary. On the other side of things, the nonexistence of inner models breaking choice is strictly weaker than $$\mathsf{V=L}$$; for example, I believe it's preserved by Sacks forcing (basically, adding a single new degree of constructibility isn't going to "make room" for inner models where choice fails if they didn't exist already - but I haven't checked the details on this).