The Lumenary · First-year graduate

Forcing and independence

Name: ______________________

Date: ______________________

You will learn to

Explain what it means for a statement to be independent of ZFC, and why independence proofs are relative consistency proofs
Define forcing posets, dense sets, generic filters and names, and describe the generic extension $M[G]$ of a countable transitive model $M$
Prove that Cohen forcing adds a new real and is ccc, and outline why $M[G] \models \mathsf{ZFC} + \neg\mathsf{CH}$ for $\mathrm{Add}(\omega, \aleph_2)$
State Easton's theorem and other independence results obtained by forcing, such as the consistency of Suslin's hypothesis
Compare the countable-transitive-model, Boolean-valued and sheaf presentations of forcing

1.
In Cohen forcing $\mathrm{Fn}(\omega, 2)$ (finite partial functions, stronger = larger), which of these sets are dense? Choose all that apply.
- A. $\{p : 5 \in \operatorname{dom} p\}$
- B. $\{p : p(n) = 1 \text{ for some even } n \in \operatorname{dom} p\}$
- C. $\{p : p(0) = 1\}$
- D. $\{p : |\operatorname{dom} p| \le 3\}$
2.
How many conditions does $\mathrm{Fn}(3, 2)$ have, i.e. how many partial functions from $\{0, 1, 2\}$ to $\{0, 1\}$ are there (including the empty function $\mathbb 1$ )?
3.
Why does the classical presentation of forcing start from a countable transitive model $M$ ?
- A.So that $M$ has only countably many dense sets, and the Rasiowa–Sikorski lemma gives an $M$ -generic filter.
- B.So that $M$ contains only countably many reals, making CH false in $M$ .
- C.Because only countable models satisfy the countable chain condition.
- D.Because ZFC proves that a countable transitive model of ZFC exists.
4.
In the proof that an $M$ -generic filter $G$ (for a forcing in which every condition has two incompatible extensions) is not in $M$ , which dense set does $G$ fail to meet if $G \in M$ ?
- A. $P \setminus G$
- B. $G$ itself
- C. $\{p : n \in \operatorname{dom} p\}$
- D. $\varnothing$
5.
The proof that $\mathrm{Fn}(I, 2)$ has the countable chain condition takes uncountably many conditions $p_\xi$ . What is the key step?
- A.Apply the Δ-system lemma to their domains, then use that only finitely many functions exist on the finite root.
- B.Apply the Rasiowa–Sikorski lemma.
- C.Note that $\mathrm{Fn}(I, 2)$ is countable.
- D.Use König's theorem.
6.
Assuming ZFC is consistent, which of these statements are independent of ZFC? Choose all that apply.
- A.The continuum hypothesis
- B.Suslin's hypothesis
- C.Every Whitehead group is free
- D. $2^{\aleph_0} \neq \aleph_\omega$
- E.Every set of reals is Lebesgue measurable
7.
The Lean file orders Cohen conditions by extension: p ≤ q means q extends p. In this order, what does Mathlib's Order.Ideal Cohen correspond to in forcing?
- A.A filter of conditions (closed under weakening, any two members have a common extension in it)
- B.A dense set
- C.A maximal antichain
- D.A name
8.
The theorem no_filter_meets_every_dense (G : Order.Ideal Cohen) : ∃ D : Set Cohen, IsCofinal D ∧ ∀ p ∈ D, p ∉ G is proved with which witness D?
- A.(G : Set Cohen)ᶜ, the complement of G
- B.Set.univ
- C.avoids x for some real x
- D.decides 0
9.
Write escape(reals, n): given a list of reals (functions from naturals to $\{0, 1\}$ ) and $n$ , return a tuple of bits $p$ of length at least $n$ that disagrees with every listed real at some position. This is the Rasiowa–Sikorski construction for the dense sets 'decide bit $k$ ' ( $k \lt n$ ) and 'disagree with $x$ '.
Computational — Practice

Answer key — Forcing and independence

1.
The first two are dense: any condition can be extended to decide $5$ , or to take the value $1$ at a fresh even number. The other two are not: a condition with $p(0) = 0$ , or with four points in its domain, cannot be extended into them.
2.
Each point has three options (undefined, $0$ , $1$ ), so there are $3^3 = 27$ conditions. A finite forcing like this is trivial: every generic filter is principal.
3.
Genericity asks $G$ to meet every dense set in $M$ . If $M$ is countable there are only countably many, and the Rasiowa–Sikorski construction meets them all. No filter meets every dense set in $V$ , so one cannot force over $V$ this way (Boolean-valued models are the alternative).
4.
If $G \in M$ , the complement $D = P \setminus G$ is in $M$ . It is dense: any $p$ has incompatible extensions $q, r$ , not both in the filter $G$ , so one lies in $D$ . Since $G \cap D = \varnothing$ , $G$ is not $M$ -generic — contradiction.
5.
By the Δ-system lemma, uncountably many domains pairwise intersect in a common finite root $R$ ; since there are only $2^{|R|}$ functions $R \to 2$ , uncountably many of these conditions agree on $R$ , and any two of them are compatible. So there is no uncountable antichain.
6.
CH, Suslin's hypothesis and the freeness of Whitehead groups are independent. $2^{\aleph_0} \neq \aleph_\omega$ is a theorem of ZFC, and 'every set of reals is measurable' is refutable in ZFC (though consistent with ZF + DC, given an inaccessible).
7.
In the extension order, an Order.Ideal is a non-empty set closed under weakening in which any two members have a common extension inside: exactly a filter of forcing (whose usual order is the reverse). Order.Cofinal sets are the dense sets.
8.
The witness is the complement of G. It is dense: for any p, the two one-bit extensions are incompatible, so a filter contains at most one of them. And G trivially misses its complement. This is why forcing works over a countable model, whose dense sets do not include such complements.
9.
```
def escape(reals, n):
    p = ()
    for x in reals:
        if all(p[i] == x(i) for i in range(len(p))):
            p = p + (1 - x(len(p)),)
    while len(p) < n:
        p = p + (0,)
    return p
```
Each step extends the current condition into the next dense set, exactly as in the proof of the Rasiowa–Sikorski lemma. Disagreements are never undone, because later steps only extend $p$ . Over a countable model the same construction runs through all its dense sets.