Forcing

From Cantor's Attic
Jump to: navigation, search

Forcing is a method for extending a transitive model $M$ of $\text{ZFC}$ (the ground model) by adjoining a new set $G$ (the generic set) to produce a new, larger model $M[G]$ called a generic extension. In short, the set $G$ can be constructed a certain way using a partially ordered set $(\mathbb{P},\leq)\in M$ (the forcing notion) so that the following holds:

  • (Generic Model Theorem). There exists a unique transitive model $M[G]$ of $\text{ZFC}$ that includes $M$ (as a subset) and contains $G$ (as an element), has the same ordinals as $M$, and any transitive model of $\text{ZFC}$ also including $M$ and containing $G$ includes $M[G]$ (i.e. $M[G]$ is minimal).

The elements of the forcing notion $\mathbb{P}$ will be called the conditions. The order $p\leq q$, for $p,q\in\mathbb{P}$, is to be interpreted as "$p$ is stronger than $q$" or as "$p$ implies $q$". $G$ will be a special subset of $\mathbb{P}$ said to be generic over $M$ and satisfying some requirements. The choice of $\mathbb{P}$ and of $\leq$ will determine what is true of false in $M[G]$.

Forcing was first introduced by Paul Cohen as a way of proving the consistency of the failure of the continuum hypothesis with $\text{ZFC}$. He also used it to prove the consistency of the failure of the axiom of choice, albeit the proof is more indirect: if $M$ satisfies choice, then so does $M[G]$, so $\neg AC$ cannot be forced directly, though it is possible to extract a submodel of $M[G]$ (for a particular generic extension) in which choice fails.

Definitions and some properties

Let $(\mathbb{P},\leq)$ be a partially ordered set, the forcing notion. Sometimes $\leq$ can just be a preorder (i.e. not necessarily antisymmetric). The elements of $\mathbb{P}$ are called conditions. We will assume $\mathbb{P}$ has a maximal element $1$, i.e. one has $p\leq 1$ for all $p\in\mathbb{P}$. This element isn't necessary if one uses the definition using Boolean algebras presented below, but is useful when trying to construct $M[G]$ without using Boolean algebras.

Two conditions $p,q\in P$ are compatible if there exists $r\in\mathbb{P}$ such that $r\leq p$ and $r\leq q$. They are incompatible otherwise. A set $W\subseteq\mathbb{P}$ is an antichain if all its elements are pairwise incompatible.

Genericity

A nonempty set $F\subseteq\mathbb{P}$ is a filter on $\mathbb{P}$ if all of its elements are pairwise compatible and it is closed under implications, i.e. if $p\leq q$ and $p\in F$ then $q\in F$.

One says that a set $D\subseteq\mathbb{P}$ is dense if for all $p\in\mathbb{P}$, there is $q\in D$ such that $q\leq p$ (i.e. $q$ implies $p$). $D$ is open dense if additionally $q\leq p$ and $p\in D$ implies $q\in D$. $D$ is predense if every $p\in\mathbb{P}$ is compatible with some $q\in D$.

Given a collection $\mathcal{D}$ of dense subsets of $\mathbb{P}$, one says that a filter $G$ is $\mathcal{D}$-generic if it intersects all sets $D\in\mathcal{D}$, i.e. $D\cap G\neq\empty$.

Given a transitive model $M$ of $\text{ZFC}$ such that $(\mathbb{P},<)\in M$, we say that a filter $G\subseteq\mathbb{P}$ is $M$-generic (or $\mathbb{P}$-generic in $M$, or just generic) if it is $\mathcal{D}_M$-generic where $\mathcal{D}_M$ is the set of all dense subsets of $\mathbb{P}$ in $M$.

In the above definitions, dense can be replaced with open dense, predence or a maximal antichain, and the resulting notion of genericity would be the same.

In most cases, if $G$ is $\mathbb{P}$-generic over $M$ then $G\not\in M$. The Generic Model Theorem mentioned above says that there is a minimal model $M[G]\supseteq M$ with $M[G]\models\text{ZFC}$, $G\in M[G]$, and if $M\models$ "$x$ is an ordinal" then so does $M[G]$.

$\mathbb{P}$-names and interpretation by $G$

Using transfinite recursion, define the following cumulative hierarchy:

  • $V^\mathbb{P}_0=\empty$, $V^\mathbb{P}_\lambda = \bigcup_{\alpha<\lambda}V^\mathbb{P}_\alpha$ for limit $\lambda$
  • $V^\mathbb{P}_{\alpha+1} = \mathcal{P}(V^\mathbb{P}_\alpha\times\mathbb{P})$
  • $V^\mathbb{P} = \bigcup_{\alpha\in\mathrm{Ord}}V^\mathbb{P}_\alpha$

Elements of $V^\mathbb{P}$ are called $\mathbb{P}$-names. Every nonempty $\mathbb{P}$-name is of a set of pairs $(n,p)$ where $n$ is another $\mathbb{P}$-name and $p\in\mathbb{P}$.

Given a filter $G\subseteq\mathbb{P}$, define the interpretation of $\mathbb{P}$-names by $G$: Given a $\mathbb{P}$-name $x$, let $x^G=\{y^G : ((\exists p\in G)(y,p)\in x)\}$. Letting $\breve{x}=\{(\breve{y},1):y\in x\}$ for every set $x$ be the canonical name for $x$, one has $\breve{x}^G=x$ for all $x$.

Let $M$ be a transitive model of $\text{ZFC}$ such that $(\mathbb{P},\leq)\subseteq M$. Let $M^\mathbb{P}$ be the $V^\mathbb{P}$ constructed in $M$. Given a $M$-generic filter $G\subseteq\mathbb{P}$, we can now define the generic extension $M[G]$ to be $\{x^G : x\in M^\mathbb{P}\}$. This $M[G]$ satisfies the Generic Model Theorem.

The forcing relation

Define the forcing language to be the first-order language of set theory augmented by a constant symbol for every $\mathbb{P}$-name in $M^\mathbb{P}$. Given a condition $p\in\mathbb{P}$, a formula $\varphi(x_1,...,x_n)$ and $x_1,...,x_n \in M^\mathbb{P}$. We say that $p$ forces $\varphi(x_1,...,x_n)$, denoted $p\Vdash_ {M,\mathbb{P}}\varphi(x_1,...,x_n)$ if there is a $M$-generic filter $G$ with $p\in G$ such that $M[G]\models\varphi(x_1^G,...,x_n^G)$. There exists an "internal" definition of $\Vdash$, i.e. a definition formalizable in $M$ itself, by induction on the complexity of the formulas of the forcing language.

The Forcing Theorem asserts that if any $M$-generic $G\ni p$ is such that $M[G]\models\varphi(x_1^G,...,x_n^G)$ (i.e. if $p\Vdash_{M,\mathbb{P}}\varphi(x_1,...,x_n)$) then all $M$-generic filters also produces a model satisfying $\varphi(x_1^G,...,x_n^G)$.

The forcing relation has the following properties, for all $p,q\in\mathbb{P}$ and formulas $\varphi,\psi$ of the forcing language:

  • $p\Vdash\varphi\land q\leq p\implies q\Vdash\varphi$
  • $p\Vdash\varphi\implies\neg(p\Vdash\neg\varphi)$
  • $p\Vdash\neg\varphi\iff\neg\exists q\leq p(q\Vdash\varphi)$
  • $p\Vdash(\varphi\land\psi)\iff(p\Vdash\varphi\land p\Vdash\psi)$
  • $p\Vdash\forall x\varphi\iff\forall x\in M^\mathbb{P}(p\Vdash\varphi(x)$
  • $p\Vdash(\varphi\lor\psi)\iff\forall q\leq p\exists r\leq q(r\Vdash\varphi\lor r\Vdash\psi)$
  • $p\Vdash\exists x\varphi\iff\forall q\leq p\exists r\leq q\exists x\in M^\mathbb{R}(r\Vdash\varphi(x))$
  • $p\Vdash\exists x\varphi\implies\exists x\in M^\mathbb{P}(p\Vdash\varphi(x))$
  • $\forall p\exists q\leq p (q\Vdash\varphi\lor q\Vdash\neg\varphi)$

Separativity

A forcing notion $(\mathbb{P},\leq)$ is separative if for all $p,q\in\mathbb{P}$, if $p\not\leq q$ then there exists a $r\leq p$ incompatible with $q$. Many notions aren't separative, for example if $\leq$ is a linear order than $(\mathbb{P},\leq)$ is separative iff $\mathbb{P}$ has only one element. However, every notion $(\mathbb{P},\leq)$ has a unique (up to isomorphism) separative quotient $(\mathbb{Q},\preceq)$, i.e. a notion $(\mathbb{Q},\preceq)$ and a function $i:\mathbb{P}\to\mathbb{Q}$ such that $x\leq y\implies i(x)\preceq i(y)$ and $x, y$ are compatible iff $i(x),i(y)$ are compatible. This name comes from the fact that $\mathbb{Q}=(\mathbb{P}/\equiv)$ where $x\equiv y$ iff every $z\in P$ is compatible with $x$ iff it is compatible with $y$. The order $\preceq$ on the equivalence classes is "$[x]\preceq[y]$ iff all $z\leq x$ are compatible with $y$". Also $i(x)=[x]$. It is sometimes convenient to identify a forcing notion with its separative quotient.

Boolean algebras

Consistency proofs

Chain conditions, distributivity, closure and property (K)

A forcing notion $(\mathbb{P},\leq)$ satisfies the $\kappa$-chain condition ($\kappa$-c.c.) if every antichain of elements of $\mathbb{P}$ has cardinality less than $\kappa$. The $\aleph_1$-c.c. is called the countable chain condition (c.c.c.). An important feature of chain conditions is that if $(\mathbb{P},\leq)$ satisfies the $\kappa$-c.c. then if $\kappa$ is regular in $M$ then it will be regular in $M[G]$. Since the $\kappa$-c.c. implies the $\lambda$-c.c. for all $\lambda\geq\kappa$, it follows that the $\kappa$-c.c. implies all regular cardinals $\geq|\mathbb{P}|^+$ will be preserved, and in particular the c.c.c. implies all cardinals and cofinalities of $M$ will be preserved in $M[G]$ for all $M$-generic $G\subseteq\mathbb{P}$.

$(\mathbb{P},\leq)$ is $\kappa$-distributive if the intersection of $\kappa$ open dense sets is still open dense. $\kappa$-distributive notions for infinite $\kappa$ does not add new subsets to $\kappa$. A stronger property, closure, is defined the following way: $\mathbb{P}$ is $\kappa$-closed if every $\lambda\leq\kappa$, every descending sequence $p_0\geq p_1\geq...\geq p_\alpha\geq... (\alpha<\lambda)$ has a lower bound. Every $\kappa$-closed notion is $\kappa$-distributive.

$(\mathbb{P},\leq)$ has property (K) (K for Knaster) if every uncountable set of conditions has an uncountable subet of pairwise compatible elements. Every notion with property (K) satisfy the c.c.c.

The Lévy collapse

Example: independence of the continuum hypothesis

Other examples of consistency results proved using forcing

In the following examples, the generated generic extensions satisfy the axiom of choice unless indicated otherwise.

  • Easton's theorem: Let $M$ be a transitive set model of $\text{ZFC+GCH}$. Let $F$ be an increasing function in $M$ from the set of $M$'s regular cardinals to the set of $M$'s cardinals, such that for all regular $\kappa$, $\mathrm{cf}F(\kappa)>\kappa$. Then there is a generic extension $M[G]$ of $M$ with the same cardinals and cofinalities such that $M[G]\models\text{ZFC+}\forall\kappa($if $\kappa$ is regular then $2^\kappa=F(\kappa)$).
  • Violating the Singular Cardinal Hypothesis at $\aleph_\omega$: Assume there is a measurable cardinal of Mitchell order $o(\kappa)=\kappa^{++}$. Then there is a generic extension in which $\kappa=\aleph_\omega$ and $2^{\aleph_\omega}=\aleph_{\omega+2}$. The hypothesis used here is optimal: in term of consistency strength, no less than a measurable of order $\kappa^{++}$ can produce a model where $\text{SCH}$ fails.
  • Violating the Singular Cardinal Hypothesis everywhere: Assume there is a strong cardinal. Then there is a generic extension in which $2^\kappa=\kappa^+$ for every successor $\kappa$ but $2^\kappa=\kappa^{++}$ for every limit cardinal $\kappa$.
  • Violating the Generalized Continuum Hypothesis everywhere: Assume there exists a supercompact cardinal. Then there is a generic extension in which $2^\kappa=\kappa^{++}$ for every $\kappa$, i.e. $\text{GCH}$ fails everywhere.
  • Large cardinal properties of $\aleph_1$: Let $\kappa$ be measurable/supercompact/huge. Then there is a generic extension satisfying $\text{ZF(+}\neg\text{AC)}$ in which $\kappa=\aleph_1$ and $\aleph_1$ is measurable/supercompact/huge (by the ultrafilter characterizations, not by the elementary embedding characterizations.)
  • Singularity of every uncountable cardinal: Assume there is a proper class of strongly compact cardinals. Then there is a generic extension in which (the axiom of choice does not hold and) every uncountable cardinal is singular and has cofinality $\aleph_0$. This also implies that the axiom of determinacy holds in the $L(\mathbb{R})$ of some forcing extension of $\text{HOD}$.
  • Regularity properties of all sets of reals: Assume there is an inaccessible cardinal. Then there is a generic extension satisfies $\text{ZF+DC+}\neg\text{AC}$ and in which every set of reals is Lebesgue measurable, has the Baire property and the perfect subset property. There is also a generic extension in which choice holds and every projective set of reals has those properties.
  • Real-valued measurability of the continuum: Assume there is a measurable cardinal. Then there is a generic extension in which $\kappa=2^{\aleph_0}$ and $2^{\aleph_0}$ is real-valued measurable (and thus weakly inaccessible, weakly hyper-Mahlo, etc.)
  • Precipitousness of the nonstationary ideal on $\omega_1$: Assume there is a measurable cardinal $\kappa$. Then there is a generic extension in which $\kappa=\aleph_1$ and the nonstationary ideal on $\omega_1$ is precipitous.
  • Saturation of the nonstationary ideal on $\omega_1$: Assume there is a Woodin cardinal $\kappa$. Then there is a generic extension in which $\kappa=\aleph_2$ the nonstationary ideal on $\omega_1$ is $\aleph_2$-saturated.
  • Saturation of an ideal on the continuum: Let $\kappa$ be a measurable cardinal. Then there is a generic extension in which $\kappa=2^{\aleph_0}$, there is a $2^{\aleph_0}$-saturated $2^{\aleph_0}$-complete ideal on $2^{\aleph_0}$ and there isn't any $\lambda$-saturated $2^{\aleph_0}$-complete ideal on $2^{\aleph_0}$ for every infinite $\lambda<2^{\aleph_0}$.

Some other applications of forcing:

  • There is a generic extension in which there is a cardinal $\kappa$ such that $2^{\mathrm{cf}(\kappa)}<\kappa<\kappa^+<\kappa^{\mathrm{cf}(\kappa)}<2^\kappa$.
  • Assume there is an inaccessible cardinal. Then there is a generic extension in which there are no Kurepa trees.
  • Let $\kappa$ be a superstrong cardinal. Let $V[G]$ be the generic extension of $V$ by the Lévy collapse $\mathrm{Col}(\aleph_0,<\kappa)$. Then there is a nontrivial elementary embedding $j:L(\mathbb{R})\to(L(\mathbb{R}))^{V[G]}$.
  • Let $\kappa$ be a superstrong cardinal. There exists a $\omega$-distributive $\kappa$-c.c. notion of forcing $(\mathbb{P},\leq)$ such that in $V^\mathbb{P}$, $\kappa=\aleph_2$ and there exists a normal $\aleph_2$-saturated $\sigma$-complete ideal on $\omega_1$.
  • Let $\kappa$ be a weakly compact cardinal. Then there is a generic extension in which $\kappa=\aleph_2$ and $\aleph_2$ has the tree property. In fact, if there is infinitely many weakly compact cardinals then in a generic extension $\aleph_{2n}$ has the tree property for every $n$. [1]
  • Assume there are infinitely many supercompact cardinals. Then there is a generic extension in which there exists infinitely many cardinals $\delta$ above $2^{\aleph_0}$ such that both $\delta$ and $\delta^+$ have the tree property. Also, the axiom of projective determinacy holds in that generic extension.
  • Let $\kappa$ be a measurable cardinal. Then there is a generic extension in which $\kappa$ remains weakly compact, there is a $\kappa^+$-saturated $\kappa$-complete ideal on $\kappa$ but there isn't any $\kappa$-saturated $\kappa$-complete ideal on $\kappa$. One can replace "$\kappa$ is weakly compact" by "$\kappa$ is weakly inaccessible and $\kappa=2^{\aleph_0}$".

Product forcing

Iterated forcing

Forcing axioms

Martin's axiom ($\text{MA}$) is the following assertion: If $(\mathbb{P},\leq)$ is a forcing notion that satisfies the countable chain condition and if $\mathcal{D}$ is a collection of fewer than $2^{\aleph_0}$ dense subsets of $\mathbb{P}$, then there exists a $\mathcal{D}$-generic filter on $\mathbb{P}$. By replacing "fewer than $2^{\aleph_0}$" by "at most $\kappa$" on obtain the axiom $\text{MA}_\kappa$. Martin's axiom is then $\text{MA}_{<2^{\aleph_0}}$. Note that $\text{MA}_{\aleph_0}$ is provably true in $\text{ZFC}$.

For all $\kappa$, $\text{MA}_\kappa$ implies $\kappa<2^{\aleph_0}$. Martin's axiom follows from the continuum hypothesis, but is also consistent with the continuum hypothesis. $\text{MA}_{\aleph_1}$ implies there are no Suslin trees, that every Aronszajn tree is special, and that the c.c.c. is equivalent to property (K).

Martin's axiom implies that $2^{\aleph_0}$ is regular, that it is not real-valued measurable, and also that $2^\lambda=2^{\aleph_0}$ for all $\lambda<2^{\aleph_0}$. It implies that the intersection of fewer than $2^{\aleph_0}$ dense open sets is dense, the union of fewer than $2^{\aleph_0}$ null sets is null, and the union of fewer than $2^{\aleph_0}$ meager sets is meager. Also, the Lebesgue measure is $2^{\aleph_0}$-additive. If additionally $\neg\text{CH}$ then every $\mathbf{\Sigma}^1_2$ set is Lebesgue measurable and has the Baire property.

A forcing notion $(\mathbb{P},\leq)$ satisfies Axiom A if there is a sequence of partial orderings $\{\leq_n:n<\omega\}$ of $\mathbb{P}$ such that $p\leq_0 q$ implies $p\leq q$, for all n $p\leq_{n+1} q$ implies $p\leq_n q$, and the following conditions holds:

  • for every descending sequence $p_0\geq_0 p_1\geq_1...\geq_{n-1}p_n\geq_n...$ there is a $q$ such that $q\leq_n p_n$ for all $n$.
  • for every $p\in\mathbb{P}$, for every $n$ and every ordinal name $\alpha$ there exists $q\leq_n p$ and a countable set $B$ such that $p\Vdash\alpha\in B$.

Every c.c.c. or $\omega$-closed notion satisfies Axiom A.

Proper forcing

We say that a forcing notion $(\mathbb{P},\leq)$ is proper if for every uncountable cardinal $\lambda$, every stationary subset of $[\lambda]^\omega$ remains stationary in every generic extension. Every c.c.c. or $\omega$-closed notion is proper, and so is every notion satisfying Axiom A. Proper forcing does not collapse $\aleph_1$: if $\mathbb{P}$ is proper then every countable set of ordinals in $M[G]$ is a subset of a countable set in $M$.

The Proper Forcing Axiom ($\text{PFA}$) is obtained by replacing "c.c.c." by "proper" in the definition of $\text{MA}_{\aleph_1}$: for every proper forcing notion $(\mathbb{P},\leq)$, if $\mathcal{D}$ is a collection of $\aleph_1$ dense subsets of $\mathbb{P}$, then there is a $\mathcal{D}$-generic filter on $\mathbb{P}$. $\text{PFA}$ implies $2^{\aleph_0}=\aleph_2$ and that the continuum (i.e. $\aleph_2$) has the tree property. It also implies that every two $\aleph_1$-dense sets of reals are isomorphic.

Unlike Martin's axiom, which is equiconsistent with $\text{ZFC}$, the $\text{PFA}$ has very high consistency strength, slightly below that of a supercompact cardinal. If there is a supercompact cardinal then there is a generic extension in which $\text{PFA}$ holds. On the other hand, [2] proves a quasi lower bound on the consistency strength of the $\text{PFA}$, which is at least the existence of a proper class of subcompact cardinals. [3] also shows that all known methods of forcing $\text{PFA}$ requires a strongly compact cardinal, and if one wants the forcing to be proper, a supercompact is required.

$\text{PFA}$ implies the failure of the square principle $\Box_\kappa$ for every uncountable cardinal $\kappa$. It also implies the Open Coloring Axiom: let $X$ be a set of reals, and let $K\subseteq[X]^2$. We say that $K$ is open if the set $\{(x,y):\{x,y\}\in K\}$ is an open set in the space $X\times X$. Then

  • ($\text{OCA}$). For every $X\subseteq\mathbb{R}$, and for any partition $[X]^2=K_0\cup K_1$ with $K_0$ open, either there exists an uncountable $Y\subseteq X$ such that $[Y]^2\subseteq K_0$ or there exists sets $H_n, n<\omega$ such that $X=\bigcup_{n<\omega}H_n$ and $[H_n]^2\subseteq K_1$ for all $n$.

This axiom has many useful implications combinatorial set theory.

The $\text{PFA}^+$ and $\text{PFA}^-$ axioms

Martin's maximum and the semiproper forcing axiom

Other types of forcing

    This article is a stub. Please help us to improve Cantor's Attic by adding information.