10
$\begingroup$

Suppose $\mathbb{V} = \mathbb{L}$ and there is a countable transitive model $\mathbb{M}$ of $ZFC$.

Let $\rho$ be the $\mathbb{L}$-rank, i.e. for all $a \in \mathbb{V}$, $\rho(a) = $the least $\alpha$ with $a \in L_{\alpha+1}$.

Define a pre-order $<'$ on $M$ by $a <' b$ iff $\rho(a) < \rho(b)$.

Then my first question is: under what circumstances is $<'$ first-order definable over $\mathbb{M}$?

My second question is: supposing $(\mathbb{V} \not= \mathbb{L})^\mathbb{M}$, and given $a, b \in M \backslash \mathbb{L}^\mathbb{M}$, when does $\mathbb{M}$ "know" that $a <' b$?

Formally, when is there a formula $\phi(x, y)$ (without parameters) such that $\mathbb{M} \models \phi(a, b)$ and for all $a', b'$ with $\mathbb{M} \models \phi(a', b')$, we have $a' <' b'$?

$\endgroup$
4
  • $\begingroup$ Thinking about this has led me to the question: Suppose in $\mathbb{M}$ there is a class well-order of order type $\beta$ larger than $ORD^\mathbb{M}$. Can we (in $\mathbb{M}$) carry out the $L$-construction up to level $\beta$? I realize we will not be able to define classes-of-classes-of-classes within $\mathbb{M}$, but I wonder if we could still define 'small' objects (e.g. reals) that arise in $L_\beta$. $\endgroup$
    – jonasreitz
    Feb 2, 2013 at 3:52
  • 1
    $\begingroup$ If so, then I propose that we try to force over $\mathbb{M}$ to make $<'$ have very large order type $\beta$, so large that there is, in $L_\beta$, a function witnessing the countability of $ORD^\mathbb{M}$. Forcing to make the order type of $<'$ large presents its own challenge, but I envision adding $\omega$-many Cohen reals, carefully selected from appropriate levels of the $L$-hierarchy to give the correct order type. $\endgroup$
    – jonasreitz
    Feb 2, 2013 at 3:52
  • $\begingroup$ I don't know about the answer to the first question, although in $M$ we can define "names" for elements of $L_\beta$: namely, supposing $\phi$ is a well-order of $ORD$, let each $\alpha$ be a name of $L_\gamma$ where $\gamma$ is the order type of $\alpha$ with respect to $\gamma$; then, using these names and Godel's 8 $L$-generating functions, we can represent the formation of any $x \in L_\beta$ as a finite tree of ordinals. With these particular names, however, it is not obvious that determining whether one name contains another (say) is first-order definable. $\endgroup$ Feb 3, 2013 at 1:59
  • $\begingroup$ Sorry, I meant, $\alpha$ should be a name of $L_\gamma$, where $\gamma$ is the order type of $\alpha$ with respect to $\phi$. $\endgroup$ Feb 3, 2013 at 2:00

3 Answers 3

8
$\begingroup$

This is a great question, and very subtle.

Here is a way to see that the relation cannot be uniformly definable. Suppose $L_\alpha$ is a countable model of ZFC, and $\phi$ works as you say in every model of the form $L_\alpha[c]$, a forcing extension to add a Cohen real $c$, chosen from $L$. (Note that in $L$ we may easily find such $L_\alpha$-generic Cohen reals, since $\alpha$ is countable.)

Fix any such extension $M=L_\alpha[c]$, which is a model of ZFC. Let $c_0$ and $c_1$ be the even and odd digits of $c$, respectively. Suppose without loss that $c_0\leq'c_1$, meaning that $c_0$ appears in $L$ before or at the same rank as $c_1$. If $M$ can define this relation, then there must be some condition forcing this instance of it, and so there must be some finite initial segment $p\subset c$, such that any $L_\alpha$-generic Cohen real $d$ extending $p$ will have $\phi(d_0,d_1)$. But fix some $L_\alpha$-generic $d_1$ extending its part of $p$, and then find $d_0$ that is $L_\alpha[d_1]$-generic and extending its part of $p$, and very high in $\omega_1^L$. This is possible because there are continuum many different $L_\alpha[d_1]$-generic Cohen reals in $L$, and so some of them must have high rank; and changing a finite part of such a real does not affect rank. So now we have $L_\alpha[d]$ with $d_1\lt' d_0$ and $d$ extends $p$, a contradiction.

So it isn't uniformly definable. But as Andres points out, this approach doesn't even answer whether it might be definable nevertheless in a non-uniform way.

$\endgroup$
10
  • $\begingroup$ Joel, I thought of this, but one needs to argue that in $L_\alpha[c]$ will be Cohen reals that come from different $L$-levels, as $<'$ does not distinguish between sets of the same rank. $\endgroup$ Jan 29, 2013 at 16:45
  • $\begingroup$ (Also, $<'$ needs not be the relation defined in $L_\alpha[d]$ by the formula that happens to define it in $L_\alpha[c]$.) $\endgroup$ Jan 29, 2013 at 16:47
  • $\begingroup$ But there are continuum many Cohen reals, and so some of them must come from higher levels. The point is that you can make either $d_0$ or $d_1$ have very high rank, while respecting any finite condition $p$. $\endgroup$ Jan 29, 2013 at 16:48
  • $\begingroup$ About your second remark, you are right. What my argument shows is that there is no one formula that will work in all $L_\alpha[c]$'s. $\endgroup$ Jan 29, 2013 at 16:49
  • $\begingroup$ Joel, about the first issue, yes, of course; I only meant that the argument does not rule out all $L_\alpha[c]$. Nice question... $\endgroup$ Jan 29, 2013 at 16:59
3
$\begingroup$

[Edit: The question is more subtle than I originally understood. I am leaving this here so as to avoid it being repeated by others.]

You can define $<'$ internally only if $M$ is a model of $V=L$, that is, only if $M$ is an $L_\alpha$. For example, $M$ could be (in $L$) a forcing extension of some $L_\alpha$. Being in $L$, every point in $M$ has a rank, but we only see in $M$ the rank of points in $L^M=L_\alpha$. However, $<'$ restricted to $L^M$ is definable in $M$. The usual definition ($a,b\in L$ and $\rho(a)<\rho(b)$) relativizes, so its definition from the point of view of $M$ gives the same relation as the definition of $<'$ in $L$ restricted to elements of $L_\alpha$.

A decent reference to see how $<'$ relativizes and the amount of absoluteness involved is Devlin's book on "Constructibility".

$\endgroup$
5
  • $\begingroup$ Oops, of course. So that's the first question. I'm going to expand upon the second question; I didn't expect the first question to be so trivial. Sorry :( $\endgroup$ Jan 25, 2013 at 20:27
  • $\begingroup$ Wait, so the proof I was thinking of for your claim doesn't work. There are definable (proper class) well-orderings in $M$ of height greater than $ORD^M$. So I actually don't see your argument $\endgroup$ Jan 29, 2013 at 13:54
  • $\begingroup$ Hi Douglas, yes, you are right, I misunderstood the question when I first read it (your rephrasing clarifies the subtlety). $\endgroup$ Jan 29, 2013 at 15:54
  • $\begingroup$ Somebody posted a similar question mathoverflow.net/questions/120173/can-a-model-of-v-neq-l-contain-a-class-giving-the-l-ordering-on-all-its-sets/120212#120212 here, and they also were misunderstood. So there must be something confusing in the question $\endgroup$ Jan 29, 2013 at 15:57
  • $\begingroup$ @Andres, your answer still gives a useful starting point, since it shows that usual definition of the $L$-order will not suffice to define $<_L$ on all of $M$ -- but it's not clear whether another definition may be more successful. $\endgroup$
    – jonasreitz
    Jan 29, 2013 at 16:13
2
$\begingroup$

The following isn't an answer to your question, as it's only one example, but I'm not able to make comments here.

It can be definable over $M$, and quite simple. (However, note that for the model I'm going to mention, things are very different if one considers $L$-order of constructibility as opposed to just $L$-rank as defined in the question.)

Let $\lambda$ be least such that $L_\lambda\models$ ZFC and let $c$ be Cohen generic over $L_\lambda$, with $c\in L_{\lambda+2}$. (This is the least level of $L$ which contains such a Cohen generic; all bounded subsets of $L_\lambda$ which are in $L_{\lambda+1}$, are already in $L_\lambda$. But $L_\lambda$ is pointwise definable, and therefore $L_{\lambda+1}$ projects to $\omega$, and in fact, it is the $\Sigma_1$-hull of the single parameter $\{\lambda\}$ in $L_{\lambda+1}$, and using this, it is easy to define a generic $c$, and in fact, there is one which is $\Sigma_1$-definable from parameter $\{\lambda\}$.)

Now rank the sets in $L_\lambda[c]$ as follows, writing $W_\alpha$ for the sets of rank $<\alpha$. Rank $<\lambda$ is just the $L$-ordering, so $W_\lambda=L_\lambda$. Then $W_{\lambda+1}$ consists of the (bounded) subsets of $L_\lambda$ which are in $L_\lambda[c]$. More generally, given $W_\alpha$ where $\lambda\leq\alpha<\lambda+\lambda$, then $W_{\alpha+1}$ is the set of subsets of $W_\alpha$ which are in $L_\lambda[c]$. And take unions at limits.

Then note that $W_{\lambda+\lambda}=L_\lambda[c]$, and $\lambda+\lambda$ is least such (just by rank considerations). Clearly this ranking is definable over $L_\lambda[c]$. So it suffices to see that this ordering is exactly $L$-rank restricted to $L_\lambda[c]$.

For this, note first that every set in $W_{\lambda+1}$ is definable from parameters over $L_{\lambda+1}$. (Given $X\in W_{\lambda+1}$, just use a name in $L_\lambda$ for $X$ and the forcing relation and the generic $c$, each of which are definable from params over $L_{\lambda+1}$.) But no set in $Y\in L_\lambda[c]\backslash W_{\lambda+1}$ is in $L_{\lambda+2}$, because every such $Y$ contains some $X\in W_{\alpha}\backslash L_\lambda$ with $\alpha>\lambda$, for any such $X$, $X\notin L_{\lambda+1}$.

Similarly, the constructibility rank cannot be any quicker than the $W$-rank in general. So it suffices to see that the constructibility rank is quick enough. For this, let $N_\alpha$ be the $L_\lambda$-class of "rank $\alpha$ hereditarily nice names" (so every element of $L_\lambda[c]$ has such a nice name), starting with nice names for subsets of $L_\lambda$ being those in $N_0$. (So $W_{\lambda+1+\alpha}$ is the set of all $\tau_c$ for $\tau\in N_\alpha$, where here $\tau_c$ denotes the interpretation of $\tau$ using the generic $c$; and the sequence $\left<N_\alpha\right>_{\alpha<\lambda}$ is definable over $L_\lambda$.) One observes that the name evaluation function $\tau\mapsto\tau_c$, with domain $N_\alpha$, is definable over $L_{\lambda+2+\alpha}$, and basically uniformly in $\alpha$. This is straightforward.

In some more detail: The relation of variables $(\tau,x)$ that says "$\tau\in N_0$ and $x\in L_\lambda$ and $x\in\tau_c$" is definable over $L_{\lambda+1}$, and also $W_{\lambda+1}\subseteq L_{\lambda+2}$ and the relation of variables $(\tau,x)$ that says "$\tau\in N_0$ and $\tau_c=x$" is definable over $L_{\lambda+2}$. It follows that the relation of $(\tau,x)$ saying "$\tau\in N_1$ and $x\in W_{\lambda+1}$ and $x\in\tau_c$", is definable over $L_{\lambda+2}$, so $W_{\lambda+2}\subseteq L_{\lambda+3}$, etc. We get the evaluation functions themselves in finitely many steps later (exactly when of course depends on exactly how one codes ordered pairs etc, but this doesn't really matter), and the definitions are all uniform enough, so we can continue through limit stages.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.