My question is about a kind of relative constructibility in set theory.

Fix a countable transitive model $W\models ZFC$ which is much bigger than $L^W$. There is a natural way within $W$ to compare how non-constructible one set is relative to another: $A$ is constructible relative to $B$ - and write $A\le_L B$ - if $A\in L[B]$. This is the direct analogue of the relation "computable relative to," $\le_T$.

There is another notion of relative constructibility that I haven't seen before, as follows. By a theorem of Barwise, given any set $A\in W$ there is an (ill-founded) end extension $W'$ of $W$ such that $W'\models A\in L$. In light of this, we can consider the following relation:

  • Say $A$ is as $L$-ish as $B$ - and write $A\le_{L, end}B$ - if for every end extension $W'$ of $W$, "$W'\models B\in L$" implies "$W'\models A\in L$."

My question is:

Is there a nice description of $\le_{L, end}$ - or an interesting subrelation, such as $\le_{L, end}$ restricted to $\mathbb{R}^W$ - without referring to end extensions?

In general, what can we say about $\le_{L, end}$, or the induced degree structure (especially in relation to what large cardinal axioms are satisfied in $W$ or the "real" universe $V$ in which $W$ lives)?

In particular:

Is $\le_{L, end}$ the same as $\le_L$?

  • 1
    $\begingroup$ +1 Great question! The theorem you mention is due to Barwise, and you can find discussion and proof in my recent paper: A multiverse perspective on the axiom of constructibility jdh.hamkins.org/multiverse-perspective-on-constructibility. $\endgroup$ Jun 12 '14 at 20:47
  • 1
    $\begingroup$ It seems that your relation could depend on the countable transitive model (which you call $V$), and perhaps also on which extensions $W$ are available in the larger set-theoretic background (which I would prefer to call $V$). Is there reason to suspect that the relation itself is available inside your countable $V$? $\endgroup$ Jun 12 '14 at 20:50
  • $\begingroup$ Whoops - I forgot to say who the result was due to! And I've fixed the names of models to be less confusing. I don't see a reason to believe that this relation is independent of either the c.t.m. or the properties of the real universe, and I don't see any reason why it should be definable inside the c.t.m. - which is why I have hope that it's different from $\le_L$. I do suspect, though, that a reasonably detailed picture of $\le_{L, end}$ might follow from e.g. assuming that $V$ and $W$ satisfy appropriate large cardinal axioms, which would be cool. (Also, thanks for the link to your paper!) $\endgroup$ Jun 12 '14 at 21:08
  • $\begingroup$ Let me add that the term "end-extension" here, as I'm sure you know but I mention it because sometimes some find it confusing, refers to a larger model that does not add new elements to old elements. In other words, $W$ is transitive in $W'$. This is very different, of course, from a top-extension, where the new elements of $W'$ all have rank exceeding any ordinal of $W$. Thus, every ground model $W$ is end-extended by its nontrivial forcing extensions $W[G]$, but never top-extended by them. $\endgroup$ Jun 12 '14 at 21:09
  • $\begingroup$ Haven't you got the order backwards? That is, in order for $A\leq B$, you would want that whenever $B$ is in $L^{W'}$, then also $A\in L^{W'}$. But this is the opposite of what you've written. $\endgroup$ Jun 12 '14 at 21:21

This is a fascinating question! I really like your relation.

Here is some small progress. (I am hopeful that more definitive answers will appear later).

First, you didn't mention it, but for definiteness let's record the fact that $\leq_L$ is included in $\leq_{L,end}$. That is, if $W\models A\leq_L B$, then also $A\leq_{L,end}B$ with respect to $W$. The reason is that if $W\subset W'$ is an end-extension with $B\in L^{W'}$, then since the ordinals of $W'$ agree with the ordinals of $W$ up to the height of $W$, it follows that when $W'$ constructs its version of $L[B]$, it will see that $A$ is added at the same stage that puts $A\in L[B]$ from the perspective of $W$.

Second, someone might worry that whenever you have an end-extension $W\subset W'$ with $B\in L^{W'}$, even though $B\notin L^W$, then it might put all of $W$ into $L^{W'}$. In other words, one might worry that $\leq_{L,end}$ collapses everything to one equivalence class. But let me prove that this isn't the case, even when one considers only well-founded extensions.

To see this, suppose we have $L_\alpha\models\text{ZFC}$ and some larger countable $L_\beta\models\text{ZFC}$, with $L_\beta\models\alpha$ is countable. So inside $L_\beta$ there is an $L_\alpha$-generic Cohen real $B$. Now, let $A$ be an $L_\beta$-generic Cohen real, which is of course also $L_\alpha$-generic and indeed $L_\alpha[B]$-generic. Consider $W=L_\alpha[A,B]$. It is easy to check that this is end-extended by $W'=L_\beta[A,B]=L_\beta[A]$. Since $B\in L_\beta^{W'}=L_\beta$ and $A\notin L^{W'}$, it follows that $A\not\leq_{L,end} B$ with respect to $W$. And so the relation does not collapse to a single equivalence class.

It seems to me that one will be able to use this kind of reasoning to show that other interesting things happen.

Update. Here is a negative answer to your final question for the version of your relation where one allows only well-founded models $W$ and $W'$. That is, if $W$ is a countable transitive model of ZFC and $W\subset L$ (but not necessarily $W\models V=L$), define $A\leq_{L,end,wf}B$ for $A,B\in W$ just in case whenever $W'$ is a transitive end-extension of $W$ and $B\in L^{W'}$, then also $A\in L^{W'}$. We should probably assume that there are unboundedly many countable $L_\alpha$ modeling ZFC for this to be robust.

Theorem. In this context, $\leq_{L,end,wf}$ can differ from $\leq_L$ in the sense of $W$.

Proof. Let $L_\alpha$ and $L_\beta$ be as above, and choose $A$ to be $L$-least in $L_\beta$ that is an $L_\alpha$-generic Cohen real, and let $B$ be any $L_\beta$-generic Cohen real with $B\in L$. Thus, $A,B$ are mutually $L_\alpha$-generic Cohen reals, and $W=L_\alpha[A,B]$ is a model of ZFC. By mutual genericity, $W$ thinks $A\not\leq_LB\not\leq_LA$. But meanwhile, any well-founded $W'$ extending $W$ for which $B\in L^{W'}$ must be at least $\beta$ in height, and so $A\in L^{W'}$ as well. So $A\leq_{L,end,wf}B$. So the orders are different. QED


Here is an extension of Barwise's theorem which may be of some use.

Theorem. Fix a real $a \subseteq \omega$ in $W$. Suppose the preorder $\preceq$ is first-order definable with parameter $a$ and that $$L[a] \vDash (\forall x,y \in \mathbb{R})(x \leq_L y \Leftrightarrow x \preceq y).$$ Then there is an end-extension $W'$ of $W$ such that $$W' \vDash (\forall x,y \in \mathbb{R})(x \leq_L y \Leftrightarrow x \preceq y).$$

The proof is similar to Barwise's. In fact, Barwise's theorem is the special case where $a = \varnothing$ and $x \preceq y$ is always true.

Let $T$ be consist of ZF together with the infinitary diagram of $W$ and a constant for the parameter $a$; we need to show that $$T_0 + (\forall x,y \in \mathbb{R})(x \leq_L y \Leftrightarrow x \preceq y)$$ is satisfiable (where the parameter $a$ in the definition of $\preceq$ is replaced by the corresponding constant).

By the Barwise Completeness Theorem, if this theory is not satisfiable then there is an infinitary proof in $W$ of $$\lnot(\forall x,y \in \mathbb{R})(x \leq_L y \Leftrightarrow x \preceq y)$$ from $T_0$. The existence of such a proof is a $\Sigma_1$ statement with parameter $a$. Therefore, by Lévy–Shoenfield absoluteness relativized with the parameter $a \subseteq \omega$, there is such a proof in $L[a]$. In the sense that there is a proof of $$\lnot(\forall x,y \in \mathbb{R})(x \leq_L y \Leftrightarrow x \preceq y)$$ from the theory $T'_0$ consisting of ZF together with the infinitary diagram of $L[a]$ and a constant for the parameter $a$. But this is absurd since $L[a]$ is a model of $T'_0$ and $$L[a] \vDash (\forall x,y \in \mathbb{R})(x \leq_L y \Leftrightarrow x \preceq y).$$

Therefore, there must be a model $W'$ of $T_0$ such that $$W' \vDash (\forall x,y \in \mathbb{R})(x \leq_L y \Leftrightarrow x \preceq y).$$ Since $T_0$ contains the infinitary diagram of $W$, this $W'$ is the required end-extension of $W$.

There is a catch with this extension: the preorder $\preceq$ is a formula so its meaning can change drastically from $W$ to $W'$. In the ideal case, preorder is provably $\Delta_1$ in ZF, in which case $W$ and $W'$ must agree on its meaning. Unfortunately, except for Barwise's striking example, it's not easy to come up with other examples.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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