Namespaces
Variants
Actions

Forcing method

From Encyclopedia of Mathematics
Revision as of 02:55, 3 December 2016 by Leonard Huang (talk | contribs) (Completed rendering of article in TeX and corrected notational errors.)
Jump to: navigation, search

A special method for constructing models of axiomatic set theory. It was proposed by P.J. Cohen in 1963 to prove the compatibility of the negation of the continuum hypothesis, $ \neg \mathsf{CH} $, and other set-theoretic assumptions with the axioms of the Zermelo–Fraenkel system $ \mathsf{ZF} $ ([1]). The forcing method was subsequently simplified and modernized ([2][6]). In particular, it was found that the method was related to the theory of Boolean-valued models ([2], [3]) and Kripke models ([6]).

The central concept of the forcing method is the forcing relation $$ p \Vdash \phi. $$ (This is to be read as “the condition $ p $ forces the formula $ \phi $”.)

The definition of the forcing relation is preceded by the specification of a language $ \mathcal{L} $ and a partially ordered set $ \mathbb{P} $ of forcing conditions $ p $ with an order relation $ \leq $. The language $ \mathcal{L} $ may contain variables and constants of different sorts (or types).

The construction of the model of $ \mathsf{ZF} $ proposed by Cohen in which $ \mathsf{CH} $ is violated proceeds as follows. A set $ M $ is called transitive if $$ x \in M \Rightarrow x \subseteq M. $$

Let $ M $ be a denumerable transitive set that is a model of $ \mathsf{ZF} $, and let $ \lambda \in M $ be an ordinal number in the sense of von Neumann, i.e., $ \lambda = \{ \alpha \mid \alpha < \lambda \} $. Let $ A \subseteq \lambda \times \omega_{0} $ be an arbitrary set (possibly $ A \notin M $), where $ \omega_{0} $ denotes the first infinite ordinal number. If $ X $ is a transitive set, then let $ \operatorname{Def}(X) $ denote the set of all $ X $-definable subsets, i.e., $ \operatorname{Def}(X) = \operatorname{Def}(X,\in \!\! |_{X \times X}) $. A process similar to that of defining Gödel constructive sets is used to define, via transfinite induction, a set $ {M_{\alpha}}[A] $ for any ordinal number $ \alpha $: $$ {M_{\alpha}}[A] \stackrel{\text{df}}{=} \bigcup_{\beta < \alpha} \operatorname{Def}({M_{\beta}}[A]) \cup \{ x \in M \cup \{ A\} \mid x \subseteq {M_{\beta}}[A] \}. $$

Let $ M[A] \stackrel{\text{df}}{=} {M_{\alpha_{0}}}[A] $, where $ a_{0} \stackrel{\text{df}}{=} \{ \alpha \in M \mid \alpha \text{ is an ordinal number} \} $. The model of $ \mathsf{ZF} $ in which $ \mathsf{CH} $ is violated is to be found among models of the type $ M[A] $. Let $ \lambda $ be an ordinal number such that the statement “$ \lambda $ is the second uncountable ordinal” is true in $ M $.

The set of forcing conditions $ \mathbb{P} $ and the relation $ \leq $ are defined by the following equivalences: (a) $ p \in \mathbb{P} \iff p $ is a function defined on some finite subset of $ \lambda \times \omega_{0} $, with values in $ \{ 0,1 \} $; (b) $ p \leq q \iff q $ is an extension of $ p $. The language $ \mathcal{L} $ considered is a so-called ramified language, with many types of variables (each $ \alpha \leq \alpha_{0} $ having its own type of variables running through the set $ {M_{\alpha}}[A] $) and with names (i.e., individual constants) for each set from $ M[A] $. If $ x \in M $, then the name of $ x $ is denoted by $ x^{\vee} $. Let $ a $ be the name of the set $ A $. The forcing relation $ p \Vdash \phi $ is introduced by a definition involving transfinite induction, which has, in particular, the following characteristics:

  1. $ (p \Vdash \langle \delta,n \rangle^{\vee} \in a) \iff (p(\langle \delta,n \rangle) = \mathbf{1}) $;
  2. $ (p \Vdash \neg \phi) \iff \neg (\exists q \geq p)(q \Vdash \phi) $;
  3. $ (p \Vdash (\phi \lor \psi)) \iff ((p \Vdash \phi) \lor (p \Vdash \psi)) $;
  4. $ (p \Vdash (\phi \land \psi)) \iff ((p \Vdash \phi) \land (p \Vdash \psi)) $;
  5. If $ \alpha $ is the type of the variable $ x $, then $ (p \Vdash (\exists x) \phi(x)) \iff (\exists c \in C_{\alpha})(p \Vdash \phi(c)) $, where $ C_{\alpha} $ is the set of all constants of type $ \alpha $.

A sequence of forcing conditions in $ \mathbb{P} $, $$ p_{0} \leq \ldots \leq p_{n} \leq \ldots, $$ is called complete if for any closed formula $ \phi $ of $ \mathcal{L} $, one has $$ \exists n \in \omega_{0}: \qquad (p_{n} \Vdash \phi) \lor (p_{n} \Vdash \neg \phi). $$ The countability of the set of all closed formulas of $ \mathcal{L} $, together with (2), makes it possible to demonstrate the existence of a complete sequence that begins with an arbitrary forcing condition $ p_{0} \in \mathbb{P} $.

A set $ A $ contained in $ \lambda \times \omega_{0} $ is called generic with respect to the model $ M $ if there exists a complete sequence $ (p_{n})_{n \in \omega_{0}} $ such that $ \displaystyle \bigcup_{n < \omega_{0}} p_{n} $ is the characteristic function $ \chi_{A} $ of $ A $. The following two facts about generic sets and the forcing relation are of fundamental importance:

  • If $ A $ is a generic set, then $$ M[A] \models \phi \iff (\exists p \subseteq \chi_{A})(p \Vdash \phi), $$ where $ M[A] \models \phi $ means that formula $ \phi $ is true in $ M[A] $.
  • The relation $$ p \Vdash \phi(c_{1},\ldots,c_{n}), \qquad (\text{where } c_{1},\ldots,c_{n} \text{ are constants in } \mathcal{L}) $$ regarded as a relation among $ p,c_{1},\ldots,c_{n} $, can be expressed in the model $ M $.

In view of the aforementioned facts, it is sufficient to show that the statement $$ (\forall p)(p \Vdash \neg \neg \phi), \qquad \text{i.e.}, \qquad (\forall p)(\exists q \geq p)(q \Vdash \phi), $$ is true in the model $ M $, i.e., to prove that $ M[A] \models \phi $. The verification of the validity of the axioms of $ \mathsf{ZF} $ and $ \neg \mathsf{CH} $ in the model $ M[A] $ is based upon this proposition. The verification of $ \neg \mathsf{CH} $ in $ M[A] $ also involves the use of special properties of the set of forcing conditions, which makes it possible to show that:

  1. If the ordinal numbers $ \delta_{1},\delta_{2} < \lambda $ are unequal, then one has $$ (\forall p)(\exists q \geq p)(\exists n < \omega_{0})(q(\langle \delta_{1},n \rangle) \neq q(\langle \delta_{2},n \rangle)), $$ that is, $$ A_{\delta_{1}} \neq A_{\delta_{2}}, \qquad \text{where } A_{\delta} \stackrel{\text{df}}{=} \{ n < \omega_{0} \mid \langle \delta,n \rangle \in A \}. $$
  2. $ M[A] \models (\lambda \text{ is the second uncountable ordinal}) $.

There is the following relation between forcing and Boolean-valued models: If one introduces the notation \begin{gather} \| \phi \| \stackrel{\text{df}}{=} \{ p \in \mathbb{P} \mid p \Vdash \neg \neg \phi \}, \\ \mathbb{B} \stackrel{\text{df}}{=} \{ X \subseteq \mathbb{P} \mid (\forall p)((p \in X) \iff (\forall q \geq p)(\exists r \geq q)(r \in X)) \}, \end{gather} then $ (\mathbb{B},\subseteq) $ is a complete Boolean algebra, and $ \| \phi \| \in \mathbb{B} $ is the Boolean value of the formula $ \phi $. Hence, to specify a partially ordered set $ (\mathbb{P},\leq) $ and to define the relation $ p \Vdash \neg \neg \phi $ is equivalent to constructing some Boolean-valued model $ \mathfrak{M} $. The analysis of the proof of theorems of the type $$ M[A] \models \phi_{0}, $$ where $ \phi_{0} $ is an axiom of $ \mathsf{ZF} $ or $ \neg \mathsf{CH} $, leads to the conclusion that the formulas of $ \mathsf{ZF} $ expressing the theorem $$ (\forall p)(p \Vdash \neg \neg \phi_{0}), $$ i.e., $ \| \phi_{0} \| = 1_{\mathbb{B}} $, are deducible from the axioms of $ \mathsf{ZF} $. Therefore, $ \mathfrak{M} $ is a Boolean-valued model for $ \mathsf{ZF} + \neg \mathsf{CH} $, constructed solely with the tools of $ \mathsf{ZF} $. The assumption of countability of a transitive set that is a model of $ \mathsf{ZF} $ and the concept of a generic set are both inessential in the relative consistency proof.

It has been shown that the construction of the Boolean-valued model may be simplified ([2], [3], [5]). In particular, the introduction of the ramified language $ \mathcal{L} $ is not necessary. A generic model $ M[A] $ may also be constructed as follows ([4]):

A subset $ X $ of a partially ordered set $ (\mathbb{P},\leq) $ is called dense if $$ (\forall p)(\exists q \geq p)(q \in X). $$ Let $ \mathbb{P} $ and the relation $ \leq $ be elements of some denumerable transitive set $ M $ that is a model of $ \mathsf{ZF} $. A subset $ G \subseteq \mathbb{P} $ is called an $ M $-generic filter if

  1. $ ((p \in G) \land (q \leq p)) \Rightarrow (q \in G) $;
  2. $ ((p \in G) \land (q \in G)) \Rightarrow (\exists r \in G)((p \leq r) \land (q \leq r)) $;
  3. $ ((X \in M) \land (X \text{ is dense in } \mathbb{P})) \Rightarrow X \cap G \neq \varnothing $.

Let $ G $ be an $ M $-generic filter in $ \mathbb{P} $. As $ M $ is denumerable, $ G $ exists. In general, $ G \notin M $. A relation $ \in_{G} $ is then defined by the equivalence $$ x \in_{G} y \iff (\exists p \in G)(\langle x,p \rangle \in y), $$ where $ x $ and $ y $ are arbitrary elements of the model $ M $.

Let a function $ F_{G} $ be defined on $ M $ by the equations $$ {F_{G}}(y) \stackrel{\text{df}}{=} \{ {F_{G}}(x) \mid x \in_{G} y \}, $$ and let $$ N_{G} \stackrel{\text{df}}{=} \{ {F_{G}}(x) \mid x \in M \}. $$ If $ \phi $ is a closed formula of the language $ \mathsf{ZF} $, supplemented by constants to denote each set from $ M $, then one defines $$ p \Vdash \phi \iff (\forall G \ni p)(G \text{ is an } M\text{-generic filter} \Rightarrow N_{G} \models \phi). $$ It can be now shown that:

(I) $ N_{G} \models \phi \iff (\exists p \in G)(p \Vdash \phi) $.

(II) The relation $ p \Vdash \phi(c_{1},\ldots,c_{n}) $ can be defined in the model $ M $ for each formula $ \phi $.

By using solely (I) and (II), and basing oneself on the fact that $ M $ is a model of $ \mathsf{ZF} $, it is possible to establish that $ N_{G} $ is a model of $ \mathsf{ZF} $. If $ \mathbb{P} $ is defined by the equivalences (a) and (b) given much earlier on, then one has $ N_{G} \models \neg \mathsf{CH} $, that $ \displaystyle \bigcup G $ is the characteristic function of some set $ A \subseteq \lambda \times \omega_{0} $, and $ M[A] = N_{G} $. The relation $ p \Vdash \phi $, which is definable in $ M $, does not satisfy points (3) and (5) of Cohen’s definition of the forcing relation. One has instead $$ (p \Vdash (\exists x) \phi(x)) \iff (\forall p' \geq p)(\exists p'' \geq p')(\exists a \in M)(p'' \Vdash \phi(a)). $$ If it is assumed that $$ \| \phi \| \stackrel{\text{df}}{=} \{ p \in \mathbb{P} \mid p \Vdash \phi \}, $$ then a Boolean-valued model for $ \mathsf{ZF} + \neg \mathsf{CH} $ is obtained that is definable in $ M $ and has a Boolean algebra $ \mathbb{B} $ that is identical with that of Cohen.

Therefore, the forcing method consists, in fact, of constructing a $ \mathbb{B} $-valued model and a homomorphism, which preserves certain infinite unions and intersections of the algebra $ \mathbb{B} $, into the two-element algebra $ \{ 0,1 \} $. For applications of the forcing method in set theory see, for example, [2].

References

[1] P.J. Cohen, “Set theory and the continuum hypothesis”, Benjamin (1966).
[2] T.J. Jech, “Lectures in set theory: with particular emphasis on the method of forcing”, Lect. notes in math., 217, Springer (1971).
[3] G. Takeuti, W.M. Zaring, “Axiomatic set theory”, Springer (1973).
[4] J.R. Shoenfield, “Mathematical logic”, Addison-Wesley (1967).
[5] Yu.I. Manin, “The problem of the continuum”, J. Soviet Math., 5: 4 (1976), pp. 451–502; Itogi Nauk. i Tekhn. Sovrem. Problemy, 5 (1975), pp. 5–73.
[6] M.C. Fitting, “Intuitionistic logic, model theory and forcing”, North-Holland (1969).

Comments

For a modern elementary introduction with applications, see [a1]. A quicker, though incomplete, account is [a3]. [a2] presents the Boolean-valued approach mentioned above.

References

[a1] K. Kunen, “Set theory, an introduction to independence proofs”, North-Holland (1980).
[a2] J.L. Bell, “Boolean-valued models and independence proofs in set theory”, Oxford Univ. Press (1977).
[a3] J.P. Burgess, “Forcing”, J. Barwise (ed.), Handbook of mathematical logic, North-Holland (1977), pp. 403–452.
[a4] T.J. Jech, “Set theory”, Acad. Press (1978), pp. 523ff. (Translated from German)
How to Cite This Entry:
Forcing method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Forcing_method&oldid=51543
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article