Forcing (mathematics)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 22 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In 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 V to a larger universe V[G] by introducing a new "generic" object 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 computability theory. Descriptive set theory uses the notions of forcing from both computability 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.

In 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 V to a larger universe V[G] by introducing a new "generic" object 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 computability theory. Descriptive set theory uses the notions of forcing from both computability 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. However, in some sense, it may be desirable to "construct the expanded model M[X] within M ". This would help ensure that M[X] "resembles" M in certain aspects, such as \aleph_2^{M[X]} being the same as \aleph_2^M (more generally, that cardinal collapse does not occur), and allow fine control over the properties of M[X] . More precisely, every member of M[X] should be given a (non-unique) name in M . The name can be thought as an expression in terms of X , just like in a simple field extension L = K(\theta) every element of L can be expressed in terms of \theta . A major component of forcing is manipulating those names within M , so sometimes it may help to directly think of M as "the universe", knowing that the theory of forcing guarantees that M[X] will correspond to an actual model. A subtle point of forcing is that, if X is taken to be an arbitrary "missing subset" of some set in M , then the M[X] constructed "within M " may not even be a model. This is because X may encode "special" information about M that is invisible within M (e.g. the countability of M ), and thus prove the existence of sets that are "too complex for M to describe". Forcing avoids such problems by requiring the newly introduced set X to be a generic set relative to M . Some statements are "forced" to hold for any generic X : For example, a generic X is "forced" to be infinite. Furthermore, any property (describable in M ) of a generic set is "forced" to hold under some forcing condition. The concept of "forcing" can be defined within M , and it gives M enough reasoning power to prove that 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. The forcing poset for Cohen forcing can be formally written as (\operatorname{Fin}(S,2),\supseteq,\emptyset) , the finite partial functions from S to 2 ~ \stackrel{\text{df}}{=} ~ \{ 0,1 \} under reverse inclusion. Cohen forcing satisfies the splitting condition because given any condition p , one can always find an element a \in S not mentioned in p , and add either the sentence a \in X or a \notin X to p to get two new forcing conditions, incompatible with each other. Another instructive example of a forcing poset is (\operatorname{Bor}(I),\subseteq,I) , where I = [0,1] and \operatorname{Bor}(I) is the collection of Borel subsets of I having non-zero Lebesgue measure. The generic object associated with this forcing poset is a random real number r \in [0, 1] . It can be shown that r falls in every Borel subset of [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. \operatorname{val}(u,G) = \{ \operatorname{val}(v,G) \mid \exists p \in G: ~ (v,p) \in u \}. The \mathbb{P} -names are, in fact, an expansion of the universe. Given x \in V , one defines \check{x} to be the \mathbb{P} -name \check{x} = \{ (\check{y},\mathbf{1}) \mid y \in x \}. Since \mathbf{1} \in G , it follows that \operatorname{val}(\check{x},G) = x . In a sense, \check{x} is a "name for x " that does not depend on the specific choice of G . This also allows defining a "name for G " without explicitly referring to G : \underline{G} = \{ (\check{p},p) \mid p \in \mathbb{P} \} so that \operatorname{val}(\underline{G},G) = \{\operatorname{val}(\check p, G) \mid p \in G\} = G . \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 Then the class of \mathbb{P} -names is defined as V^{(\mathbb{P})} = \bigcup \{ \operatorname{Name}(\alpha) ~|~ \alpha ~ \text{is an ordinal} \}. The interpretation map and the map x \mapsto \check{x} can similarly be defined with a hierarchical construction. M[G] = \left\{ \operatorname{val}(u,G) ~ \Big| ~ u \in M^{(\mathbb{P})} \right\}. To reduce the study of the set theory of M[G] to that of 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 \mathbb{P} -names as constants. Define p \Vdash_{M,\mathbb{P}} \varphi(u_1,\ldots,u_n) (to be read as " p forces \varphi in the model M with poset \mathbb{P} "), where p is a condition, \varphi is a formula in the forcing language, and the u_{i} 's are \mathbb{P} -names, to mean that if G is a generic filter containing p , then M[G] \models \varphi(\operatorname{val}(u_1,G),\ldots,\operatorname{val}(u_{n},G)) . The special case \mathbf{1} \Vdash_{M,\mathbb{P}} \varphi is often written as " \mathbb{P} \Vdash_{M,\mathbb{P}} \varphi " or simply " \Vdash_{M,\mathbb{P}} \varphi ". Such statements are true in M[G] , no matter what G is. What is important is that this external definition of the forcing relation p \Vdash_{M,\mathbb{P}} \varphi is equivalent to an internal definition within M , defined by transfinite induction (specifically \in -induction) over the \mathbb{P} -names on instances of u \in v and u = v , and then by ordinary induction over the complexity of formulae. This has the effect that all the properties of M[G] are really properties of M , and the verification of \mathsf{ZFC} in M[G] becomes straightforward. This is usually summarized as the following three key properties: Truth: M[G] \models \varphi(\operatorname{val}(u_1,G),\ldots,\operatorname{val}(u_n,G)) if and only if it is forced by G , that is, for some condition p \in G , we have p \Vdash_{M,\mathbb{P}} \varphi(u_1,\ldots,u_n) . Definability: The statement " p \Vdash_{M,\mathbb{P}} \varphi(u_1,\ldots,u_n) " is definable in M . Coherence: 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) . 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 \Vdash_{M,\mathbb{P}}^* rather than \Vdash_{M,\mathbb{P}} . The modified forcing relation \Vdash_{M,\mathbb{P}}^* can be defined recursively as follows: p \Vdash_{M,\mathbb{P}}^* u \in v means (\exists (w, q) \in v) (q \ge p \wedge p \Vdash_{M,\mathbb{P}}^* w = u). p \Vdash_{M,\mathbb{P}}^* u \ne v means (\exists (w, q) \in v) (q \ge p \wedge p \Vdash_{M,\mathbb{P}}^* w \notin u) \vee (\exists (w, q) \in u) (q \ge p \wedge p \Vdash_{M,\mathbb{P}}^* w \notin v). p \Vdash_{M,\mathbb{P}}^* \neg \varphi means \neg (\exists q \le p) (q \Vdash_{M,\mathbb{P}}^* \varphi). p \Vdash_{M,\mathbb{P}}^* (\varphi \vee \psi) means (p \Vdash_{M,\mathbb{P}}^* \varphi) \vee (p \Vdash_{M,\mathbb{P}}^* \psi). p \Vdash_{M,\mathbb{P}}^* \exists x\, \varphi(x) means (\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, u = v means \neg (u \ne v) , \forall x\, \varphi(x) means \neg \exists x\, \neg \varphi(x) , etc. Cases 1 and 2 depend on each other and on case 3, but the recursion always refers to \mathbb{P} -names with lesser ranks, so transfinite induction allows the definition to go through. By construction, \Vdash_{M,\mathbb{P}}^* (and thus \Vdash_{M,\mathbb{P}} ) automatically satisfies Definability. The proof that \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 \vee and \exists as the elementary symbols ), cases 1 and 2 rely only on the assumption that G is a filter, and only case 3 requires G to be a generic filter. Formally, an internal definition of the forcing relation (such as the one presented above) is actually a transformation of an arbitrary formula \varphi(x_1,\dots,x_n) to another formula p\Vdash_{\mathbb{P}}\varphi(u_1,\dots,u_n) where p and \mathbb{P} are additional variables. The model M does not explicitly appear in the transformation (note that within M , u \in M^{(\mathbb{P})} just means " u is a \mathbb{P} -name"), and indeed one may take this transformation as a "syntactic" definition of the forcing relation in the universe V of all sets regardless of any countable transitive model. However, if one wants to force over some countable transitive model M , then the latter formula should be interpreted under M (i.e. with all quantifiers ranging only over M ), in which case it is equivalent to the external "semantic" definition of \Vdash_{M,\mathbb{P}} described at the top of this section: For any formula \varphi(x_1,\dots,x_n) there is a theorem T of the theory \mathsf{ZFC} (for example, a conjunction of a finite number of axioms) such that for any countable transitive model M such that M\models T and any partial order satisfying the splitting condition \mathbb{P}\in M and any \mathbb{P} -generic filter G over M (\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 is the sense in which the forcing relation is indeed "definable in M ". The simplest nontrivial forcing poset is (\operatorname{Fin}(\omega,2),\supseteq,\emptyset) , the finite partial functions from \omega to 2 ~ \stackrel{\text{df}}{=} ~ \{ 0,1 \} under reverse inclusion. That is, a condition p is essentially two disjoint finite subsets {p^{-1}}[1] and {p^{-1}}[0] of \omega , to be thought of as the "yes" and "no" parts of with no information provided on values outside the domain of p . " q is stronger than p " means that q \supseteq p , in other words, the "yes" and "no" parts of q are supersets of the "yes" and "no" parts of p , and in that sense, provide more information. Let G be a generic filter for this poset. If p and q are both in G , then p \cup q is a condition because G is a filter. This means that g = \bigcup G is a well-defined partial function from \omega to 2 because any two conditions in G agree on their common domain. In fact, g is a total function. Given n \in \omega , let D_{n} = \{ p \mid p(n) ~ \text{is defined} \} . Then D_{n} is dense. (Given any p , if n is not in p 's domain, adjoin a value for n —the result is in D_{n} .) A condition p \in G \cap D_{n} has n in its domain, and since p \subseteq g , we find that g(n) is defined. Let X = {g^{-1}}[1] , the set of all "yes" members of the generic conditions. It is possible to give a name for X directly. Let \underline{X} = \left \{ \left (\check{n},p \right ) \mid p(n) = 1 \right \}. Then \operatorname{val}(\underline{X},G) = X. Now suppose that A \subseteq \omega in V . We claim that X \neq A . Let D_{A} = \{ p \mid \exists n(n \in \operatorname{Dom}(p) \land (p(n) = 1 \iff n \notin A)) \}. Then D_A is dense. (Given any p , find n that is not in its domain, and adjoin a value for n contrary to the status of " n \in A ".) Then any p \in G \cap D_A witnesses X \neq A . To summarize, X is a "new" subset of \omega , necessarily infinite. Replacing \omega with \omega \times \omega_{2} , that is, considering instead finite partial functions whose inputs are of the form (n,\alpha) , with n and \alpha , and whose outputs are 0 or 1 , one gets \omega_{2} new subsets of \omega . They are all distinct, by a density argument: Given \alpha , let D_{\alpha,\beta} = \{ p \mid \exists n(p(n,\alpha) \neq p(n,\beta)) \}, then each D_{\alpha,\beta} is dense, and a generic condition in it proves that the αth new set disagrees somewhere with the \beta th new set. This is not yet the falsification of the continuum hypothesis. One must prove that no new maps have been introduced that map \omega onto \omega_{1} , or \omega_{1} onto \omega_{2} . For example, if one considers instead \operatorname{Fin}(\omega,\omega_{1}) , finite partial functions from \omega to \omega_{1} , the first uncountable ordinal, one gets in V[G] a bijection from \omega to \omega_{1} . In other words, \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. Given an uncountable subfamily W \subseteq \operatorname{Fin}(E,2) , shrink W to an uncountable subfamily W_{0} of sets of size at most n , for some n (for some n this is uncountable, since otherwise W = \bigcup_{n would be a countable union of countable sets, thus countable). If p(e_{1}) = b_{1} for uncountably many p \in W_{0} , shrink this to an uncountable subfamily W_{1} and repeat, getting a finite set \{ (e_{1},b_{1}),\ldots,(e_{k},b_{k}) \} \in W_{0} and an uncountable family W_{k} of incompatible conditions of size n - k such that every e is in \operatorname{Dom}(p) for at most countable many p \in W_{k} . Now, pick an arbitrary p \in W_{k} , and pick from W_{k} any q that is not one of the countably many members that have a domain member in common with p . Then p \cup \{ (e_{1},b_{1}),\ldots,(e_{k},b_{k}) \} and q \cup \{ (e_{1},b_{1}),\ldots,(e_{k},b_{k}) \} are compatible, so W is not an antichain. In other words, \operatorname{Fin}(E,2) -antichains are countable. The importance of antichains in forcing is that for most purposes, dense sets and maximal antichains are equivalent. A maximal antichain A is one that cannot be extended to a larger antichain. This means that every element p \in \mathbb{P} is compatible with some member of A . The existence of a maximal antichain follows from Zorn's Lemma. Given a maximal antichain A , let D = \left \{ p \in \mathbb{P} \mid (\exists q \in A)(p \leq q) \right \}. Then D is dense, and G \cap D \neq \varnothing if and only if G \cap A \neq \varnothing . Conversely, given a dense set D , Zorn's Lemma shows that there exists a maximal antichain A \subseteq D , and then G \cap D \neq \varnothing if and only if G \cap A \neq \varnothing . Assume that \mathbb{P} satisfies the c.c.c. Given x,y \in V , with f: x \to y a function in V[G] , one can approximate f inside V as follows. Let u be a name for f (by the definition of V[G] ) and let p be a condition that forces u to be a function from x to y . Define a function F: x \to \mathcal{P}(y) , by F(a) \stackrel{\text{df}}{=} \left \{ b \left | (\exists q \in \mathbb{P}) \left [(q \leq p) \land \left (q \Vdash ~ u \left (\check{a} \right ) = \check{b} \right ) \right ] \right \}. \right. By the definability of forcing, this definition makes sense within V . By the coherence of forcing, a different b must come from an incompatible p . By c.c.c., F(a) is countable. In summary, f is unknown in V as it depends on G , but it is not wildly unknown for a c.c.c.-forcing. One can identify a countable set of guesses for what the value of f is at any input, independent of G . This has the following very important consequence. If in V[G] , f: \alpha \to \beta is a surjection from one infinite ordinal onto another, then there is a surjection g: \omega \times \alpha \to \beta in V , and consequently, a surjection h: \alpha \to \beta in V . In particular, cardinals cannot collapse. The conclusion is that 2^{\aleph_{0}} \geq \aleph_{2} in V[G] . The exact value of the continuum in the above Cohen model, and variants like \operatorname{Fin}(\omega \times \kappa,2) for cardinals \kappa in general, was worked out by Robert M. Solovay, who also worked out how to violate \mathsf{GCH} (the generalized continuum hypothesis), for regular cardinals only, a finite number of times. For example, in the above Cohen model, if \mathsf{CH} holds in V , then 2^{\aleph_{0}} = \aleph_{2} holds in V[G] . William B. Easton worked out the proper class version of violating the \mathsf{GCH} for regular cardinals, basically showing that the known restrictions, (monotonicity, Cantor's theorem and König's theorem), were the only \mathsf{ZFC} -provable restrictions (see Easton's theorem). Easton's work was notable in that it involved forcing with a proper class of conditions. In general, the method of forcing with a proper class of conditions fails to give a model of \mathsf{ZFC} . For example, forcing with \operatorname{Fin}(\omega \times \mathbf{On},2) , where \mathbf{On} is the proper class of all ordinals, makes the continuum a proper class. On the other hand, forcing with \operatorname{Fin}(\omega,\mathbf{On}) introduces a countable enumeration of the ordinals. In both cases, the resulting V[G] is visibly not a model of \mathsf{ZFC} . At one time, it was thought that more sophisticated forcing would also allow an arbitrary variation in the powers of singular cardinals. However, this has turned out to be a difficult, subtle and even surprising problem, with several more restrictions provable in \mathsf{ZFC} and with the forcing models depending on the consistency of various large-cardinal properties. Many open problems remain. For any positive integer n , the set D_n= \left \{p\in P : \operatorname{diam}(p) is dense, where \operatorname{diam}(p) is the diameter of the set p . For any Borel subset B \subseteq [0,1] of measure 1, the set D_B=\{p\in P : p\subseteq B\} is dense. For any filter G and any pair of elements p_1,p_2\in G there is q\in G such that q\leq p_1,p_2 . In this ordering, this means that any filter is closed under finite intersection. Therefore, by Cantor's intersection theorem, the intersection of all the elements in any filter is nonempty. If G is a filter intersecting the dense set D_n for any positive integer n , then the filter G contains conditions of arbitrarily small positive diameter. Therefore, the intersection of all conditions from G has diameter 0. But the only nonempty sets of diameter 0 are singletons. So there is exactly one real number r_G such that r_G\in\bigcap G . Let B\subseteq[0,1] be any Borel set of measure 1. If G intersects D_B , then r_G\in B . However, a generic filter over a countable transitive model M is not in M . The real r_G defined by G is provably not an element of M . One issue with this construction is that if p\in P , then M\models " p is compact", but from the viewpoint of some larger universe V\supseteq M , p can be non-compact and the intersection of all conditions from the generic filter G can then be empty. To fix this, we consider the set C=\{\bar p : p \in G \} of topological closures of conditions from G . Because \bar p\supseteq p , and because G is closed under finite intersection, Cantor's intersection theorem applies and the intersection of the set C is nonempty. Since \operatorname{diam}(\bar p) = \operatorname{diam}(p) and the ground model M inherits a metric from the universe V , the set C has elements of arbitrarily small diameter. Finally, there is exactly one real that belongs to all members of the set C . The generic filter G can be reconstructed from r_G as G=\{p\in P : r_G\in\bar p\} . If a \in M^{(\mathbb{P})} is a name for r_G (i.e., M[G] \models val(a,G) = r_G ), and for B\in M holds M\models " B is a Borel set of measure 1", then by the truth property of forcing p\Vdash_{M, \mathbb{P}} a \in \check{B} for some p\in G . There is a name a that satisfies \operatorname{val}(a,G)\in\bigcup_{p\in G}\bar p for any generic filter G . For that a , p\Vdash_{M, \mathbb{P}}a\in\check{B} holds for any condition p . Every Borel set can be (non-uniquely) built up, starting from intervals with rational endpoints and applying the operations of complement and countable union, a countable number of times. The record of such a construction is called a Borel code. Given a Borel set B in V , one recovers a Borel code, and then applies the same construction sequence in M[G] , getting a Borel set B^* . It can be proven that one gets the same set independent of the code chosen for B , and that basic properties are preserved. For example, if B \subseteq C , then B^* \subseteq C^* . If B has measure zero, then B^* has measure zero. This mapping B\mapsto B^* is injective. For any set B\subseteq[0,1] such that B\in M and M\models " B is a Borel set of measure 1" one has r_{G} \in B^* . This means that r_{G} is an "infinite random sequence of 0s and 1s" from the viewpoint of M , which means that it satisfies all statistical tests from the ground model M . So given r_{G} , a random real, one can show that G = \left \{ B ~ (\text{in } M) \mid r \in B^* ~ (\text{in } M[G]) \right \}. Because of this mutual inter-definability between r and G , one generally writes M[r] for M[G] . A different interpretation of reals in M[G] was provided by Dana Scott. Rational numbers in M[G] have names that correspond to countably-many distinct rational values assigned to a maximal antichain of Borel sets – in other words, a certain rational-valued function on I = [0,1] . Real numbers in M[G] then correspond to Dedekind cuts of such functions, that is, measurable functions. Sometimes in (**), a stronger theory S than \mathsf{ZFC} is used for proving \operatorname{Con}(T + H) . Then we have proof of the consistency of \mathsf{ZFC} + H relative to the consistency of S . Note that \mathsf{ZFC} \vdash \operatorname{Con}(\mathsf{ZFC}) \leftrightarrow \operatorname{Con}(\mathsf{ZFL}) , where \mathsf{ZFL} is \mathsf{ZF} + (V = L) (the axiom of constructibility).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375658868 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.