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'$?

  • $\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 '13 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 '13 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$ – Douglas Ulrich Feb 3 '13 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$ – Douglas Ulrich Feb 3 '13 at 2:00

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.

  • $\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$ – Andrés E. Caicedo Jan 29 '13 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$ – Andrés E. Caicedo Jan 29 '13 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$ – Joel David Hamkins Jan 29 '13 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$ – Joel David Hamkins Jan 29 '13 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$ – Andrés E. Caicedo Jan 29 '13 at 16:59

[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".

  • $\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$ – Douglas Ulrich Jan 25 '13 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$ – Douglas Ulrich Jan 29 '13 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$ – Andrés E. Caicedo Jan 29 '13 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$ – Douglas Ulrich Jan 29 '13 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 '13 at 16:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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