User jonasreitz - MathOverflow

Can a model of $V\neq L$ contain a class giving the $L$-ordering on all its sets?

2013-01-29T03:03:59Z

This question is inspired by the excellent question by Douglas Ulrich When is $L$-Rank definable in inner models of $V=L$?

Suppose $M \in L$ is a countable model of $ZFC$, and furthermore suppose $M \vDash V \neq L$. These models have the funny property that, although every set in them is constructible, the model does not recognize this fact -- the "nonconstructible" sets simply arise at a level of the $L$-hierarchy that is greater than the ordinals of $M$. Provided any countable $ZFC$ model exists, then such models abound -- for example, we can easily build forcing extensions of countable models by building an $M$-generic filter directly, and the forcing extension will not recognize that the generic is constructible.

In the answer to the question linked above it is shown that such a model $M$ cannot define the $L$-order on all of its members, at least not with the usual definition -- it can only define $<_L$ for those elements that it recognizes as constructible (that is, for members of $L^M$). However, I am interested whether this limitation is inherent, or simply a limitation of definability over $M$. In particular, is it consistent for us to add the $L$-order on all of $M$, as a class, without destroying $ZFC$? I will phrase the question in terms of $GBC$ models, to make the use of classes explicit.

Is it consistent that $M \in L$ is a countable model of $GBC$ with $M \vDash V \neq L$, and there is class $U \in M$ such that $U$ gives the $L$-order on $M$? (That is, $\langle x,y \rangle \in U$ if and only if $x <_L y$, for all sets $x, y \in M$).

Note: In the context of $GBC$ the statement $V \neq L$ may be ambiguous -- I intend it to refer only to sets, and not to classes, e.g. $V \neq L$ means "there exists a nonconstructible set."

Such a $U$ would give us a proper class well order with order type larger than $ORD^M$, but this does not seem immediately problematic - many such well orders are definable over any model of $ZFC$. One way in which such a $U$ might be inconsistent is if, from $U$, we could show how to "construct" every set in $M$, but these constructions would be of more-than-$ORD^M$ length, and so this might not directly contradict $V \neq L$.

If such a $U$ is inconsistent, it would be nice to see why this limitation exists. On the other hand, if we can have such a $U$, is it universally possible?

If such a $U$ is consistent, are there any restrictions on the models $M$ that can have them?

For example, it might be consistent only if every member of $M$ has $L$-rank "not too much greater" than $ORD^M$.

EDIT: changed a stray occurence of "GBC" to "ZFC" in paragraph 1, for clarity.

Is every class that does not add sets necessarily added by forcing?

2013-01-09T20:38:51Z

We know there are many situations in which we can force over a model $M$ of GBC to add a class $G$ without adding any sets. That is, the extension $M[G]$ satisfies GBC and has the same sets as $M$. This technique is used, for example, in the proof that GBC is a conservative extension of ZFC, by forcing to add a universal choice function to a model of ZFC.

I'd like to know whether every class that can be 'safely' added to a model (preserving GBC and adding no sets) arises through forcing:

If $M$ is a model of GBC and $G$ is a class (that is, a subcollection of the sets of $M$, not a class member of $M$) such that $M[G]$ satisfies GBC and has the same sets as $M$, then is $G$ necessarily generic for some partial order $P \in M$?

I feel 'morally certain' that the answer must be no. Certainly the analogous question about sets, 'Can every set be added by forcing?' has a negative answer - we cannot, for example, force over $L$ to add a measure to a cardinal $\kappa$ (or to add $0^\#$, or any other set that might increase the consistency strength). However, I don't see how to adapt this kind of argument to classes, if we are not allowed to add sets. I'd love to see a counterexample (a proof of a positive answer would also be welcome!).

Which of these relations on partial orders allows us to identify forcing equivalence?

2012-11-25T17:08:24Z

Background

This question was inspired by Justin Palumbo's excellent question Cantor Bernstein for notions of forcing.

In his question, Justin considers a relation $\lhd$ on partial orders (defined below as $\lhd_1$) which begins to capture the notion of one partial order being "stronger" than another. He asks a natural question, namely whether this relation satisfies antisymmetry -- that is, if $\mathbb{Q}\lhd\mathbb{P}$ and $\mathbb{P}\lhd\mathbb{Q}$, does it follow that $\mathbb{P} \sim \mathbb{Q}$? Here, $\sim$ means forcing equivalent: two partial orders $\mathbb{P}$ and $\mathbb{Q}$ are forcing equivalent if they give rise to the same generic extensions, that is, every extension $V[G]$ by $\mathbb{P}$ can be realized as an extension $V[H]$ by $\mathbb{Q}$, and vice versa (in Joel Hamkins' terminology, we could say they are forcing equivalent if they give us access to the same neighborhood of the multiverse).

Unfortunately the given relation does not satisfy antisymmetry. In fact, the counterexamples given in the responses to the question demonstrate that $\lhd$ falls short of capturing the idea of one partial order being stronger than another. I'm trying to find the "right version" of $\lhd$ -- a relation on partial orders $\mathbb{Q} \lhd \mathbb{P}$ that captures our intuitive notion of '$\mathbb{P}$ is stronger than $\mathbb{Q}$'. A good test criteria is whether the relation satisfies antisymmetry. I will consider a number of (I hope) natural strengthenings of the $\lhd$ relation (or variations -- it's not clear that all of them are strengthenings).

Consider the following relations on partial orders:

$\mathbb{Q} \lhd_1 \mathbb{P}$: Every $\mathbb{P}$ extension contains a $\mathbb{Q}$ extension. $\mathbb{Q} \lhd_1 \mathbb{P}$ if and only if whenever $V[G]$ is a forcing extension by $\mathbb{P}$, there is an $H\in V[G]$ generic for $\mathbb{Q}$ with $V[H] \subseteq V[G]$. (this is the original definition from Justin's post).
$\mathbb{Q} \lhd_2 \mathbb{P}$: Every $\mathbb{P}$ extension contains a $\mathbb{Q}$ extension meeting an arbitrary condition. $\mathbb{Q} \lhd_2 \mathbb{P}$ if and only if whenever $V[G]$ is an extension by $\mathbb{P}$, and $q \in \mathbb{Q}$, there is $H$ in $V[G]$ generic for $\mathbb{Q}$ with $q \in H$.
$\mathbb{Q} \lhd_3 \mathbb{P}$: Every $\mathbb{Q}$ extension is contained in a $\mathbb{P}$ extension. $\mathbb{Q} \lhd_3 \mathbb{P}$ if and only if whenever $V[H]$ is an extension by $\mathbb{Q}$, there is an extension $V[G]$ by $\mathbb{P}$ such that $V[H] \subseteq V[G]$.
$\mathbb{Q} \lhd_4 \mathbb{P}$: $\mathbb{Q}$ embeds into $\mathbb{P}$. $\mathbb{Q} \lhd_4 \mathbb{P}$ if and only if there is a complete embedding of (the Boolean algebra of) $\mathbb{Q}$ into (the Boolean algebra of) $\mathbb{P}$.
$\mathbb{Q} \lhd_5 \mathbb{P}$: Every $\mathbb{Q}$ extension is equal to a $\mathbb{P}$ extension. $\mathbb{Q} \lhd_5 \mathbb{P}$ if and only if whenever $V[H]$ is an extension by $\mathbb{Q}$, there is an extension $V[G]$ by $\mathbb{P}$ such that $V[H] = V[G]$.

Please note that I have ignored serious metamathematical considerations in giving these definitions, but I believe each of them has a first-order definition.

Question. Which of the relations above satisfy antisymmetry? That is, for which of the relations above do we have $\mathbb{Q}\lhd\mathbb{P}$ and $\mathbb{P}\lhd\mathbb{Q}$ implies $\mathbb{P}$ is forcing equivalent to $\mathbb{Q}$?

From the responses to Justin's question it is clear that $\lhd_1$ does not satisfy antisymmetry. On the other hand, $\lhd_5$ does satisfy antisymmetry, but is extremely restrictive in terms of the partial orders that it can compare (for example, $Add(\omega,1)$ and $Add(\omega,1)\times Add(\omega_1,1)$ are incomparable by $\lhd_5$, although the latter is apparently more powerful than the former).

At the risk of violating the suggested guidelines for keeping questions focussed and specific, I'll include two followup questions -- feel free to ignore.

Question 2. What are the relative strengths of these relations (which ones imply which others)?

For example, we (trivially) have $\mathbb{Q} \lhd_5 \mathbb{P}$ implies $\mathbb{Q} \lhd_3 \mathbb{P}$, and $\mathbb{Q} \lhd_2 \mathbb{P}$ implies $\mathbb{Q} \lhd_1 \mathbb{P}$.

Question 3. What is the "right" notion of $\lhd$ for partial orders, that captures our intuitive idea of one partial order being "stronger" or "more effective" than another?

This is "too vague", but it's the question that motivated those above.

Answer by jonasreitz for Which of these relations on partial orders allows us to identify forcing equivalence?

2012-11-26T05:03:44Z

I believe I have an answer to my first question.

To recap, $\lhd_1$ is not antisymmetric (as demonstrated in the answers to Justin Palumbo's question).

As Francois G. Dorais points out in a comment, $\lhd_2$ is not reflexive (and therefore not antisymmetric).

It follows directly from the definition that $\lhd_5$ is antisymmetric (it was defined to accomplish exactly this).

This leaves $\lhd_3$ and $\lhd_4$. I will show that neither of these is antisymmetric -- the same counterexample works for both.

Let $\mathbb{R}_n$ be the product that adds a Cohen generic to each of the first $n$ cardinals. Now let $\mathbb{P}$ be the lottery sum of the posets $\{ \mathbb{R}_{2n} \mid n \in \omega \}$ . This partial order adds Cohen generics to the first $2n$ cardinals, where $n$ is chosen generically. Similarly, let $\mathbb{Q}$ be the lottery sum of $\{ \mathbb{R}_{2n+1} \mid n \in \omega \}$ , which adds Cohen generics to the first $2n+1$ cardinals. Observe that $\mathbb{P}$ and $\mathbb{Q}$ are not forcing equivalent, since they do not share any of the same generic extensions (extensions by $\mathbb{P}$ and $\mathbb{Q}$ always differ by a Cohen generic on at least one cardinal).

However, any generic extension $V[G]$ by $\mathbb{P}$ can be extended to a generic extension $V[H]$ by $\mathbb{Q}$ by simply adding a Cohen generic to the 'next' ($2n+1^{th}$) cardinal. This shows that $\mathbb{P} \lhd_3 \mathbb{Q}$. The same argument shows that $\mathbb{Q} \lhd_3 \mathbb{P}$. Thus $\lhd_3$ is not antisymmetric.

For $\lhd_4$, observe that each $\mathbb{R}_n$ embeds completely into $\mathbb{R}_{n+1}$, and we can thus construct a complete embedding of $\mathbb{P}$ into $\mathbb{Q}$ by working term-by-term with each member of the lottery sum. The same argument allows us to construct a complete embedding of $\mathbb{Q}$ into $\mathbb{P}$. Thus $\mathbb{P} \lhd_4 \mathbb{Q}$ and $\mathbb{Q} \lhd_4 \mathbb{P}$, and so $\lhd_4$ is not antisymmetric either.

Answer by jonasreitz for Cantor-Bernstein for notions of forcing

2012-11-24T03:08:23Z

I realize I'm a bit late to the party, but I wanted to add that counterexamples can be easily constructed out of almost any type of forcing. I'll give a particular example, but the method is flexible. All we need are three forcings, $\mathbb{R}_1$, $\mathbb{R}_2$ and $\mathbb{R}_3$, pairwise incomparable by the $\lhd$ relation described in the question. For concreteness, let's take $\mathbb{R}_1 = Add(\omega,1)$, $\mathbb{R}_2 = Add(\omega_1,1)$ and $\mathbb{R}_3 = Add(\omega_2,1)$.

Let $\mathbb{P}$ be the lottery sum of $\mathbb{R}_1$ and $\mathbb{R}_1 \times \mathbb{R}_2$ (so $\mathbb{P}$ first chooses generically whether to force with just $\mathbb{R}_1$ or with the product $\mathbb{R}_1 \times \mathbb{R}_2$, and then forces accordingly). Similarly, let $\mathbb{Q}$ be the lottery sum of $\mathbb{R}_1$ and $\mathbb{R}_1 \times \mathbb{R}_3$.

$\mathbb{P}$ and $\mathbb{Q}$ are clearly not forcing equivalent, since the first has the option of adding a generic for $\mathbb{R}_2$, which the second cannot (and vice versa, adding a generic to $\mathbb{R}_3$). However, forcing with one will always add a generic for the other, since either one will add a generic for $\mathbb{R}_1$, which is one option in the lottery in each case.

This does not answer the second question, about Boolean algebras, and I think it demonstrates that the order relation on Boolean algebras given by "embedding into a subalgebra" is really distinct from the $\lhd$ order -- here we have two forcings satisfying $\mathbb{P} \lhd \mathbb{Q}$ and $\mathbb{Q} \lhd \mathbb{P}$, but neither Boolean algebra embeds into a subalgebra of the other.

This suggests a natural additional condition, namely that $H$ give the entire extension $V[G]$. That is, in every extension $V[G]$ by $\mathbb{P}$ there is $H$ generic for $\mathbb{Q}$ such that $V[G]=V[H]$. I believe this guarantees forcing equivalence in the case where $\mathbb{P} \lhd \mathbb{Q}$ and $\mathbb{Q} \lhd \mathbb{P}$, since every extension by $\mathbb{P}$ equals and extension by $\mathbb{Q}$ and vice versa.

What can we learn about an elementary embedding from the image of the ordinals?

2012-02-26T01:51:19Z

If $j : V \rightarrow M$ is an elementary embedding, what can we learn in $M$ from $j''ORD$? That is, what is $M[j''ORD]$?

In particular,

Is it $M[j''ORD]$ equal to all of $V$?

If not, do we get a model intermediate between $M$ and $V$? If $\kappa$ is the critical point of $j$, is $\kappa$ still a large cardinal in $M[j''ORD]$? I am thinking of $j$ arising from a measure on $\kappa$, but I'm also interested in the more general situation.

My thinking goes like this: If we have the image of all of $V$, we can reconstruct $V$ itself by taking the Mostowski collapse of $j''V$ (and $j$ is the inverse of the Mostowski collapse). In $M[j''ORD]$, let's consider the class $W$ of sets with rank in $j''ORD$. Does the Mostowski collapse of $W$ yield all of $V$, and if not, what's missing?

EDIT: formatting, clarification of question.

Answer by jonasreitz for When can we detect forcing?

2010-11-08T17:30:25Z

Amit Gupta's comment gives the answer to your first question, which I will expand on slightly:

Every poset is detectable, and even more, the class of all posets is uniformly detectable. That is, there is a single formula $\phi(x)$ that takes as input a poset $P$, such that $\phi(P)$ is true in a model $M$ exactly when $M$ is a forcing extension of an inner model $N$ by $P$ (let us call $N$ a ground model of $M$ by $P$). It follows that the same is true for any set of posets (or definable class $C$ of posets) in $M$: we can detect when $M$ is a $C$-forcing extension.

Regarding your second question ("consistent classes"), there are many examples of consistent classes. For example, let $C$ be the class of posets that add a subset to a regular cardinal using the poset as defined in $L$ (that is, $C$ is the class of posets of the form $ Add(\kappa,1)^L $ ). If we start in $V$ and force with the (class) product of $C$, then in the resulting model $V[G]$, for every member $P$ of $C$ there is a ground model of $V[G]$ by $P$. This is because, for a fixed $\kappa$, we can use the commutativity of the product to rewrite the extension as class forcing (adding a subset to each cardinal except $\kappa$), followed by set forcing adding a subset to $\kappa$. This allows us to rewrite $V[G]=V[G^\prime][g]$, and $V[G]$ is an extension of $V[G^\prime]$ by $Add(\kappa,1)^L$ as required.

We can modify this argument in various ways to handle other classes. It will work for any class of posets from $L$ whose product preserves $ZFC$. We can also take our posets from another absolute inner model, such as $L[mu]$, instead of from $L$. Dropping the requirement that the posets be from a designated inner model (for example, taking $C$ to be the class of posets $Add(\kappa,1)$) may still possible but would require a more delicate argument. The issue here is that the definition of the poset $Add(\kappa,1)$ is not absolute, and so the poset defined in $V$ may not exist in every ground model. Nonetheless I suspect that the same model defined in the previous example will work.

There are also some classes that are clearly not consistent, for example the the class $C$ of partial orders that collapse $\kappa$ to $\omega$ (for every $\kappa$). Any model containing generics for all such posets will fail to satisfy $ZFC$, as every cardinal will be collapsed.

For the more general case, one avenue of attack might be to use the Maximality Principle (introduced by Joel Hamkins). This principle says that any statement that can be forced in such a way that further forcing cannot make it false, is already true, and existence of a ground model for a particular poset is just such a statement.

Comment by jonasreitz

2013-02-16T21:42:08Z

...I guess this just shows that $V[g][X]$ and $V[X]$ have the same reals - I'm not sure it follows that $g \in V[X]$.

Comment by jonasreitz

2013-02-16T21:38:10Z

Joel, doesn't your argument work even when $\alpha$ is uncountable? That is, every real in $V[g]$ will appear as a block in $X$, regardless of the size of $\mathbb{R}$.

Comment by jonasreitz

2013-02-02T23:35:43Z

from $W[B][C]$ up to the full model $W[B][A]$, so this does not provide an $\text{Add}(\delta,1)$ ground in the way you require. I have been playing with variations of this idea to see if I can get an example.

Comment by jonasreitz

2013-02-02T23:35:33Z

Joel, Yes, I see. This is a very interesting question -- I thought the answer was 'clearly' yes, but now I'm not so certain. One more thought, which may not prove useful: The set $A$ is not $W[B]$ generic for $\text{Add}(\delta,1)^{W[B]}$, as you correctly point out, but it is $W[B]$ generic for $\text{Add}(\delta,1)^W$. This forcing will add a generic for $\text{Add}(\delta,1)^{W[B]}$, so there is a $C \in W[B][A] \setminus W[B]$ such $W[B][C]$ is an $\text{Add}(\delta,1)^{W[B]}$ extension of $W[B]$. Unfortunately, we need to do a little further forcing (quotient forcing) to get

Comment by jonasreitz

2013-02-02T03:55:54Z

Joel, an observation: if $M=W[A]$ is already an $Add(\delta,1)$ extension for some $\delta>\kappa$, then forcing to add a subset to $\kappa$ is equivalent to forcing over $W$ with the product, and so the answer to your question is 'yes'. If we specifically disallow $M$ of this form, then we have $M[G]=N[A]$ for which there is no $W$ with $W[A][G]=M[G]=N[A]$, which is looking an awfully lot like a counterexample to directedness of grounds (I may be ignoring some subtleties here, however.)

Comment by jonasreitz

2013-02-02T03:52:34Z

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.

Comment by jonasreitz

2013-02-02T03:52:26Z

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

Comment by jonasreitz

2013-01-29T16:48:40Z

@Joel, yes, I had intended $M$ to be transitive. However, I know if we allow non-transitive models we get some very interesting and strange results, as in your "Multiverse Perspective on the Axiom of Constructibility" -- so I guess I'm also interested in the nontransitive case...

Comment by jonasreitz

2013-01-29T16:40:10Z

Douglas, just wanted to say I love your question. In contemplating these odd models in which every element is constructible, but $V \neq L$, I am always struck by the possibility that every set is, in fact, constructible, if we are willing to continue the $L$-construction far enough beyond $ORD$. This idea is addressed more rigorously by Joel Hamkins in his [A Multiverse Perspective on the Axiom of Constructibility](jdh.hamkins.org/the-set-theoretic-multiverse)

Comment by jonasreitz

2013-01-29T16:13:10Z

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

Comment by jonasreitz

2013-01-10T16:23:42Z

What a great example, Joel! The fact that the satisfaction class is compatible with GBC but is not definable is a very nice combination. Does existence of a satisfaction class increase the consistency strength of GBC?

Comment by jonasreitz

2013-01-10T03:54:31Z

$G \cap V_\alpha^M$, we could instead take $P$ to be all subsets of $V_\alpha^M$, for all $\alpha$, ordered by set-inclusion. But, while $G$ would give a filter for this partial order (as would any collection of sets of $M$), there does not seem to be a good reason to think $it would be generic.

Comment by jonasreitz

2013-01-10T03:51:59Z

Hi Ali, thanks for the response! I see that your example works, provided $G \in C$ -- in this case $P$ is linearly ordered, and therefore trivial forcing, and the resulting generic $G$ is necessarily in the ground model. I am mainly interested in the case where $G$ is not a member of $C$, so we really are 'adding something' by adjoining $G$ to the model. I like the idea of modifying your example to work in this case, but it's not clear how to define the partial order $P$ (since we do not have access to $G$ to carry out the definition). Rather than taking

Comment by jonasreitz

2012-11-26T03:52:48Z

for the $\mathbb{P}$ and $\mathbb{Q}$ described in my answer to your question [here](mathoverflow.net/questions/79298/…). Thanks for the reference -- it seems to be exactly on-topic. -Jonas

Comment by jonasreitz

2012-11-26T03:48:28Z

Justin, thanks for your comments. Yes, I see that $\lhd_4$ implies $\lhd_1$ -- great! For the reverse implication, I'm worried that the map sending $q$ to $[q\in \tau]$ may not preserve incompatibility (and thus may not give a complete embedding). For example, if $\mathbb{Q}$ is the lottery sum of two posets, and $\tau$ always yields a generic for the first of them (with no mention of the second), then it will map all members of the second poset to Boolean value 0. This is the case