14
$\begingroup$

My question is about a variant of the usual notion of relative constructibility, $\le_c$ (which an earlier version of this question confusingly denoted "$\le_L$"), in set theory.

Fix a countable transitive model $W\models\mathsf{ZFC+V\not=L}$. By a theorem of Barwise, given any set $A\in W$ there is a (possibly-ill-founded) end extension $W'\supseteq_{end}W$ such that $W'\models A\in L$. In light of this, we can consider the following preorder on elements of $W$: $$A\le_{L,end}B\quad:=\quad\forall W'\supseteq_{end}W[W'\models \mathsf{ZFC}+B\in L\implies W'\models A\in L].$$

Broadly speaking, I'm interested in whether there is 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 - and in general, anything we can say about $\le_{L, end}$, or the induced degree structure.

To keep things reasonably concrete, the following specific question seems natural:

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

I'm especially interested in the situation where $V$ satisfies strong large cardinal axioms (say, "There is a proper class of Woodins) and $W$ is "far from $L$" (say, $\mathbb{R}^W$ is closed under sharps).

$\endgroup$
7
  • 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$ Commented Jun 12, 2014 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$ Commented Jun 12, 2014 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$ Commented Jun 12, 2014 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$ Commented Jun 12, 2014 at 21:09
  • 1
    $\begingroup$ If the B is short for Billie, she is indeed Eilish. $\endgroup$
    – Asaf Karagila
    Commented Feb 15, 2022 at 6:21

3 Answers 3

3
+500
$\begingroup$

Remarks:

(i) I'm interpreting the definition of $\leq_{L,\mathrm{end}}$ as quantifying over set models $W'$, not proper classes.

(ii) I'm considering the main question (comparing the two orders), particularly in the case that $V$ has large cardinals, but mainly not in the case of "particular interest", i.e. where $W$ is far from $L$; some remarks on the latter case are made in the "Edit" at the bottom.)

Claim: Assume ZF + there are ordinals $\kappa<\lambda$ such that $L_\kappa\models$ZFC and $L_\lambda\models$ZFC and $\kappa$ is a cardinal in $L_\lambda$. Let $\psi$ be the statement "there is a countable transitive $W\models$ZFC such that defining $\leq_{L,\mathrm{end}}$ w.r.t. $W$, then $\leq_{L,\mathrm{end}}$ is different to $\leq_{\mathrm{c}}\upharpoonright W$". Then:

(i) There is a forcing extension $V[G_1]$ of $V$ such that $V[G_1]\models\psi$, and

(ii) If every real has a sharp (in particular, if there is a measurable cardinal), then $\psi$ holds in $V$.

In fact, we will get the two orders to disagree over $\mathbb{R}^W$.

Proof: The proofs of (i) and (ii) are almost the same, so I'll deal with them simulatenously.

Let $\lambda$ be least as hypothesized, and $\kappa$ the corresponding ordinal. Then $L_\lambda$ is pointwise definable by condensation etc, so $\lambda<\omega_1$, and there is a bijection $\pi:\omega\to\lambda$ with $\pi\in L_{\lambda+2}$. If every real has a sharp, then we can find a sequence $\vec{y}=\left<y_\alpha\right>_{\alpha<\lambda}$ of reals such that $y_\alpha<_{\mathrm{c}}y_\beta$ for $\alpha<\beta<\lambda$, and in fact with $\vec{y}\upharpoonright \beta\in L[y_\beta]$ for each $\beta<\lambda$. In any case, we can easily force the existence of such a sequence of reals. So from now on we assume that there is such a sequence.

We will find a sequence $G=\left<x_n\right>_{n<\omega}$ which is generic over $L_\lambda$ for the $\omega$-fold finite support product $\mathbb{C}^{<\omega}$ of Cohen forcing, such that setting $W=L_\kappa[G]$ (not $W=L_\lambda[G]$), we have $\leq_{\mathrm{c}}\upharpoonright X$ is a wellorder of ordertype $\lambda$, where $X=\{x_n\}_{n<\omega}$, and hence this order is not in $W$ (in fact not in $L_\lambda[G]$).

However, we do have $\leq_{L,\mathrm{end}}\upharpoonright X\in W$. For this, it suffices to see it is in $L_\lambda[G]$. And for this, it suffices to see it is in $L_\lambda[G,H]$ whenever $H$ is $L_\lambda[G]$-generic for $\mathrm{Coll}(\omega,\kappa)$ (by Solovay's theorem on this business; alternatively use homogeneity of the forcing and the uniformity of the next sentence). For the latter, we observe that $\leq_{L,\mathrm{end}}\upharpoonright X$ is $\Pi^1_1(\{z\})$ whenever $z$ is a real coding $L_\kappa[G]$, and since $L_\lambda[G,H]\models$ZFC and is transitive, it is therefore in $L_\lambda[G,H]$. For the $\Pi^1_1(\{z\})$-definability, it is easy assuming ZF+DC, as if there is an uncountable counterexample $W'$ to the $\forall W'$ quantifier, we can get a countable one by taking a countable hull (cf. Remark (i) at the start). Without DC we can still do a variant of this. Suppose $W'$ is a counterexample. Let $W''=L^{W'}$, and note that $W''$ is still a counterexample. Now let $W'''$ be the definable hull in $W''$ of parameters in $W\cup\{W\}$ (recalling $A,B\in W$); since $W''$ models "$V=L$", this gives an elementary substructure, and it is countable, so $W'''$ is a countable counterexample, as desired.

So we need to construct $G$.

Let $T\subseteq{^{<\omega}}2$ be a perfect tree. Recall that $t\in T$ is a \emph{splitting node} of $T$ iff $t\frown(0)\in T$ and $t\frown(1)\in T$ (this is defined in the same manner for finite trees below). Given a real $x$, let $b_x$ be the infinite branch through $T$ determined by using $x(n)$ as the bit of $b_x$ following the $n$th splitting node along $b_x$. So the map ${^\omega}2\to[T]$ (the codomain is the set of branches of $T$) sending $x\mapsto b_x$ is a bijection. Note that if $T\in L$, then $x\equiv_{\mathrm{c}}b_x$.

Lemma: There is a perfect tree $T\subseteq {^{<\omega}}2$, with $T\in L$, such that for every finite sequence $\vec{b}=(b_0,\ldots,b_{m-1})$ of pairwise distinct branches $b_i$ through $T$, $\vec{b}$ is $L_\lambda$-generic for $\mathbb{C}^m$ (the $m$-fold product of Cohen forcing).

Proof: For $m\in[1,\omega)$, let $\mathscr{D}_m$ be the set of all open dense $D\subseteq\mathbb{C}^m$ such that $D\in L_\lambda$. Let $\mathscr{D}=\bigcup_{m\in[1,\omega)}\mathscr{D}_n$. Fix an enumeration $\vec{D}=\left<D_n\right>_{n<\omega}$ of $\mathscr{D}$, such that each $D\in\mathscr{D}$ gets repeated infinitely often, and such that $\vec{D}\in L$. Let $m_n$ be the arity of $D_n$ (that is, $D_n\subseteq\mathbb{C}^{m_n}$). We construct a sequence $\left<T_n\right>_{n<\omega}$ of finite trees $T_n\subseteq{^{k_n}2}$ where $k_n<\omega$, such that:

(i) $T_0=\{\emptyset\}$ and $k_0=0$,

(ii) for all maximal nodes $t$ of $T_n$, we have $\mathrm{lh}(t_n)=k_n$,

(iii) for all maximal nodes $t$ of $T_n$, there are exactly $n$ splitting nodes $s$ of $T_n$ such that $s\subseteq t$ (so $s\subsetneq t$, since $t$ is maximal),

(iv) for each $i<n$, we have $T_i=\{t\upharpoonright k_i\bigm|t\in T_n\}$, and each maximal node of $T_i$ is a splitting node of $T_n$ (so $k_i<k_n$), and

(v) for each $i<n$, letting $m=m_i$, we have $\vec{t}\in D_i$ for each $m$-tuple $\vec{t}=(t_0,\ldots,t_{m-1})$ of pairwise distinct maximal nodes $t_i$ of $T$.

The construction is straightforward by density: given $T_n$, construct $T_{n+1}$ by first adding $t\frown(0)$ and $t\frown(1)$ to $T_{n+1}$ for each maximal $t$ of $T_n$, and then letting $m=m_n$, successively extend the $m$-tuples of distinct so-far-maximal nodes so as to get them into $D_n$. Since there are only finitely many such $m$-tuples, this is achieved after finitely many extensions, and then we just extend every node further up to some common length $k_{n+1}$ (note there the longest splitting nodes of $T_{n+1}$ are the maximal nodes of $T_n$).

Setting $T=\bigcup_{n<\omega}T_n$, we claim this works. For let $\vec{b}=(b_0,\ldots,b_{m-1})$ be an $m$-tuple of distinct branches through $T$. Let $n_0$ be large enough that $b_i\upharpoonright k_{n_0}\neq b_j\upharpoonright k_{n_0}$ whenever $0\leq i<j<m$. Then at every stage $n\in[n_0,\omega)$ such that $m_n=m$, we ensured that $(b_0\upharpoonright k_{n+1},\ldots,b_{m-1}\upharpoonright k_{n+1})\in D_n$. Since every open dense $D\subseteq\mathbb{C}^m$ in $L_\lambda$ gets repeated infinitely often in the enumeration, it follows that $(b_0,\ldots,b_{m-1})$ is $L_\lambda$-generic, as desired. This completes the proof of the lemma.

Now let $z_n=y_{\pi(n)}$ for $n<\omega$ (recall $\left<y_\alpha\right>_{\alpha<\lambda}$ and $\pi:\omega\to\lambda$ from earlier). Let $b_n=b_{z_n}$ be the branch induced by $z_n$ (as described earlier). So ($*$) for all finite $m$-tuples of distinct integers $(n_0,\ldots,n_{m-1})$, $(b_{n_0},\ldots,b_{n_{m-1}})$ is generic over $L_\lambda$ for $\mathbb{C}^m$. However, we don't know that the full sequence $\left<b_n\right>_{n<\omega}$ is generic over $L_\lambda$ for the $\omega$-fold finite support product $\mathbb{C}^{<\omega}$ of $\mathbb{C}$. But by a standard trick, using ($*$), we can modify each $b_n$ on at most finitely many digits, producing a sequence $\left<b'_n\right>_{n<\omega}$ which is $L_\lambda$-generic for $\mathbb{C}^{<\omega}$. (Enumerate the dense subsets of $\mathbb{C}^{<\omega}$ in $L_\lambda$ as $\left<E_n\right>_{n<\omega}$, and progressively extend conditions $p_n$ getting into $E_n$, such that, letting $p_{ni}$ be the projection of $p_n$ to the $i$th component, and letting $A_i=\mathrm{dom}(p_{ni})$, we ensure that for $n'>n$, we have that $p_{n'i}$ agrees with $b_n$ outside of $A_i$. This can be achieved using (*), since $\mathbb{C}^{<\omega}$ factors nicely.)

Now let $G=\left<b'_n\right>_{n<\omega}$. So $G$ is generic over $L_\lambda$ for $\mathbb{C}^{<\omega}$, and note that since $b'_n$ eventually agrees with $b_n$, we have $b'_n\equiv_{\mathrm{c}} b_n\equiv_{\mathrm{c}}z_n=y_{\pi(n)}$. Therefore letting $X=\{b'_n\}_{n<\omega}$, the restriction $\leq_{\mathrm{c}}\upharpoonright X$ is just a wellorder of length $\lambda$, as desired.


Edit: Consider now the case that $W$ is closed under sharps, assuming that $V$ is closed under sharps for reals. Then the preceding argument does not work, and in fact we have the following (related to some things Hamkins wrote in his answer above):

Theorem 2: Assume ZF + for every real $x$, $x^\#$ exists. Let $W$ be a countable transitive model of ZFC which is closed under (true) sharps. Define $\leq_{L,\mathrm{end}}$ w.r.t. $W$. Let $A,B\in W$. Then $A\leq_{\mathrm{c}}B$ implies $A\leq_{L,\mathrm{end}}B$.

Proof: Suppose $A\leq_{\mathrm{c}}B$, i.e. $A\in L(B)$. Then since $B^\#\in W$, it follows that $A\in L^W(B)=L_{\mathrm{OR}^W}(B)$. Let $W'$ be any end-extension of $W$ which models ZFC with $B\in L^{W'}$. If $\mathrm{OR}^{W'}=\mathrm{OR}^W$ then $L^{W'}=L^W$, so $B\in L^W$, so $L^W(B)=L^W$, so $A\in L^W=L^{W'}$. Suppose instead that $\mathrm{OR}^W\neq\mathrm{OR}^{W'}$. Let $\gamma$ be the least $W'$-ordinal such that $B\in L^{W'}$ (note $\gamma$ might be illfounded). Let $\alpha\in\mathrm{OR}^W$ be such that $A\in L_\alpha(B)$. Then $\alpha\in\mathrm{OR}^{W'}$, so $\gamma+\alpha$ makes sense in $W'$ and $\gamma+\alpha\in\mathrm{OR}^{W'}$, which easily implies that $L_\alpha(B)\subseteq L^{W'}$, so $A\in L^{W'}$, as desired.

$\endgroup$
6
  • $\begingroup$ Thanks for this, this is great (as usual)! Re: (ii), I've fixed my notation (I've seen "$\le_c$" used, but not "$\le_{rc}$," so I've gone with the former). Re: (i), does it actually matter if we look at class models $W'$? I think even restricting attention to countable set models $W'$ should give the same notion, since $W$ is countable (or am I missing something?). It will take me some time to read this answer in detail, but I suspect I'll accept and bounty it by the end of this coming weekend. $\endgroup$ Commented Feb 16, 2022 at 18:57
  • $\begingroup$ No worries! Okay, $\leq_c$ seems better. Re (i), why couldn't the "for all $W'$" quantifier hold over all set-sized end extensions, but fail for some proper class $W'$? $\endgroup$
    – Farmer S
    Commented Feb 16, 2022 at 22:09
  • $\begingroup$ Is this a global choice issue? At least within the context of set-sized extensions, it seems to me that via dLS a set-sized witness to failure implies a countable witness to failure, is that right? $\endgroup$ Commented Feb 16, 2022 at 22:22
  • $\begingroup$ Well...for set-sized models and with DC, yes directly; without DC I used a variant of that argument above. But that needn't work for a proper class model, even with global choice. $\endgroup$
    – Farmer S
    Commented Feb 16, 2022 at 22:41
  • $\begingroup$ Ah, I missed that you weren't assuming choice in $V$! That clarifies things. (And also yes, I was overestimating the power of global choice.) $\endgroup$ Commented Feb 17, 2022 at 17:12
8
$\begingroup$

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_c$ is included in $\leq_{L,end}$. That is, if $W\models A\leq_c 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_c$ 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_cB\not\leq_cA$. 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

$\endgroup$
4
$\begingroup$

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_c 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_c 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_c 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_c 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_c 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_c 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_c 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.

$\endgroup$

You must log in to answer this question.

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