Open main menu

Wikipedia β

In the mathematical discipline of set theory, forcing is a technique discovered by Paul Cohen for proving consistency and independence results. It was first used, in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory. Forcing was 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 notion 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.

Contents

IntuitionEdit

Intuitively, forcing consists of expanding the set theoretical universe   to a larger universe  . In this bigger universe, for example, one might have many new subsets of     that were not there in the old universe, and thereby violate the continuum hypothesis. While impossible on the face of it, this is just another version of Cantor's paradox about infinity. In principle, one could consider

 ,

identify   with  , and then introduce an expanded membership relation involving “new” sets of the form  . Forcing is a more elaborate version of this idea, reducing the expansion to the existence of one new set, and allowing for fine control over the properties of the expanded universe.

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.

Forcing posetsEdit

A forcing poset is an ordered triple,  , where   is a preorder on   that is atomless, meaning that it satisfies the following condition:

  • For each  , there are   such that  , with no   such that  . The largest element of   is  , that is,   for all  . Members of   are called forcing conditions or just conditions. One reads   as “  is stronger than  ”. Intuitively, the “smaller” condition provides “more” information, just as the smaller interval   provides more information about the number   than the interval   does.

There are various conventions in use. Some authors require   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.

 -namesEdit

Associated with a forcing poset   is the class   of  -names. A  -name is a set   of the form

 

This is actually a definition by transfinite recursion. More precisely, one first uses transfinite recursion to define the following hierarchy:

 

Then the class of  -names is defined as

 

The  -names are, in fact, an expansion of the universe. Given  , one defines   to be the  -name

 

Again, this is really a definition by transfinite recursion.

InterpretationEdit

Given any subset   of  , one next defines the interpretation or valuation map from  -names by

 

This is again a definition by transfinite recursion. Note that if  , then  . One then defines

 

so that  .

ExampleEdit

A good example of a forcing poset is  , where   and   is the collection of Borel subsets of   having non-zero Lebesgue measure. In this case, one can talk about the conditions as being probabilities, and a  -name assigns membership in a probabilistic sense. Due to the ready intuition this example can provide, probabilistic language is sometimes used with other forcing posets.

Countable transitive models and generic filtersEdit

The key step in forcing is, given a   universe  , to find an appropriate object   not in  . The resulting class of all interpretations of  -names will turn out to be a model of   that properly extends the original   (since  ).

Instead of working with  , one considers a countable transitive model   with  . By “model”, we mean a model of set theory, either of all of  , or a model of a large but finite subset of  , or some variant thereof. “Transitivity” means that if  , then  . The Mostowski collapse lemma says that this can be assumed if the membership relation is well-founded. The effect of transitivity is that membership and other elementary notions can be handled intuitively. Countability of the model relies on the Löwenheim–Skolem theorem.

As   is a set, there are sets not in   – this follows from Russell's paradox. The appropriate set   to pick and adjoin to   is a generic filter on  . The “filter” condition means that

  •  ;
  •  ;
  • if  , then  ;
  • if  , then there exists an   such that  .

For   to be “generic” means:

  • If   is a “dense” subset of   (that is, for each  , there exists a   such that  ), then  .

The existence of a generic filter   follows from the Rasiowa–Sikorski lemma. In fact, slightly more is true: Given a condition  , one can find a generic filter   such that  . Due to the splitting condition, if   is a filter, then   is dense. If  , then   because   is a model of  . For this reason, a generic filter is never in  .

ForcingEdit

Given a generic filter  , one proceeds as follows. The subclass of  -names in   is denoted  . Let  . To reduce the study of the set theory of   to that of  , one works with the “forcing language”, which is built up like ordinary first-order logic, with membership as the binary relation and all the  -names as constants.

Define   (to be read as “  forces   in the model   with poset  ”), where   is a condition,   is a formula in the forcing language, and the  ’s are  -names, to mean that if   is a generic filter containing  , then  . The special case   is often written as “ ” or simply “ ”. Such statements are true in  , no matter what   is.

What is important is that this external definition of the forcing relation   is equivalent to an internal definition within  , defined by transfinite induction over the  -names on instances of   and  , and then by ordinary induction over the complexity of formulae. This has the effect that all the properties of   are really properties of  , and the verification of   in   becomes straightforward. This is usually summarized as the following three key properties:

  • Truth:   if and only if it is forced by  , that is, for some condition  , we have  .
  • Definability: The statement “ ” is definable in  .
  • Coherence: If   and  , then  .

We define the forcing relation   in   by induction on the complexity of formulas, in which we first define the relation for atomic formulas by  -induction and then define it for arbitrary formulas by induction on their complexity.

Define we forcing relation on atomic formulas. We define forcing of both types of formulas   and   simultaneously. This means that we define one relation   where   denotes type of formula as follows:

1.   means  .

2.   means  .

3.   means  .

Here   is condition and   and   are  -names. Let   is formula defined by  -induction:

R1.   if and only if  .

R2.   if and only if  .

R3.   if and only if  .

More formally, we use following binary relation  -names: Let   holds for names   and   if and only if   for at least one condition  . This relation is well founded, which means that for any name   the class of all names   such that holds   is set and there are no function   such that  .

Well founded relation is not preorder in general because in general it is not transitive. But, if we consider it as "ordering", then well founded relation is relation without infinite decreasing sequences and where for any element the class of elements below it is set.

It is easy to close any binary relation for transitivity. For names   and   holds   if there is at least one finite sequence   (as map with domain  ) for some   such that  ,   and for any   holds  . Such ordering is well founded to.

We define following well defined ordering on pairs of names:   if one of following holds:

1.  ,

2.   and  ,

3.   and    .

Relation   is defined by recursion on pair   of names. For any pair it is defined by the same relation on "more simple" pairs. Actually, by the recursion theorem there is a formula   such that R1, R2 and R3 are theorems because it's the truth value at some point is defined by it's truth value in "smaller" points relative to the some well founded relation used as "ordering". Now, we are ready define forcing relation.

1.   means  .

2.   means  .

3.   means  .

4.   means  .

5.   means  .

Actually, this is transform of arbitrary formula   to formula   where   and   are additional variables. This is definition of forcing relation in universe of all set regardless to any countable transitive model. However, there is relation between this "syntax" formulation of forcing and "semantic" formulation of forcing over some countable transitive model  .

1. For any formula   there is theorem   of the theory   (for example conjunction of finite number of axioms) such that for any countable transitive model   such that   and any atomless partial order   and any  -generic filter   over   holds

 .

This is announced property of definability of forcing relation.

ConsistencyEdit

The discussion above can be summarized by the fundamental consistency result that, given a forcing poset  , we may assume the existence of a generic filter  , not belonging to the universe  , such that   is again a set-theoretic universe that models  . Furthermore, all truths in   may be reduced to truths in   involving the forcing relation.

Both styles, adjoining   to either a countable transitive model   or the whole universe  , 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 forcingEdit

The simplest nontrivial forcing poset is  , the finite partial functions from   to   under reverse inclusion. That is, a condition   is essentially two disjoint finite subsets   and   of  , to be thought of as the “yes” and “no” parts of  , with no information provided on values outside the domain of  . “  is stronger than  ” means that  , in other words, the “yes” and “no” parts of   are supersets of the “yes” and “no” parts of  , and in that sense, provide more information.

Let   be a generic filter for this poset. If   and   are both in  , then   is a condition because   is a filter. This means that   is a well-defined partial function from   to   because any two conditions in   agree on their common domain.

In fact,   is a total function. Given  , let  . Then   is dense. (Given any  , if   is not in  ’s domain, adjoin a value for   — the result is in  .) A condition   has   in its domain, and since  , we find that   is defined.

Let  , the set of all “yes” members of the generic conditions. It is possible to give a name for   directly. Let  . Then  . Now suppose that   in  . We claim that  . Let  . Then   is dense. (Given any  , if   is not in  ’s domain, adjoin a value for   contrary to the status of “ ”.) Then any   witnesses  . To summarize,   is a “new” subset of  , necessarily infinite.

Replacing   with  , that is, consider instead finite partial functions whose inputs are of the form  , with   and  , and whose outputs are   or  , one gets   new subsets of  . They are all distinct, by a density argument: Given  , let  , then each   is dense, and a generic condition in it proves that the αth new set disagrees somewhere with the  -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   onto  , or   onto  . For example, if one considers instead  , finite partial functions from   to  , the first uncountable ordinal, one gets in   a bijection from   to  . In other words,   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 this poset are countable.

The countable chain conditionEdit

An antichain   of   is a subset such that if  , then   and   are incompatible (written  ), meaning there is no   in   such that   and  . In the example on Borel sets, incompatibility means that   has zero measure. In the example on finite partial functions, incompatibility means that   is not a function, in other words,   and   assign different values to some domain input.

  satisfies the countable chain condition (c.c.c.) if and only if every antichain in   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   satisfies the c.c.c. because the measures add up to at most  . Also,   is c.c.c., but the proof is more difficult.

Given an uncountable subfamily  , shrink   to an uncountable subfamily   of sets of size  , for some  . If   for uncountably many  , shrink this to an uncountable subfamily   and repeat, getting a finite set   and an uncountable family   of incompatible conditions of size   such that every   is in   for at most countable many  . Now, pick an arbitrary  , and pick from   any   that is not one of the countably many members that have a domain member in common with  . Then   and   are compatible, so   is not an antichain. In other words,  -antichains are countable.

The importance of antichains in forcing is that for most purposes, dense sets and maximal antichains are equivalent. A maximal antichain   is one that cannot be extended to a larger antichain. This means that every element   is compatible with some member of  . The existence of a maximal antichain follows from Zorn’s Lemma. Given a maximal antichain  , let  . Then   is dense, and   if and only if  . Conversely, given a dense set  , Zorn’s Lemma shows that there exists a maximal antichain  , and then   if and only if  .

Assume that   is c.c.c. Given  , with   a function in  , one can approximate   inside   as follows. Let   be a name for   (by the definition of  ) and let   be a condition that forces   to be a function from   to  . Define a function  , whose domain is  , by  . By the definability of forcing, this definition makes sense within  . By the coherence of forcing, different  ’s come from incompatible  ’s. By c.c.c.,   is countable.

In summary,   is unknown in   as it depends on  , 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   is at any input, independent of  .

This has the following very important consequence. If in  ,   is a surjection from one infinite ordinal onto another, then there is a surjection   in  , and consequently, a surjection   in  . In particular, cardinals cannot collapse. The conclusion is that   in  .

Easton forcingEdit

The exact value of the continuum in the above Cohen model, and variants like   for cardinals   in general, was worked out by Robert M. Solovay, who also worked out how to violate   (the generalized continuum hypothesis), for regular cardinals only, a finite number of times. For example, in the above Cohen model, if   holds in  , then   holds in  .

William B. Easton worked out the proper class version of violating the   for regular cardinals, basically showing that the known restrictions, (monotonicity, Cantor’s Theorem and König’s Theorem), were the only  -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  . For example, forcing with  , where   is the proper class of all ordinals, makes the continuum a proper class. On the other hand, forcing with   introduces a countable enumeration of the ordinals. In both cases, the resulting   is visibly not a model of  .

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   and with the forcing models depending on the consistency of various large-cardinal properties. Many open problems remain.

Random realsEdit

Random forcing can be defined as forcing over set   of all compact subsets of   of positive measure ordered by relation   (smaller set in context of inclusion is smaller set in ordering and represents condition with more information). There are two types of important dense sets:

1. For any positive integer   the set   is dense, where   is diameter of the set  .

2. For any Borel subset   of   of measure 1, the set   is dense.

For any filter   and for any finitely many elements   there is   such that holds  . In case of this ordering, this means that any filter is set of compact sets with finite intersection property. For this reason, intersection of all elements of any filter is nonempty. Let   is filter intersecting dense set   for any positive integer  , then filter   contains conditions of arbitrary small positive diameter. Therefore, intersection of all conditions from   has diameter 0. Only nonempty sets of diameter 0 are singletons. Finally, there is exactly one real number   such that  .

Let   is any Borel set of measure 1. If   intersects  , then  .

However, generic filter over countable transitive model   is not in  . Real   is defined by  . One can prove that it is not in   to. Problem is that if  , then  "  is compact", but from the viewpoint of universe   can be non-compact and intersection of all conditions from generic filter is actually empty. For this reason, we consider set   of closures (in topological sense) of conditions from generic filter. Due to   and finite intersection property of  , the set   has finite intersection property to. Elements of the set   are bounded closed sets as closures of bounded sets. Therefore,   is set of compacts with finite intersection property and for this reason has nonempty intersection. Due to   and model   inherits metric from universe, the set   has elements of arbitrary small diameter. Finally, there is exactly one real which belongs to all members of the set  . The generic filter   can be reconstructed from   as  .

If   is name of  , and for   holds  "  is Borel set of measure 1", then holds   for some  . There is name   such that for any generic filter   holds  . Then   holds for any condition  .

Every Borel set can, non-uniquely, be built up, starting from intervals with rational endpoints and applying the operations of complement and countable unions, a countable number of times. The record of such a construction is called a Borel code. Given a Borel set   in  , one recovers a Borel code, and then applies the same construction sequence in  , getting a Borel set  . One can prove that one gets the same set independent of the construction of  , and that basic properties are preserved. For example, if  , then  . If   has measure zero, then   has measure zero. This mapping   is injective.

For any set   such that   and  "  is Borel set of measure 1" holds  .

This means that   is "infinite random sequence of 0's and 1's" from the viewpoint of   which means that it satisfies all statistical tests from the ground model  .

So given  , a random real, one can show that  . Because of the mutual inter-definability between   and  , one generally writes   for  .

A different interpretation of reals in   was provided by Dana Scott. Rational numbers in   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  . Real numbers in   then correspond to Dedekind cuts of such functions, that is, measurable functions.

Boolean-valued modelsEdit

Perhaps more clearly, the method can be explained in terms of Boolean-valued models. In these, any statement is assigned a truth value from some complete atomless Boolean algebra, rather than just a true/false value. Then an ultrafilter is picked in this Boolean algebra, which assigns values true/false to statements of our theory. The point is that the resulting theory has a model which contains this ultrafilter, which can be understood as a new model obtained by extending the old one with this ultrafilter. By picking a Boolean-valued model in an appropriate way, we can get a model that has the desired property. In it, only statements which must be true (are "forced" to be true) will be true, in a sense (since it has this extension/minimality property).

Meta-mathematical explanationEdit

In forcing, we usually seek to show that some sentence is consistent with   (or optionally some extension of  ). One way to interpret the argument is to assume that   is consistent and then prove that   combined with the new sentence is also consistent.

Each “condition” is a finite piece of information – the idea is that only finite pieces are relevant for consistency, since, by the Compactness Theorem, a theory is satisfiable if and only if every finite subset of its axioms is satisfiable. Then we can pick an infinite set of consistent conditions to extend our model. Therefore, assuming the consistency of  , we prove the consistency of   extended by this infinite set.

Logical explanationEdit

By Gödel's second incompleteness theorem, one cannot prove the consistency of any sufficiently strong formal theory, such as  , using only the axioms of the theory itself, unless the theory is inconsistent. Consequently, mathematicians do not attempt to prove the consistency of   using only the axioms of  , or to prove that   is consistent for any hypothesis   using only  . For this reason, the aim of a consistency proof is to prove the consistency of   relative to the consistency of  . Such problems are known as problems of relative consistency. In fact one proves

(*)  

We will now give the general schema of relative consistency proofs. As any proof is finite, it uses only a finite number of axioms:

 

For any given proof,   can verify the validity of this proof. This is provable by induction on the length of the proof.

 

Now, we obtain

 

If we prove the following,

(**)  ,

we can conclude that

 ,

which is equivalent to

 ,

which gives (*). The core of the relative consistency proof is proving (**). One has to construct a   proof of   for any given finite subset   of the   axioms (by   instruments of course). (No universal proof of   of course.)

In  , it is provable that for any condition  , the set of formulas (evaluated by names) forced by   is deductively closed. Furthermore, for any   axiom,   proves that this axiom is forced by  . Then it suffices to prove that there is at least one condition that forces  .

In the case of Boolean-valued forcing, the procedure is similar – one has to prove that the Boolean value of   is not  .

Another approach uses the Reflection Theorem. For any given finite set of   axioms, there is a   proof that this set of axioms has a countable transitive model. For any given finite set   of   axioms, there is a finite set   of   axioms such that   proves that if a countable transitive model   satisfies  , then   satisfies  . One has to prove that there is finite set   of   axioms such that if a countable transitive model   satisfies  , then   satisfies the hypothesis  . Then, for any given finite set   of   axioms,   proves  .

Sometimes in (**), a stronger theory   than   is used for proving  . Then we have proof of the consistency of   relative to the consistency of  . Note that  , where   is   (the axiom of constructibility).

See alsoEdit

ReferencesEdit

External linksEdit

  • Nik Weaver’s book Forcing for Mathematicians was written for mathematicians who want to learn the basic machinery of forcing. No background in logic is assumed, beyond the facility with formal syntax which should be second nature to any well-trained mathematician.
  • Timothy Chow’s article A Beginner’s Guide to Forcing is a good introduction to the concepts of forcing that avoids a lot of technical detail. This paper grew out of Chow’s newsgroup article Forcing for dummies. In addition to improved exposition, the Beginner’s Guide includes a section on Boolean-valued models.
  • See also Kenny Easwaran’s article A Cheerful Introduction to Forcing and the Continuum Hypothesis, which is also aimed at the beginner but includes more technical details than Chow’s article.
  • Cohen, P. J. The Independence of the Continuum Hypothesis, Proceedings of the National Academy of Sciences of the United States of America, Vol. 50, No. 6. (Dec. 15, 1963), pp. 1143–1148.
  • Cohen, P. J. The Independence of the Continuum Hypothesis, II, Proceedings of the National Academy of Sciences of the United States of America, Vol. 51, No. 1. (Jan. 15, 1964), pp. 105–110.
  • Paul Cohen gave a historical lecture The Discovery of Forcing (Rocky Mountain J. Math. Volume 32, Number 4 (2002), 1071–1100) about how he developed his independence proof. The linked page has a download link for an open access PDF but your browser must send a referer header from the linked page to retrieve it.
  • Weisstein, Eric W. "Forcing". MathWorld.