What are some simple example of "forcing" in set theory?

Question

Can someone illustrate the idea of "forcing" in set theory through some simple examples? The article on forcing on wikipedia goes straight to axiom of choice and continuum hypothesis, I wonder if there are simpler application that illustrates this so called technique.

Answer 1

Let $\mathcal{M}$ be a countable transitive model of ZFC.

Suppose we want to add to $\mathcal{M}$ a function from $\mathbb{N}$ into $\{0,1\}$. Let $\mathbb{P} := (P, \leq_\mathbb{P})$ be the poset where $P$ is the collection of all finite partial functions and $\leq_\mathbb{P}$ is the extension of functions (i.e $f \leq_\mathbb{p}$ if and only if $f \subseteq g$ when regarding $f$ and $g$ as sets of ordered pairs).

Note that two functions in $\mathbb{P}$ have a common extension in $\mathbb{P}$ if they are compatible as functions (i.e. if they agree on their common domain).

Let $G$ be a generic ideal of $\mathbb{P}$. That is to say $G$ is a collection of finite partial functions from $\mathbb{N}$ to $\{0,1\}$ such that an two elements of $G$ are compatible. That means that taking the union of all the functions that are in $G$ produce a single function $\widetilde{f}$ from a subset of $\mathbb{N}$ into $\{0,1\}$.

Using the fact that $G$ is generic (i.e $G$ intersects every dense set in $\mathcal{M}$) can you see why $G$ the domain of the function $\widetilde{f}$ must be all of $\mathbb{N}$ ? Hint : try to find appropriate dense subsets of $\mathcal{M}$.

Even though $\mathcal{M}$ already contains many functions from $\mathcal{N}$ into $\{0,1\}$, we claim that $\widetilde{f}$ cannot be in $\mathcal{M}$ (i.e. we used $G$ to obtain a function from $\mathcal{N}$ into $\{0,1\}$ that does not exists in $\mathcal{M}$).

To see this, consider any function $h : \mathbb{N} \rightarrow \{0,1\}$ that lies in $\mathcal{M}$ and consider $D_h$ the dense subset of $\mathcal{M}$ containing all finite partial functions which disagree with $h$ at some point. The generic ideal $G$ must intersect $D_h$ since it is dense, but that means that $\widetilde{f}$ cannot equal $h$.

Answer 2

An easy example is the cardinal collapse. I will show that there is a forcing extension in which a given cardinal becomes countable by adding in a new bijection. To keep the examples simple one will avoid all other properties that the extension may have and mention ontological concerns at the end.

Let $M$ be a countable transitive set which models some amount of the set theory axiom (depending on what you want to do).

Let $\kappa$ be an uncountable cardinal of $M$, i.e. $M$ has no bijection between $\omega$ and $\kappa$. In $M$, define the set of all partial functions from $\omega$ to $\kappa$ with finite domain. Call this set $\text{Coll}(\omega, \kappa)$. $p, q \in \text{Coll}(\omega, \kappa)$ is ordered by $p \leq q$ if and only if $p$ is an extension of $q$ as function. With this ordering $\text{Coll}(\omega, \kappa)$ is a forcing poset.

In the our world, there is a $G \subseteq \text{Coll}(\omega, \kappa)$ whic is a generic filter meaning

(1) $G$ is upward closed: if $p \leq q$ and $p \in G$, then $q \in G$.

(2) All elements of $G$ are compatible: $p, q \in G$ implies there exists $t \in G$ with $t \leq p$ and $t \leq q$.

(3) If $D \subset \text{Coll}(\omega, \kappa)$ is dense (i.e. for all $p \in \text{Coll}(\omega, \kappa)$ and $D \in M$, there exists a $q \in D$ such that $q \leq p$), then $D \cap G \neq \emptyset$.

Now condition (2) implies that if $p, q$ are partial functions, then $p \cup q$ is still a partial function. Thus given such a $G$, define $$f_G = \bigcup_{p \in G} p$$ $f_G$ is a (possible partial) function from $\omega$ to $\kappa$.

Now if $f_G$ was a total surjective function, then in any model of set theory extending $M$ and containing $G$, $\kappa$ would be countable as $f_G$ is the bijection witnessing this.

Consider for each $n \in \omega$ $$E_n = \{p \in \text{Coll}(\omega, \kappa) : n \in \text{dom}(p)\}$$ You can show $E_n$ is dense. So by the fact that $G$ is generic, one has that there is a $p \in G \cap E_n$. Since $p \subseteq f_G$, one knows that $n \in \text{dom}(f_G)$. Since $G \cap E_n$ for all $n$, $f_G$ is a total function.

Consider for each $\alpha \in \kappa$, $$K_\alpha = \{p \in \text{Coll}(\omega, \kappa) : \alpha \in \text{range}(p)\}$$ Again, $K_\alpha$ is dense. So there is a $p \in G \cap K_\alpha$. Since $p \subseteq f_G$, $\alpha \in \text{range}(f_G)$. Since $G \cap E_\alpha \neq \emptyset$ for all $f_G$ is surjective.

So it has been shown that $f_G$ is a bijection between $\kappa$ and $\omega$. So in any model of set theory extending $M$ with $G$ in it, $\kappa$ would be countable.

There is a standard procedure to produce a smallest transitive model of set theory containing $M$ and $G$. It is called $M[G]$. So in this models, one made an uncountable cardinal of the original models $M$ into a countable set.

---

Now to mention the subtle details.

When I say "some amount of set theory axioms", you can take a finite amount of $\text{ZFC}$ need to do what you want and make the forcing construction go through. For instance, in our example $M$ should have enough axioms to prove $\omega$ exists and $\text{Coll}(\omega, \kappa)$ exists.

What do I mean by "our world": So to be precise, we are living in some model of set theory, which you can call $V$. $M \in V$ is a countable set. $G$ certainly does not exists in $M$ ($\kappa$ would have been countable in $M$). However, why does $G$ exists in our world $V$? In general, it may not exist, but since $M$ is countable from our point of view (in $V$), it is a very easy construction to make a $G$ meet the countably many dense sets in $M$.

Finally, the construction of the model $M[G]$ is the technical part of forcing. However, the construction of $M[G]$ is rarely importantly in forcing arguments. The main ideas of forcing proofs are the combinatorics involving the the dense sets. The construction generally comes up when proving abstract forcing theorems. It is something one should avoid being distracted on when first learning forcing.

---

Some other interesting examples which are generally useful in descriptive set theory:

Cohen forcing as described by the other answer is useful since it can add a element which is not in any ground model meager sets. Random forcing adds an element which is not in any ground model null set. Sacks forcing adds an element which is not in any ground models countable sets of reals.