Forcing (mathematics)

For the use of forcing in recursion theory, see Forcing (computability).

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. Intuitively, forcing can be thought of as a technique to expand the set theoretical universe ${\displaystyle V}$ to a larger universe ${\displaystyle V[G]}$ by introducing a new "generic" object ${\displaystyle G}$.

Forcing was first used by Paul Cohen in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory. It has been considerably reworked and simplified in the following years, and has since served as a powerful technique, both in set theory and in areas of mathematical logic such as recursion theory. Descriptive set theory uses the notions of forcing from both recursion theory and set theory. Forcing has also been used in model theory, but it is common in model theory to define genericity directly without mention of forcing.

Intuition

Forcing is usually used to construct an expanded universe that satisfies some desired property. For example, the expanded universe might contain many new real numbers (at least ${\displaystyle \aleph _{2}}$  of them), identified with subsets of the set ${\displaystyle \mathbb {N} }$  of natural numbers, that were not there in the old universe, and thereby violate the continuum hypothesis.

In order to intuitively justify such an expansion, it is best to think of the "old universe" as a model ${\displaystyle M}$  of the set theory, which is itself a set in the "real universe" ${\displaystyle V}$ . By the Löwenheim–Skolem theorem, ${\displaystyle M}$  can be chosen to be a "bare bones" model that is externally countable, which guarantees that there will be many subsets (in ${\displaystyle V}$ ) of ${\displaystyle \mathbb {N} }$  that are not in ${\displaystyle M}$ . Specifically, there is an ordinal ${\displaystyle \aleph _{2}^{M}}$  that "plays the role of the cardinal ${\displaystyle \aleph _{2}}$ " in ${\displaystyle M}$ , but is actually countable in ${\displaystyle V}$ . Working in ${\displaystyle V}$ , it should be easy to find one distinct subset of ${\displaystyle \mathbb {N} }$  per each element of ${\displaystyle \aleph _{2}^{M}}$ . (For simplicity, this family of subsets can be characterized with a single subset ${\displaystyle X\subseteq \aleph _{2}^{M}\times \mathbb {N} }$ .)

However, in some sense, it may be desirable to "construct the expanded model ${\displaystyle M[X]}$  within ${\displaystyle M}$ ". This would help ensure that ${\displaystyle M[X]}$  "resembles" ${\displaystyle M}$  in certain aspects, such as ${\displaystyle \aleph _{2}^{M[X]}}$  being the same as ${\displaystyle \aleph _{2}^{M}}$  (more generally, that cardinal collapse does not occur), and allow fine control over the properties of ${\displaystyle M[X]}$ . More precisely, every member of ${\displaystyle M[X]}$  should be given a (non-unique) name in ${\displaystyle M}$ . The name can be thought as an expression in terms of ${\displaystyle X}$ , just like in a simple field extension ${\displaystyle L=K(\theta )}$  every element of ${\displaystyle L}$  can be expressed in terms of ${\displaystyle \theta }$ . A major component of forcing is manipulating those names within ${\displaystyle M}$ , so sometimes it may help to directly think of ${\displaystyle M}$  as "the universe", knowing that the theory of forcing guarantees that ${\displaystyle M[X]}$  will correspond to an actual model.

A subtle point of forcing is that, if ${\displaystyle X}$  is taken to be an arbitrary "missing subset" of some set in ${\displaystyle M}$ , then the ${\displaystyle M[X]}$  constructed "within ${\displaystyle M}$ " may not even be a model. This is because ${\displaystyle X}$  may encode "special" information about ${\displaystyle M}$  that is invisible within ${\displaystyle M}$  (e.g. the countability of ${\displaystyle M}$ ), and thus prove the existence of sets that are "too complex for ${\displaystyle M}$  to describe".^[1][2]

Forcing avoids such problems by requiring the newly introduced set ${\displaystyle X}$  to be a generic set relative to ${\displaystyle M}$ .^[1] Some statements are "forced" to hold for any generic ${\displaystyle X}$ : For example, a generic ${\displaystyle X}$  is "forced" to be infinite. Furthermore, any property (describable in ${\displaystyle M}$ ) of a generic set is "forced" to hold under some forcing condition. The concept of "forcing" can be defined within ${\displaystyle M}$ , and it gives ${\displaystyle M}$  enough reasoning power to prove that ${\displaystyle M[X]}$  is indeed a model that satisfies the desired properties.

Cohen's original technique, now called ramified forcing, is slightly different from the unramified forcing expounded here. Forcing is also equivalent to the method of Boolean-valued models, which some feel is conceptually more natural and intuitive, but usually much more difficult to apply.^[3]

The role of the model

In order for the above approach to work smoothly, ${\displaystyle M}$  must in fact be a standard transitive model in ${\displaystyle V}$ , so that membership and other elementary notions can be handled intuitively in both ${\displaystyle M}$  and ${\displaystyle V}$ . A standard transitive model can be obtained from any standard model through the Mostowski collapse lemma, but the existence of any standard model of ${\displaystyle {\mathsf {ZFC}}}$  (or any variant thereof) is in itself a stronger assumption than the consistency of ${\displaystyle {\mathsf {ZFC}}}$ .

To get around this issue, a standard technique is to let ${\displaystyle M}$  be a standard transitive model of an arbitrary finite subset of ${\displaystyle {\mathsf {ZFC}}}$  (any axiomatization of ${\displaystyle {\mathsf {ZFC}}}$  has at least one axiom schema, and thus an infinite number of axioms), the existence of which is guaranteed by the reflection principle. As the goal of a forcing argument is to prove consistency results, this is enough since any inconsistency in a theory must manifest with a derivation of a finite length, and thus involve only a finite number of axioms.

Forcing conditions and forcing posets

Each forcing condition can be regarded as a finite piece of information regarding the object ${\displaystyle X}$  adjoined to the model. There are many different ways of providing information about an object, which give rise to different forcing notions. A general approach to formalizing forcing notions is to regard forcing conditions as abstract objects with a poset structure.

A forcing poset is an ordered triple, ${\displaystyle (\mathbb {P} ,\leq ,\mathbf {1} )}$ , where ${\displaystyle \leq }$  is a preorder on ${\displaystyle \mathbb {P} }$ , and ${\displaystyle \mathbf {1} }$  is the largest element. Members of ${\displaystyle \mathbb {P} }$  are the forcing conditions (or just conditions). The order relation ${\displaystyle p\leq q}$  means "${\displaystyle p}$  is stronger than ${\displaystyle q}$ ". (Intuitively, the "smaller" condition provides "more" information, just as the smaller interval ${\displaystyle [3.1415926,3.1415927]}$  provides more information about the number π than the interval ${\displaystyle [3.1,3.2]}$  does.) Furthermore, the preorder ${\displaystyle \leq }$  must be atomless, meaning that it must satisfy the splitting condition:

• For each ${\displaystyle p\in \mathbb {P} }$ , there are ${\displaystyle q,r\in \mathbb {P} }$  such that ${\displaystyle q,r\leq p}$ , with no ${\displaystyle s\in \mathbb {P} }$  such that ${\displaystyle s\leq q,r}$ .

In other words, it must be possible to strengthen any forcing condition ${\displaystyle p}$  in at least two incompatible directions. Intuitively, this is because ${\displaystyle p}$  is only a finite piece of information, whereas an infinite piece of information is needed to determine ${\displaystyle X}$ .

There are various conventions in use. Some authors require ${\displaystyle \leq }$  to also be antisymmetric, so that the relation is a partial order. Some use the term partial order anyway, conflicting with standard terminology, while some use the term preorder. The largest element can be dispensed with. The reverse ordering is also used, most notably by Saharon Shelah and his co-authors.

Examples

Let ${\displaystyle S}$  be any infinite set (such as ${\displaystyle \mathbb {N} }$ ), and let the generic object in question be a new subset ${\displaystyle X\subseteq S}$ . In Cohen's original formulation of forcing, each forcing condition is a finite set of sentences, either of the form ${\displaystyle a\in X}$  or ${\displaystyle a\notin X}$ , that are self-consistent (i.e. ${\displaystyle a\in X}$  and ${\displaystyle a\notin X}$  for the same value of ${\displaystyle a}$  do not appear in the same condition). This forcing notion is usually called Cohen forcing.

The forcing poset for Cohen forcing can be formally written as ${\displaystyle (\operatorname {Fin} (S,2),\supseteq ,0)}$ , the finite partial functions from ${\displaystyle S}$  to ${\displaystyle 2~{\stackrel {\text{df}}{=}}~\{0,1\}}$  under reverse inclusion. Cohen forcing satisfies the splitting condition because given any condition ${\displaystyle p}$ , one can always find an element ${\displaystyle a\in S}$  not mentioned in ${\displaystyle p}$ , and add either the sentence ${\displaystyle a\in X}$  or ${\displaystyle a\notin X}$  to ${\displaystyle p}$  to get two new forcing conditions, incompatible with each other.

Another instructive example of a forcing poset is ${\displaystyle (\operatorname {Bor} (I),\subseteq ,I)}$ , where ${\displaystyle I=[0,1]}$  and ${\displaystyle \operatorname {Bor} (I)}$  is the collection of Borel subsets of ${\displaystyle I}$  having non-zero Lebesgue measure. The generic object associated with this forcing poset is a random real number ${\displaystyle r\in [0,1]}$ . It can be shown that ${\displaystyle r}$  falls in every Borel subset of ${\displaystyle [0,1]}$  with measure 1, provided that the Borel subset is "described" in the original unexpanded universe (this can be formalized with the concept of Borel codes). Each forcing condition can be regarded as a random event with probability equal to its measure. Due to the ready intuition this example can provide, probabilistic language is sometimes used with other divergent forcing posets.

Generic filters

Even though each individual forcing condition ${\displaystyle p}$  cannot fully determine the generic object ${\displaystyle X}$ , the set ${\displaystyle G\subseteq \mathbb {P} }$  of all true forcing conditions does determine ${\displaystyle X}$ . In fact, without loss of generality, ${\displaystyle G}$  is commonly considered to be the generic object adjoined to ${\displaystyle M}$ , so the expanded model is called ${\displaystyle M[G]}$ . It is usually easy enough to show that the originally desired object ${\displaystyle X}$  is indeed in the model ${\displaystyle M[G]}$ .

Under this convention, the concept of "generic object" can be described in a general way. Specifically, the set ${\displaystyle G}$  should be a generic filter on ${\displaystyle \mathbb {P} }$  relative to ${\displaystyle M}$ . The "filter" condition means that it makes sense that ${\displaystyle G}$  is a set of all true forcing conditions:

• ${\displaystyle G\subseteq \mathbb {P} ;}$ 
• ${\displaystyle \mathbf {1} \in G;}$ 
• if ${\displaystyle p\geq q\in G}$ , then ${\displaystyle p\in G;}$ 
• if ${\displaystyle p,q\in G}$ , then there exists an ${\displaystyle r\in G}$  such that ${\displaystyle r\leq p,q.}$ 

For ${\displaystyle G}$  to be "generic relative to ${\displaystyle M}$ " means:

• If ${\displaystyle D\in M}$  is a "dense" subset of ${\displaystyle \mathbb {P} }$  (that is, for each ${\displaystyle p\in \mathbb {P} }$ , there exists a ${\displaystyle q\in D}$  such that ${\displaystyle q\leq p}$ ), then ${\displaystyle G\cap D\neq \varnothing }$ .

Given that ${\displaystyle M}$  is a countable model, the existence of a generic filter ${\displaystyle G}$  follows from the Rasiowa–Sikorski lemma. In fact, slightly more is true: Given a condition ${\displaystyle p\in \mathbb {P} }$ , one can find a generic filter ${\displaystyle G}$  such that ${\displaystyle p\in G}$ . Due to the splitting condition on ${\displaystyle \mathbb {P} }$ , if ${\displaystyle G}$  is a filter, then ${\displaystyle \mathbb {P} \setminus G}$  is dense. If ${\displaystyle G\in M}$ , then ${\displaystyle \mathbb {P} \setminus G\in M}$  because ${\displaystyle M}$  is a model of ${\displaystyle {\mathsf {ZFC}}}$ . For this reason, a generic filter is never in ${\displaystyle M}$ .

P-names and interpretations

Associated with a forcing poset ${\displaystyle \mathbb {P} }$  is the class ${\displaystyle V^{(\mathbb {P} )}}$  of ${\displaystyle \mathbb {P} }$ -names. A ${\displaystyle \mathbb {P} }$ -name is a set ${\displaystyle A}$  of the form

${\displaystyle A\subseteq \{(u,p)\mid u~{\text{is a}}~\mathbb {P} {\text{-name and}}~p\in \mathbb {P} \}.}$ 

Given any filter ${\displaystyle G}$  on ${\displaystyle \mathbb {P} }$ , the interpretation or valuation map from ${\displaystyle \mathbb {P} }$ -names is given by

${\displaystyle \operatorname {val} (u,G)=\{\operatorname {val} (v,G)\mid \exists p\in G:~(v,p)\in u\}.}$ 

The ${\displaystyle \mathbb {P} }$ -names are, in fact, an expansion of the universe. Given ${\displaystyle x\in V}$ , one defines ${\displaystyle {\check {x}}}$  to be the ${\displaystyle \mathbb {P} }$ -name

${\displaystyle {\check {x}}=\{({\check {y}},\mathbf {1} )\mid y\in x\}.}$ 

Since ${\displaystyle \mathbf {1} \in G}$ , it follows that ${\displaystyle \operatorname {val} ({\check {x}},G)=x}$ . In a sense, ${\displaystyle {\check {x}}}$  is a "name for ${\displaystyle x}$ " that does not depend on the specific choice of ${\displaystyle G}$ .

This also allows defining a "name for ${\displaystyle G}$ " without explicitly referring to ${\displaystyle G}$ :

${\displaystyle {\underline {G}}=\{({\check {p}},p)\mid p\in \mathbb {P} \}}$ 

so that ${\displaystyle \operatorname {val} ({\underline {G}},G)=\{\operatorname {val} ({\check {p}},G)\mid p\in G\}=G}$ .

Rigorous definitions

The concepts of ${\displaystyle \mathbb {P} }$ -names, interpretations, and ${\displaystyle {\check {x}}}$  are actually defined by transfinite recursion. With ${\displaystyle \varnothing }$  the empty set, ${\displaystyle \alpha +1}$  the successor ordinal to ordinal ${\displaystyle \alpha }$ , ${\displaystyle {\mathcal {P}}}$  the power-set operator, and ${\displaystyle \lambda }$  a limit ordinal, define the following hierarchy:

${\displaystyle {\begin{aligned}\operatorname {Name} (\varnothing )&=\varnothing ,\\\operatorname {Name} (\alpha +1)&={\mathcal {P}}(\operatorname {Name} (\alpha )\times \mathbb {P} ),\\\operatorname {Name} (\lambda )&=\bigcup \{\operatorname {Name} (\alpha )\mid \alpha <\lambda \}.\end{aligned}}}$ 

Then the class of ${\displaystyle \mathbb {P} }$ -names is defined as

${\displaystyle V^{(\mathbb {P} )}=\bigcup \{\operatorname {Name} (\alpha )~|~\alpha ~{\text{is an ordinal}}\}.}$ 

The interpretation map and the map ${\displaystyle x\mapsto {\check {x}}}$  can similarly be defined with a hierarchical construction.

Forcing

Given a generic filter ${\displaystyle G\subseteq \mathbb {P} }$ , one proceeds as follows. The subclass of ${\displaystyle \mathbb {P} }$ -names in ${\displaystyle M}$  is denoted ${\displaystyle M^{(\mathbb {P} )}}$ . Let

${\displaystyle M[G]=\left\{\operatorname {val} (u,G)~{\Big |}~u\in M^{(\mathbb {P} )}\right\}.}$ 

To reduce the study of the set theory of ${\displaystyle M[G]}$  to that of ${\displaystyle M}$ , one works with the "forcing language", which is built up like ordinary first-order logic, with membership as the binary relation and all the ${\displaystyle \mathbb {P} }$ -names as constants.

Define ${\displaystyle p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})}$  (to be read as "${\displaystyle p}$  forces ${\displaystyle \varphi }$  in the model ${\displaystyle M}$  with poset ${\displaystyle \mathbb {P} }$ "), where ${\displaystyle p}$  is a condition, ${\displaystyle \varphi }$  is a formula in the forcing language, and the ${\displaystyle u_{i}}$ 's are ${\displaystyle \mathbb {P} }$ -names, to mean that if ${\displaystyle G}$  is a generic filter containing ${\displaystyle p}$ , then ${\displaystyle M[G]\models \varphi (\operatorname {val} (u_{1},G),\ldots ,\operatorname {val} (u_{n},G))}$ . The special case ${\displaystyle \mathbf {1} \Vdash _{M,\mathbb {P} }\varphi }$  is often written as "${\displaystyle \mathbb {P} \Vdash _{M,\mathbb {P} }\varphi }$ " or simply "${\displaystyle \Vdash _{M,\mathbb {P} }\varphi }$ ". Such statements are true in ${\displaystyle M[G]}$ , no matter what ${\displaystyle G}$  is.

What is important is that this external definition of the forcing relation ${\displaystyle p\Vdash _{M,\mathbb {P} }\varphi }$  is equivalent to an internal definition within ${\displaystyle M}$ , defined by transfinite induction (specifically ${\displaystyle \in }$ -induction) over the ${\displaystyle \mathbb {P} }$ -names on instances of ${\displaystyle u\in v}$  and ${\displaystyle u=v}$ , and then by ordinary induction over the complexity of formulae. This has the effect that all the properties of ${\displaystyle M[G]}$  are really properties of ${\displaystyle M}$ , and the verification of ${\displaystyle {\mathsf {ZFC}}}$  in ${\displaystyle M[G]}$  becomes straightforward. This is usually summarized as the following three key properties:

• Truth: ${\displaystyle M[G]\models \varphi (\operatorname {val} (u_{1},G),\ldots ,\operatorname {val} (u_{n},G))}$  if and only if it is forced by ${\displaystyle G}$ , that is, for some condition ${\displaystyle p\in G}$ , we have ${\displaystyle p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})}$ .
• Definability: The statement "${\displaystyle p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})}$ " is definable in ${\displaystyle M}$ .
• Coherence: ${\displaystyle p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})\land q\leq p\implies q\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})}$ .

Internal definition

There are many different but equivalent ways to define the forcing relation ${\displaystyle \Vdash _{M,\mathbb {P} }}$  in ${\displaystyle M}$ .^[4] One way to simplify the definition is to first define a modified forcing relation ${\displaystyle \Vdash _{M,\mathbb {P} }^{*}}$  that is strictly stronger than ${\displaystyle \Vdash _{M,\mathbb {P} }}$ . The modified relation ${\displaystyle \Vdash _{M,\mathbb {P} }^{*}}$  still satisfies the three key properties of forcing, but ${\displaystyle p\Vdash _{M,\mathbb {P} }^{*}\varphi }$  and ${\displaystyle p\Vdash _{M,\mathbb {P} }^{*}\varphi '}$  are not necessarily equivalent even if the first-order formulae ${\displaystyle \varphi }$  and ${\displaystyle \varphi '}$  are equivalent. The unmodified forcing relation can then be defined as

$${\displaystyle p\Vdash _{M,\mathbb {P} }\varphi \iff p\Vdash _{M,\mathbb {P} }^{*}\neg \neg \varphi .}$$

 

In fact, Cohen's original concept of forcing is essentially ${\displaystyle \Vdash _{M,\mathbb {P} }^{*}}$  rather than ${\displaystyle \Vdash _{M,\mathbb {P} }}$ .^[3]

The modified forcing relation ${\displaystyle \Vdash _{M,\mathbb {P} }^{*}}$  can be defined recursively as follows:

1. ${\displaystyle p\Vdash _{M,\mathbb {P} }^{*}u\in v}$  means ${\displaystyle (\exists (w,q)\in v)(q\geq p\wedge p\Vdash _{M,\mathbb {P} }^{*}w=u).}$ 
2. ${\displaystyle p\Vdash _{M,\mathbb {P} }^{*}u\neq v}$  means ${\displaystyle (\exists (w,q)\in v)(q\geq p\wedge p\Vdash _{M,\mathbb {P} }^{*}w\notin u)\vee (\exists (w,q)\in u)(q\geq p\wedge p\Vdash _{M,\mathbb {P} }^{*}w\notin v).}$ 
3. ${\displaystyle p\Vdash _{M,\mathbb {P} }^{*}\neg \varphi }$  means ${\displaystyle \neg (\exists q\leq p)(q\Vdash _{M,\mathbb {P} }^{*}\varphi ).}$ 
4. ${\displaystyle p\Vdash _{M,\mathbb {P} }^{*}(\varphi \vee \psi )}$  means ${\displaystyle (p\Vdash _{M,\mathbb {P} }^{*}\varphi )\vee (p\Vdash _{M,\mathbb {P} }^{*}\psi ).}$ 
5. ${\displaystyle p\Vdash _{M,\mathbb {P} }^{*}\exists x\,\varphi (x)}$  means ${\displaystyle (\exists u\in M^{(\mathbb {P} )})(p\Vdash _{M,\mathbb {P} }^{*}\varphi (u)).}$ 

Other symbols of the forcing language can be defined in terms of these symbols: For example, ${\displaystyle u=v}$  means ${\displaystyle \neg (u\neq v)}$ , ${\displaystyle \forall x\,\varphi (x)}$  means ${\displaystyle \neg \exists x\,\neg \varphi (x)}$ , etc. Cases 1 and 2 depend on each other and on case 3, but the recursion always refer to ${\displaystyle \mathbb {P} }$ -names with lesser ranks, so transfinite induction allows the definition to go through.

By construction, ${\displaystyle \Vdash _{M,\mathbb {P} }^{*}}$  (and thus ${\displaystyle \Vdash _{M,\mathbb {P} }}$ ) automatically satisfies Definability. The proof that ${\displaystyle \Vdash _{M,\mathbb {P} }^{*}}$  also satisfies Truth and Coherence is by inductively inspecting each of the five cases above. Cases 4 and 5 are trivial (thanks to the choice of ${\displaystyle \vee }$  and ${\displaystyle \exists }$  as the elementary symbols^[5]), cases 1 and 2 relies only on the assumption that ${\displaystyle G}$  is a filter, and only case 3 requires ${\displaystyle G}$  to be a generic filter.^[3]

Formally, an internal definition of the forcing relation (such as the one presented above) is actually a transformation of an arbitrary formula ${\displaystyle \varphi (x_{1},\dots ,x_{n})}$  to another formula ${\displaystyle p\Vdash _{\mathbb {P} }\varphi (u_{1},\dots ,u_{n})}$  where ${\displaystyle p}$  and ${\displaystyle \mathbb {P} }$  are additional variables. The model ${\displaystyle M}$  does not explicitly appear in the transformation (note that within ${\displaystyle M}$ , ${\displaystyle u\in M^{(\mathbb {P} )}}$  just means "${\displaystyle u}$  is a ${\displaystyle \mathbb {P} }$ -name"), and indeed one may take this transformation as a "syntactic" definition of the forcing relation in the universe ${\displaystyle V}$  of all sets regardless of any countable transitive model. However, if one wants to force over some countable transitive model ${\displaystyle M}$ , then the latter formula should be interpreted under ${\displaystyle M}$  (i.e. with all quantifiers ranging only over ${\displaystyle M}$ ), in which case it is equivalent to the external "semantic" definition of ${\displaystyle \Vdash _{M,\mathbb {P} }}$  described at the top of this section:

For any formula ${\displaystyle \varphi (x_{1},\dots ,x_{n})}$  there is a theorem ${\displaystyle T}$  of the theory ${\displaystyle {\mathsf {ZFC}}}$  (for example conjunction of finite number of axioms) such that for any countable transitive model ${\displaystyle M}$  such that ${\displaystyle M\models T}$  and any atomless partial order ${\displaystyle \mathbb {P} \in M}$  and any ${\displaystyle \mathbb {P} }$ -generic filter ${\displaystyle G}$  over ${\displaystyle M}$ 

$${\displaystyle (\forall a_{1},\ldots ,a_{n}\in M^{\mathbb {P} })(\forall p\in \mathbb {P} )(p\Vdash _{M,\mathbb {P} }\varphi (a_{1},\dots ,a_{n})\,\Leftrightarrow \,M\models p\Vdash _{\mathbb {P} }\varphi (a_{1},\dots ,a_{n})).}$$

 

This the sense under which the forcing relation is indeed "definable in ${\displaystyle M}$ ".

Consistency

The discussion above can be summarized by the fundamental consistency result that, given a forcing poset ${\displaystyle \mathbb {P} }$ , we may assume the existence of a generic filter ${\displaystyle G}$ , not belonging to the universe ${\displaystyle V}$ , such that ${\displaystyle V[G]}$  is again a set-theoretic universe that models ${\displaystyle {\mathsf {ZFC}}}$ . Furthermore, all truths in ${\displaystyle V[G]}$  may be reduced to truths in ${\displaystyle V}$  involving the forcing relation.

Both styles, adjoining ${\displaystyle G}$  to either a countable transitive model ${\displaystyle M}$  or the whole universe ${\displaystyle V}$ , are commonly used. Less commonly seen is the approach using the "internal" definition of forcing, in which no mention of set or class models is made. This was Cohen's original method, and in one elaboration, it becomes the method of Boolean-valued analysis.

Cohen forcing

The simplest nontrivial forcing poset is ${\displaystyle (\operatorname {Fin} (\omega ,2),\supseteq ,0)}$ , the finite partial functions from ${\displaystyle \omega }$  to ${\displaystyle 2~{\stackrel {\text{df}}{=}}~\{0,1\}}$  under reverse inclusion. That is, a condition ${\displaystyle p}$  is essentially two disjoint finite subsets ${\displaystyle {p^{-1}}[1]}$  and ${\displaystyle {p^{-1}}[0]}$  of ${\displaystyle \omega }$ , to be thought of as the "yes" and "no" parts of ${\displaystyle p}$ , with no information provided on values outside the domain of ${\displaystyle p}$ . "${\displaystyle q}$  is stronger than ${\displaystyle p}$ " means that ${\displaystyle q\supseteq p}$ , in other words, the "yes" and "no" parts of ${\displaystyle q}$  are supersets of the "yes" and "no" parts of ${\displaystyle p}$ , and in that sense, provide more information.

Let ${\displaystyle G}$  be a generic filter for this poset. If ${\displaystyle p}$  and ${\displaystyle q}$  are both in ${\displaystyle G}$ , then ${\displaystyle p\cup q}$  is a condition because ${\displaystyle G}$  is a filter. This means that ${\displaystyle g=\bigcup G}$  is a well-defined partial function from ${\displaystyle \omega }$  to ${\displaystyle 2}$  because any two conditions in ${\displaystyle G}$  agree on their common domain.

In fact, ${\displaystyle g}$  is a total function. Given ${\displaystyle n\in \omega }$ , let ${\displaystyle D_{n}=\{p\mid p(n)~{\text{is defined}}\}}$ . Then ${\displaystyle D_{n}}$  is dense. (Given any ${\displaystyle p}$ , if ${\displaystyle n}$  is not in ${\displaystyle p}$ 's domain, adjoin a value for ${\displaystyle n}$ —the result is in ${\displaystyle D_{n}}$ .) A condition ${\displaystyle p\in G\cap D_{n}}$  has ${\displaystyle n}$  in its domain, and since ${\displaystyle p\subseteq g}$ , we find that ${\displaystyle g(n)}$  is defined.

Let ${\displaystyle X={g^{-1}}[1]}$ , the set of all "yes" members of the generic conditions. It is possible to give a name for ${\displaystyle X}$  directly. Let

${\displaystyle {\underline {X}}=\left\{\left({\check {n}},p\right)\mid p(n)=1\right\}.}$ 

Then ${\displaystyle \operatorname {val} ({\underline {X}},G)=X.}$  Now suppose that ${\displaystyle A\subseteq \omega }$  in ${\displaystyle V}$ . We claim that ${\displaystyle X\neq A}$ . Let

${\displaystyle D_{A}=\{p\mid (\exists n)(n\in \operatorname {Dom} (p)\land (p(n)=1\iff n\notin A))\}.}$ 

Then ${\displaystyle D_{A}}$  is dense. (Given any ${\displaystyle p}$ , find ${\displaystyle n}$  that is not in its domain, and adjoin a value for ${\displaystyle n}$  contrary to the status of "${\displaystyle n\in A}$ ".) Then any ${\displaystyle p\in G\cap D_{A}}$  witnesses ${\displaystyle X\neq A}$ . To summarize, ${\displaystyle X}$  is a "new" subset of ${\displaystyle \omega }$ , necessarily infinite.

Replacing ${\displaystyle \omega }$  with ${\displaystyle \omega \times \omega _{2}}$ , that is, consider instead finite partial functions whose inputs are of the form ${\displaystyle (n,\alpha )}$ , with ${\displaystyle n<\omega }$  and ${\displaystyle \alpha <\omega _{2}}$ , and whose outputs are ${\displaystyle 0}$  or ${\displaystyle 1}$ , one gets ${\displaystyle \omega _{2}}$  new subsets of ${\displaystyle \omega }$ . They are all distinct, by a density argument: Given ${\displaystyle \alpha <\beta <\omega _{2}}$ , let

${\displaystyle D_{\alpha ,\beta }=\{p\mid (\exists n)(p(n,\alpha )\neq p(n,\beta ))\},}$ 

then each ${\displaystyle D_{\alpha ,\beta }}$  is dense, and a generic condition in it proves that the αth new set disagrees somewhere with the ${\displaystyle \beta }$ th new set.

This is not yet the falsification of the continuum hypothesis. One must prove that no new maps have been introduced which map ${\displaystyle \omega }$  onto ${\displaystyle \omega _{1}}$ , or ${\displaystyle \omega _{1}}$  onto ${\displaystyle \omega _{2}}$ . For example, if one considers instead ${\displaystyle \operatorname {Fin} (\omega ,\omega _{1})}$ , finite partial functions from ${\displaystyle \omega }$  to ${\displaystyle \omega _{1}}$ , the first uncountable ordinal, one gets in ${\displaystyle V[G]}$  a bijection from ${\displaystyle \omega }$  to ${\displaystyle \omega _{1}}$ . In other words, ${\displaystyle \omega _{1}}$  has collapsed, and in the forcing extension, is a countable ordinal.

The last step in showing the independence of the continuum hypothesis, then, is to show that Cohen forcing does not collapse cardinals. For this, a sufficient combinatorial property is that all of the antichains of the forcing poset are countable.

The countable chain condition

Main article: Countable chain condition

An (strong) antichain ${\displaystyle A}$  of ${\displaystyle \mathbb {P} }$  is a subset such that if ${\displaystyle p,q\in A}$  and ${\displaystyle p\neq q}$ , then ${\displaystyle p}$  and ${\displaystyle q}$  are incompatible (written ${\displaystyle p\perp q}$ ), meaning there is no ${\displaystyle r}$  in ${\displaystyle \mathbb {P} }$  such that ${\displaystyle r\leq p}$  and ${\displaystyle r\leq q}$ . In the example on Borel sets, incompatibility means that ${\displaystyle p\cap q}$  has zero measure. In the example on finite partial functions, incompatibility means that ${\displaystyle p\cup q}$  is not a function, in other words, ${\displaystyle p}$  and ${\displaystyle q}$  assign different values to some domain input.

${\displaystyle \mathbb {P} }$  satisfies the countable chain condition (c.c.c.) if and only if every antichain in ${\displaystyle \mathbb {P} }$  is countable. (The name, which is obviously inappropriate, is a holdover from older terminology. Some mathematicians write "c.a.c." for "countable antichain condition".)

It is easy to see that ${\displaystyle \operatorname {Bor} (I)}$  satisfies the c.c.c. because the measures add up to at most ${\displaystyle 1}$ . Also, ${\displaystyle \operatorname {Fin} (E,2)}$  satisfies the c.c.c., but the proof is more difficult.

Given an uncountable subfamily ${\displaystyle W\subseteq \operatorname {Fin} (E,2)}$ , shrink ${\displaystyle W}$  to an uncountable subfamily ${\displaystyle W_{0}}$  of sets of size ${\displaystyle n}$ , for some ${\displaystyle n<\omega }$ . If ${\displaystyle p(e_{1})=b_{1}}$  for uncountably many ${\displaystyle p\in W_{0}}$ , shrink this to an uncountable subfamily ${\displaystyle W_{1}}$  and repeat, getting a finite set ${\displaystyle \{(e_{1},b_{1}),\ldots ,(e_{k},b_{k})\}}$  and an uncountable family ${\displaystyle W_{k}}$  of incompatible conditions of size ${\displaystyle n-k}$  such that every ${\displaystyle e}$  is in ${\displaystyle \operatorname {Dom} (p)}$  for at most countable many ${\displaystyle p\in W_{k}}$ . Now, pick an arbitrary ${\displaystyle p\in W_{k}}$ , and pick from ${\displaystyle W_{k}}$  any ${\displaystyle q}$  that is not one of the countably many members that have a domain member in common with ${\displaystyle p}$ . Then ${\displaystyle p\cup \{(e_{1},b_{1}),\ldots ,(e_{k},b_{k})\}}$  and ${\displaystyle q\cup \{(e_{1},b_{1}),\ldots ,(e_{k},b_{k})\}}$  are compatible, so ${\displaystyle W}$  is not an antichain. In other words, ${\displaystyle \operatorname {Fin} (E,2)}$ -antichains are countable.^{[citation needed]}

The importance of antichains in forcing is that for most purposes, dense sets and maximal antichains are equivalent. A maximal antichain ${\displaystyle A}$  is one that cannot be extended to a larger antichain. This means that every element ${\displaystyle p\in \mathbb {P} }$  is compatible with some member of ${\displaystyle A}$ . The existence of a maximal antichain follows from Zorn's Lemma. Given a maximal antichain ${\displaystyle A}$ , let

${\displaystyle D=\left\{p\in \mathbb {P} \mid (\exists q\in A)(p\leq q)\right\}.}$ 

Then ${\displaystyle D}$  is dense, and ${\displaystyle G\cap D\neq \varnothing }$  if and only if ${\displaystyle G\cap A\neq \varnothing }$ . Conversely, given a dense set ${\displaystyle D}$ , Zorn's Lemma shows that there exists a maximal antichain ${\displaystyle A\subseteq D}$ , and then ${\displaystyle G\cap D\neq \varnothing }$  if and only if ${\displaystyle G\cap A\neq \varnothing }$ .

Assume that ${\displaystyle \mathbb {P} }$  satisfies the c.c.c. Given ${\displaystyle x,y\in V}$

February 11, 2024