145B SET THEORY II: AN INTRODUCTION TO FORCING

ASSAF SHANI

1. Introduction
We assume the axioms ZF, and we call the universe of all sets V . (The axiom
of foundation allows us to present V as the union of Vα for all ordinals α.) We can
then define Godel’s model L of all constructible sets, and prove that L satisfies the
axiom of choice and the continuum hypothesis.
In conclusion, the consistency of the axioms ZF implies the consistency of the
axioms ZFC+CH. In other words, using ZF, we cannot refute the axiom of choice,
nor the continuum hypothesis!
But can we prove them? The answer is no. In the 60’s, Cohen introduced the
method of forcing and used it to show that the axiom of choice cannot be proven
using ZF, and the continuum hypothesis cannot be proven using ZFC.
Combining Godel’s and Cohen’s results, we say that the axiom of choice is in-
dependent of ZF, and that CH is independent of ZFC. Proving this will be one of
our main goals.

1.1. Inner models. How can we prove this? At first, we started with an arbitrary
model V of ZF and constructed an inner model L which satisfies ZFC+CH. Can we
repeat this idea? Perhaps start with an arbitrary model V of ZFC, and construct
some inner model M in which the continuum hypothesis fails.
This approach cannot work. What if the model we started with satisfies V=L.
Then any class inner model of it will be everything. For example, maybe we can
prove, just using ZF, that V=L, that is, that every set is constructible. Using this
inner model approach, we cannot even rule out this option.

1.2. Outer models? Let us take this “worst-case scenario” that V=L. Assume
further that there is a countable ordinal α such that Lα is itself a model of ZFC
(this is not unreasonable to ask for). Lα is a small, countable, set, and there are
many sets outside of it. We hope, perhaps, to create a different model of set theory
by adding to Lα some sets. For example, Lα contains only countably many real
numbers, so there are real numbers outside of Lα that we may try to add.
More specifically, let ω2Lα be whatever ordinal Lα thinks is ω2 . (We are assuming
Lα is a model of ZFC.) Like everything inside Lα , ω2Lα is countable., so we may
actually find “ω2Lα -many” reals and add them to Lα . Perhaps, by adding these
reals to Lα , we can find a model of ZFC having ω2 many reals, and therefore failing
to satisfy the continuum hypothesis!
In some sense, this is precisely what we will do. However, the approach above is
extremely naive, and is pretty far from reality. (Indeed the Continuum Hypothesis,

Date: Fall 2020.

1
2 ASSAF SHANI

#1 in Hilbert’s famous list of problems, was open for a long time.) Roughly speak-
ing, Cohen’s method of forcing allows us to add reals, and other sets, to some given
model of set theory. It turns out however that we need to choose these sets very
carefully for two reasons. One is to ensure that we can construct another model of
set theory, containing the original one and the additional sets. The other is to be
able to analyze the resulting model, for example, to determine whether or not it
satisfies the continuum hypothesis.

2. Axiomatic set theory review

We begin by reviewing some basic set theory. We will take a logic-based and
axiomatic approach, emphasizing questions of definability in set theory. It should
make sense that paying attention to axiomatic issues will be helpful towards proving
independence results. However, the entanglement between logical methods and set
theory is much deeper. Often times a careful analysis of definability and axiomatics
sheds more light on seemingly unrelated questions.

2.1. Formulas. Given a language L (some relation symbols, functions symbols,

and constant symbols,) terms in the language L are defined recursively as
follows. Any variable is a term (e.g. x, y, x1 , x2 ,...); given a function symbol
f (x1 , ..., xn ) from L and terms t1 , ..., tn , then f (t1 , ..., tn ) is a term as well.
For example, in the language of pure set theory, we only have the relation symbol
∈ (and equality =). There are no function symbols, so the terms are only variables.
A formula in the language L is defined recursively as follows. An atomic
formula is of the form R(x1 , ..., xn ), where R is an n-ary relation symbol from L
and x1 , ..., xn are terms. We further construct formulas by logical connectives, for
example, given formulas φ and ψ, then φ ∨ ψ and ¬φ are formulas, and quantifiers,
if φ is a formula then ∀xφ and ∃xφ are formulas.
For example, in set theory the atomic formulas are of the form x = y or x ∈ y.
∀x∃y∃z(y 6= z ∧ x ∈ y ∧ y ∈ z) is a more complex example of a formula (without
free variable). ∀x(x ∈ y ⇐⇒ x ∈ z) is a formula with two free variables, y and z,
which, assuming the axiom of extensionality, is equivalent to the formula y = z.
Remark 2.1. Given a formula φ, in which the variable x does not occur, we may
still consider x as a free variable, a.k.a., a “dummy variable”. That is, we consider
it as a variable, but φ says nothing about it.
Given a language L, a model M for L is a set M together with interpretations
of the symbols in the language. Each constant symbol is interpreted as an element
in M , an n-ary relation symbol is interpreted as a subset of M n , and an n-ary
function symbol is interpreted as a function M n → M . Sometimes M will be a
proper (definable) class rather than a set, and the interpretations will be definable
subsets and functions with class domain.
For example, working with ZF, we construct Vα , and may view it as a model
for the language of set theory by interpreting x ∈ y, for x, y in Vα , according to
the true value of “x ∈ y”. In this case we may say that (Vα , ∈) is a model in the
language of set theory, but we will often drop the ∈ when it is clear. There could
be also models in the language of set theory in which the symbol ∈ is interpreted
in a very different way. For example when taking ultrapowers (we will talk more
about it).
 145B SET THEORY II: AN INTRODUCTION TO FORCING 3

Given a model M, a formula φ(x1 , ..., xn ) with free variables x1 , ..., xn , and
members of a1 , ..., an in M , the satisfaction relation M |= φ is defined inductively
on the construction of formulas, in the logical way. For example, M satisfies ∃xψ(x)
if there exists a ∈ M such that M |= ψ(a).
For example, Vω satisfies all the axioms of ZFC apart for the axiom of infinity.
2.2. Bounded quantification and ∆0 formulas.
Definition 2.2 (Bounded quantifiers). Given a formula φ and variables x, X (pos-
sibly free variables of φ), the following are formulas
(∀x ∈ X)φ(x, X, ...), (∃x ∈ X)φ(x, X, ...)
which formally stand for
∀x(x ∈ X =⇒ φ(x, X, ...)), ∃x(x ∈ X ∧ φ(x, X, ...)).
These are called bounded quantifiers.
Definition 2.3 (∆0 formulas). A formula in the language of set theory is ∆0 if
all the quantifiers appearing in it are bounded. (Formally, we define these recur-
sively, stating that all the atomic formulas are ∆0 , applying any connectives to ∆0
formulas gives ∆0 formulas, and applying bounded quantifiers to ∆0 formulas give
∆0 formulas.)
Example 2.4. • (∃x ∈ X)(∀y ∈ X)(x ∈ y) is a ∆0 formula with one free
variable X;
• (∀x ∈ X)(x ∪ {x} ∈ X) is a ∆0 formula with one free variable X. How to
write it formally?
(∀x ∈ X)(∃y ∈ X)[x ∈ y ∧ (∀z ∈ y)(z = x ∨ z ∈ x)]
Remark 2.5. We care about formulas up to equivalence. For example, the formula
∀x(x = x) is technically not ∆0 , but it is logically equivalent to a tautology, and
we consider it ∆0 .
2.3. Transitive models.
Definition 2.6. Recall that a set X is transitive if for any x ∈ X if y ∈ x then
y ∈ X.
Remark 2.7. The formula φ(X) defined by (∀x ∈ X)(∀y ∈ x)(y ∈ X) is a ∆0
formula such that X is transitive if and only if φ(X) holds.
Theorem 2.8. Suppose X is a transitive set. Consider (X, ∈) as a model in the
language of set theory. Let φ(x1 , ..., xn ) be a ∆0 formula and a1 , ..., an members of
X. Then
(∗) φ(a1 , ..., an ) is true if and only if (X, ∈) |= φ(a1 , ..., an ).
Slogan: “∆0 statements are absolute between transitive models of set theory”.
Proof. The proof is by induction, along the construction sequence of a formula.
First consider atomic formulas. If φ is of the form x ∈ y, then (∗) is true by
definition (we defined the relation ∈ in X to be precisely the real relation ∈).
Similarly, if φ is of the form x = y, (∗) holds.
To deal with logical connectives, suppose (∗) holds for ψ and φ, then show that
(∗) holds for ¬ψ and for ψ ∨ φ. This is left as an exercise.
4 ASSAF SHANI

Finally, we need to show that if (∗) is true for φ(x, y, x1 , ..., xn ) them (∗) is
true after applying a bounded quantifier. Let ψ(y, x1 , ..., xn ) be the formula (∃x ∈
y)φ(x, y, x1 , ..., xn ), and fix b, a1 , ..., an in X. Suppose first that (X, ∈) |= ψ(b, a1 , ..., an ).
Then, working in (X, ∈), there is some a ∈ b such that φ(a, b, a1 , ..., an ) holds in
(X, ∈). By induction hypothesis (by (∗) for φ), it follows that φ(a, b, a1 , ..., an ) is
true (in V ), and therefore ψ(b, a1 , ..., an ) is true.
Assume now that ψ(b, a1 , ..., an ) is true. By the definition of ψ, there is some
a ∈ b such that φ(a, b, a1 , ..., an ) holds. Since X is transitive, then a ∈ X. Therefore
in (X, ∈) we conclude that ψ(b, a1 , ..., an ) is true. 

Corollary 2.9. If X is a transitive set, then (X, ∈) satisfies the axiom of exten-
sionality. That is, given A, B ∈ X, if A and B have the same members, then
A = B.
Proof. Given A, B ∈ X, the axiom of extensionality for A, B can be written as a
∆0 formula
((∀x ∈ A)x ∈ B) ∧ ((∀x ∈ B)x ∈ A).


2.4. Relativization. When studying different models of set theory, we want to

know when a model M satisfies a sentence φ. There is a simple way to express the
statement M |= φ with a formula, as follows.
Definition 2.10. Let M be a set, or a definable class. For a formula φ(x1 , ..., xn )
we define the relativization of φ to M , denoted φM (x1 , ..., xn ), by induction on the
construction of formulas.
• (x ∈ y)M is defined to be x ∈ y;
• (x = y)M is defined to be x = y;
• given (φ ∨ ψ)M is defined to be φM ∨ ψ M ;
• (¬φ)M is defined to be ¬(φM );
• (∃xφ)M is defined to be (∃x ∈ M )φM .
Remark 2.11. M is a parameter in the formula ψ M . If M is a definable class,
defined using the formula χ(x), we replace x ∈ M with χ(x).
Example 2.12. Let φ be the sentence ∀x∀y∃z(x ∈ z ∧ y ∈ z). Then φVω is the
formula (∀x ∈ Vω )(∀y ∈ Vω )(∃z ∈ Vω )(x ∈ z ∧ y ∈ z).
Exercise 2.13. Show that for any set M , considered as a model (M, ∈) in the
language of set theory, for any formula φ(x1 , ..., xn ) and any a1 , ..., an ∈ M ,
φM (a1 , ..., an ) is true if and only if (M, ∈) |= φ(a1 , ..., an ).
Exercise 2.14. (1) Show that for any set M and formula φ, φM is a ∆0 for-
mula.
(2) Suppose φ is a ∆0 formula and M is any set, show that φM is φ.
2.5. The Levy Hierarchy.
Definition 2.15. Say that a formula is Σ0 , or Π0 , if it is ∆0 . Define recursively:
• a formula is Σn+1 if it is of the form ∃xφ for some Πn formula φ;
• a formula is Πn+1 if it is of the form ∀xφ for some Σn formula φ.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 5

Say that a property P (that is, some definable relation) is Σn (resp. Πn ) if there
is a Σn (resp. Πn ) formula φ which defines P . Say that a property P is ∆n if it is
both Σn and Πn .
Up to logical equivalence, Σn formulas are precisely the negations of Πn formulas,
and Πn formulas are the negations of Σn formulas. So a property P is ∆n if and
only if both P and ¬P are Σn (equivalently, if both P and ¬P are Πn ).
The proof that a specific formula “correctly represents the property P” will often
use some axioms of ZF (and will not be a simple logical equivalence). When saying
that “P is Σn ” we usually mean that this is proved in ZF. In some contexts we will
allow ourselves to use more, or restrict ourselves to less, than ZF.
Example 2.16. The property P (R, X) saying that R is a (strict) well ordering on
X, is Π1 . It can be described as follows: R is a well ordering on X if
(1) for any x, y ∈ X, if x 6= y then either x R y or y R x, and not both;
(2) for any x, y, z ∈ X, if x R y and y R z then x R z;
(3) For any set Y , if Y ⊆ X then there is some y ∈ Y such that for any other
z ∈ Y , either y R z or y = z.
Properties (1) and (2) are ∆0 in fact. (3) is of the form ∀Y followed by a ∆0
statement (note that saying Y ⊆ X is ∆0 , (∀y ∈ Y )y ∈ X, and therefore is Π1 .
Example 2.17. The property P (x) saying that “x is an ordinal”, is ∆0 . It can be
expressed as follows: x is an ordinal if x is transitive and ∈ is a linear ordering of
x. We saw above that being a linear order can be expressed by a ∆0 formula.
Note that we used ZF to argue that the above ∆0 formula captures the concept
of an ordinal. Specifically, the axiom of foundation tells us that if ∈ is a linear order
on x then it must be a well order. Without the axiom of foundation, we would need
to stipulate this extra assumption, which would give a Π1 instead of ∆0 .
Example 2.18. The property P (x, y) saying that “x is the powerset of y”, is Π1 .
This can be expressed by the Π1 formula φ(x, y):
∀a(a ∈ x ⇐⇒ a ⊆ y)
S
Exercise 2.19. The property P (x, y) saying that “x is the union of y, x = y”,
is ∆0 .
Exercise 2.20. (1) Suppose that M is a transitive set, ψ(x1 , ..., xn ) is a Π1
formula and a1 , ..., an are in M . Show that if ψ(a1 , ..., an ) is true, then
(M, ∈) |= ψ(a1 , ..., an ).
(2) Suppose that M is a transitive set, ψ(x1 , ..., xn ) is a Σ1 formula and a1 , ..., an
are in M . Show that if (M, ∈) |= ψ(a1 , ..., an ) then ψ(a1 , ..., an ) is true.
(3) Conclude that if M is a transitive set, P (x1 , ..., xn ) is a ∆1 property, then for
any a1 , ..., an in M , P (a1 , ..., an ) holds if and only if (M, ∈) |= P (a1 , ..., an ).
That is, ∆1 statements are absolute between transitive models of set theory.
(4) Show that part (1) can fail for Σ1 formulas. That is, find a Σ1 formula
φ(x1 , ..., xn ) (for some n), a transitive set M and a1 , ..., an in M such that
φ(a1 , ..., an ) is true, yet (M, ∈) |= ¬φ(a1 , ..., an ).
Closure properties. While the syntactic requirement for being Σn or Πn are
rather strict, the collection of Σn properties and Πn properties are closed under a
variety of operations.
Theorem 2.21. For n ≥ 1.
6 ASSAF SHANI

(1) If P and Q are Σn (respectively Πn ) properties, then P ∨ Q, P ∧ Q, (∃x ∈

X)P , and (∀x ∈ X)P , are Σn (respectively Πn ) properties.
(2) If P is a Σn property then ∃xP is a Σn property.
(3) If P is a Πn property then ∀xP is a Πn property.
Proof. The proof goes by induction on n. Let us consider the case n = 1, as the
inductive step is similar.
We show that if P is Σ1 then ∃xP is Σ1 as well. Let φ(x, x1 , ..., xn ) be a Σ1
formula such that P (x, x1 , ..., xn ) holds if and only if φ(x, x1 , ..., xn ). By definition,
φ is of the form ∃yψ(y, x, x1 , ..., xn ), where ψ is a Σ0 formula. Now P is equivalent
to the formula ∃x∃yψ(y, x, x1 , ..., xn ), which is equivalent to the Σ1 formula
∃X(∃x, y ∈ X)ψ(y, x, x1 , ..., xn ).
Next we show that if P is Σ1 then (∀x ∈ X)P is Σ1 . Let φ(X, x, x1 , ..., xn ) be a
Σ1 formula such that P (X, x, x1 , ..., xn ) holds if and only if φ(X, x, x1 , ..., xn ). By
definition, φ is of the form ∃yψ(y, X, x, x1 , ..., xn ), where ψ is a Σ0 formula. Now P
is equivalent to the statement (∀x ∈ X)∃yψ(y, X, x, x1 , ..., xn ), which is equivalent
to the Σ1 property
∃Y (∀x ∈ X)(∃y ∈ Y )ψ(y, X, x, x1 , ..., xn ).
Note that for the latter equivalence we used the axiom of replacement as well as
the axiom of foundation.
The remaining cases are easier, and left as an exercise. For example, we show
that if P and Q are Σ1 then P ∧ Q is Σ1 . For notational simplicity assume P (x)
and Q(x) are properties of a single variable. By assumption, there are Σ1 formulas
φ(x) and ψ(x) such that which define P and Q respectively. There are Σ0 formulas
ψ0 (x, y) and φ0 (x, y) such that φ is ∃yφ0 and ψ is ∃yψ0 . Now P ∧ Q can be written
as ∃yψ0 (x, y) ∧ ∃yφ0 (x, y), which is equivalent to the Σ1 formula ∃y(ψ0 (x, y) ∧
φ0 (x, y)). 

Exercise 2.22. Complete the proof of Theorem 2.21

2.6. The Vα hierarchy. Define recursively along the ordinals
• V∅ = ∅;
• Vα+1 =
S P(Vα ), the powerset of Vα ; and
• Vα = β<α Vβ , if α is a limit ordinal.
The axiom
S of foundation is equivalent to the statement that the whole universe is
V = α Vα . That is, any set x is in Vα for some ordinal α.
Consider the formula φ(y, F ) saying that y is an ordinal and F codes the con-
struction of Vα up to y. That is:
• F (∅) = ∅;
• (∀β ∈ y)(F (β + 1) = P(F (β))); S
• ∀β ∈ y, if β is limit then F (β) = γ<β F (γ).
Note that the second bullet is Π1 and the rest is ∆0 , so φ is a Π1 property.
Corollary 2.23. The property P (X, α) saying that “X is Vα ” is ∆2 .
Proof. First, X is equal to Vα if and only if there exists an F such that φ(α + 1, F )
and X = F (α). This is a statement of the form ∃(Π1 ), and is therefore Σ2 .
 145B SET THEORY II: AN INTRODUCTION TO FORCING 7

Second, X is equal to Vα if for any F , φ(α + 1, F ) =⇒ F (α) = X. This is

a statement of the form ∀(Π1 → ∆0 ), equivalently, ∀(∆0 ∨ ¬Π1 ), which is ∀(Σ1 ),
which is Π2 . 
Corollary 2.24. The property P (X) saying “X is Vα for some ordinal α” is Σ2 .
Proof. By the previous corollary, we may write this statement as ∃(Σ2 ), which is
Σ2 . 
2.7. The axioms of ZFC. Recall the axioms of ZFC:
• Extensionality: for any A, B, if A ⊆ B and B ⊆ A then A = B.
• Comprehension (scheme): given a formula φ(x, x1 , ..., xn ), we include the
axiom saying that for any a1 , ..., an and any set A there exists a set B whose
elements are precisely those x ∈ A for which φ(x, a1 , ..., an ) holds.
• Pairing: for any a, b there exists a set whose elements are precisely a and
b.
• Union: for any set X there exists a set Y such that y ∈ Y ⇐⇒ ∃x ∈
X(y ∈ x).
• Infinity: there exists an inductive set, that is, a set X such that ∅ ∈ X and
x ∪ {x} ∈ X for any x ∈ X.
• Foundation: for any set X there exists x ∈ X such that x ∩ X = ∅.
• Replacement (scheme): given a formula φ(x, y, x1 , ..., xn ) we include the
axiom saying that for any a1 , ..., an and for any set X, if for any x ∈ X
there exists a unique y such that φ(x, y, a1 , ..., an ) holds, then there exists a
set Y such that for any x ∈ X there is a y ∈ Y such that φ(x, y, a1 , ..., an ).
• The axiom of choice: for any set X, if all members of X are non-empty
then there exists a function f with domain X such that f (x) ∈ x for every
x ∈ X.
Remark 2.25. The axioms of Extensionality, and Foundation are Π1 statement.
The axiom of Infinity is a Σ1 statement. The axioms of Pairing, Union, and Choice
are Π2 statements.
2.8. H(κ). Let κ be an infinite regular cardinal. Say that a set x is hereditarily
smaller than κ if |t.c.(x)| < κ, where t.c.(x) is the transitive closure of x. Let
H(κ) be the collection of all sets x which are hereditarily smaller than κ.
Remark 2.26. If x is hereditarily smaller than κ then x is in Vκ . So H(κ) ⊆ Vκ
and H(κ) is a set by comprehension.
It follows from the definition that H(κ) is a transitive set.
Exercise 2.27. Show that H(ω) = Vω . However, H(ω1 ) is strictly contained in
Vω1 .
Theorem 2.28 (Assume ZFC). For a regular cardinal κ, H(κ) satisfies all the
axioms of ZFC apart from the powerset axiom.
Proof. The main point is showing that the axiom of replacement holds. The others
are easier. S
For the union axiom, take x ∈ H(κ). Then S the transitive closure of x is
closure of {x}. So x ∈ H(κ). To be precise, we must
contained in the transitiveS
also show that the set z = x is in fact the union of x as calculated in H(κ). That
is, that H(κ) |= “z is the union of x”. This is easy to show directly, but it also
8 ASSAF SHANI

follows at once from our observations regarding the complexity of this statement.
Recall that the definition of “z is the union of x” is Π1 , and H(κ) is transitive,
therefore “z is the union of x” also holds in H(κ).
Fix a formula φ(x, y) and a set X ∈ H(κ) such that for any x ∈ X there exists
a unique y in H(κ) such that M |= φ(x, y). Then
(∀x ∈ X)(∃!y ∈ H(κ))(φM (x, y)).
We may now apply the axiom of replacement for the formula φM , to find a set
Y of all sets y ∈ H(κ) for which there exists some x ∈ X such that φM (x, y) holds.
Since there is a surjective map from X onto Y , |Y | < κ. It suffices to prove the
following:
Lemma 2.29. If Y ⊆ H(κ) and |Y | < κ then Y ∈ H(κ).
Proof.
[
t.c.(Y ) = t.c.(y).
y∈Y

So t.c.(Y ) can be written as a union of < κ many sets of size < κ. Since κ is a
regular cardinal, we conclude that t.c.(Y ) is of size < κ. 

Exercise 2.30. Show that the powerset axiom fails in H(ℵ1 ).

It follows that H(ℵ1 ) satisfies all the axioms of ZFC but not the powerset axiom,
and therefore the powerset axiom is independent from the other axioms of ZFC.

2.9. The reflection principle.

Theorem 2.31. For any formula φ(x1 , ..., xn ) there is an ordinal α such that
for any a1 , ..., an ∈ Vα , φVα (a1 , ..., an ) holds if and only if φ(a1 , ..., an ).
That is, Vα “reflects” correctly the truth value of φ.
Definition 2.32. Given a function f whose domain and range are ordinals, say
that α is a closure point of f if for any β < α, f (β) < α. We also consider
definable functions whose domain may be the class of all ordinals. That is, f
is defined by some formula χ(x, y) in the sense that for each ordinal α there is a
unique ordinal θ such that χ(α, θ) holds.
Exercise 2.33. Given a definable function f from ordinals to ordinals, the collec-
tion of all closure points of f is
(1) definable via a formula; S
(2) closed, that is, if X is a set of closure points of f and α = sup X = X,
then α is a closure point of f ;
(3) unbounded, that is, for any ordinal β there is an ordinal α > β such that
α is a closure point of f .
Hint: part (3) makes an essential use of the axiom of replacement.
We will prove the following strong version of Theorem 2.31: for any formula φ
there is a definable function f all of whose closure points reflect φ correctly. That
is, there is a closed unbounded class of ordinals which reflect φ.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 9

Exercise 2.34. Suppose χ1 , ..., χn are definable functions from ordinals to ordinals.
Show that there is a formula χ defining a function from ordinals to ordinals such
that any closure point of χ is a closure point for each of χ1 , ..., χn .
Lemma 2.35. Let φ(x1 , ..., xn ) be a formula, then there is a definable function f
from ordinals to ordinals such that for any closure point of f
(?) for any a1 , ..., an ∈ Vα , φVα (a1 , ..., an ) holds if and only if φ(a1 , ..., an ).
Proof. We prove this inductively on the construction of formulas. If φ is an atomic
formula then (?) is satisfied for any α. (In fact this is the case for any ∆0 formula
φ.)
The main inductive case is the existentional quantifier. Suppose φ is of the form
∃xψ(x, x1 , ..., xn ), where we already know the lemma for ψ. That is, there is a
definable function h such that for any closure point α for h, (?) holds for Vα and
ψ.
Define a function f recursively as follows. f (0) = 0. Suppose we define f on all
ordinals below α. Let θ = supβ<α f (β). Let ζ > θ be the minimal ordinal such
that
∀a1 , ..., an ∈ Vθ (∃xψ(x, a1 , ..., an ) =⇒ (∃x ∈ Vζ )ψ(x, a1 , ..., an )).
Such ζ exists by the axiom of replacement. Define f (α) = h(β) where β is minimal
such that h(β) ≥ ζ. Note that any closure point for f is also a closure point for h.
(Also any closure point of f is a limit ordinal.)
Let α be a closure point of f and take a1 , ..., an in Vα . Since α is a closure point
for h, we have

ψ Vα (a, a1 , ..., an ) if and only if ψ(a, a1 , ..., an ),

for any a ∈ Vα . In particular

φVα (a1 , ..., an ) =⇒ φ(a1 , ..., an ).
Conversely, suppose φ(a1 , ..., an ) is true. Fix β < α such that a1 , ..., an are all in
Vβ . Since ∃xψ(x, a1 , ..., an ), it follows from the definition of f that there is an a
in Vf (β) for which ψ(a, a1 , ..., an ) holds, and so ψ Vα (a1 , ..., an ) holds. As α is a
closure point of f , f (β) < α, and so a ∈ Vα . It follows that φVα (a1 , ..., an ) holds,
as required. 

2.10. Coding of formulas. We may code formulas as sets in Vω as follows. (We

fix an infinite list of variable x0 , x1 , ... to be used by our formulas.) For each formula
φ we assign a code [φ] ∈ Vω recursively.
• [xi = xj ] = h0, i, ji, [xi ∈ xj ] = h1, i, ji;
• [¬φ] = h2, [φ]i;
• [φ ∧ ψ] = h3, [φ], [ψ]i;
• [∃xi φ] = h4, i, [φ]i.
Say that x codes a formula, Formula(x), if x = [φ] for some formula φ.
Claim 2.36. Formula(x) is a ∆1 property (using ω as a parameter).
Proof. x codes a formula if for any set Z, if
(∀i, j ∈ ω) h0, i, ji ∈ Z∧h1, i, ji ∈ Z∧(∀y, z ∈ Z) (h2, zi ∈ Z ∧ h3, z, yi ∈ Z ∧ h4, z, yi ∈ Z)
10 ASSAF SHANI

then x ∈ Z. That is, any set Z that has the codes for atomic formulas, and is closed
under the operations for formula constructions, must contain codes for all formulas
and therefore x. This is a Π1 statement.
Also, x is a formula if and only if there exists a function F whose domain is
a natural number and F codes a construction sequence of formulas F (0), F (1), ...
where x is F (n) for some n in the domain of F . The latter can be written as a Σ1
statement. 
If x codes a formula we will write φx for the formula coded by x.
Exercise 2.37. For each natural number n there is a ∆1 formula Formulan (x)
such that x is a code for a Σn formula if and only if Formulan (x) holds.
Exercise 2.38. There is a ∆1 formula Free(x, y) which holds if and only if x codes
a formula and y ⊆ ω is the set of all free variables appearing in φx .
Similarly, the property Pk (x, y, z1 , ..., zk ) saying “y codes a formula with k vari-
ables and x is the code for the sentence φy (z1 , ..., zk )” is ∆1 (φx is the sentence
obtained from the formula φy by substituting the free variables with constants).
Fact 2.39. For each natural number n ≥ 1 there is a Σn formula Truthn (x) which
holds if and only if x is a code of a true Σn sentence.
Proof sketch. The proof is by induction. We sketch the Σ1 case. First we find a
Σ1 formula Truthqf (x, z) which holds if and only if z = hz1 , ..., zk i is a sequence
of length k, for some k ∈ ω, x is a code for a quantifier free formula with k free
variables and φx (z1 , ..., zk ) is true.
Truthqf (x, z) says that there are sequences F and T coding a construction se-
quence F (0), F (1), ..., F (n) which does not use the “∃” clause at all and F (n) is x,
and a sequence of “truth values” T (0), ..., T (n) ∈ {0, 1} such that for each i ≤ n
• if F (i) is of the form h0, l, ti, then T (i) = 1 iff zl = zt ;
• if F (i) is of the form h1, l, ti then T (i) = 1 iff zl ∈ zt ;
• if F (i) is of the form h2, F (j)i, j < i then T (i) = 1 iff T (j) = 0;
• if T (i) is of the form h3, F (j1 ), F (j2 )i then T (i) = 1 iff T (j1 ) = 1 and
T (j2 ) = 1;
and T (n) = 1. This is a Σ1 statement, and it works.
Now we can define a Σ1 formula Truth1 (x, z) saying: z = hz1 , ..., zk i and there
is a code y such that x is the code for the formula ∃x0 φy (x0 , x1 , ..., xk ) and there
is a z0 such that Truthqf (x, hz0 , z1 , ..., zn i).
In particular if x codes a Σ1 sentence then φx is true if and only if Truth1 (x, ∅).

Corollary 2.40. For any n there is an ordinal α such that for any Σn formula
φ(x1 , ..., xk ) and for any a1 , ..., ak ∈ Vα
φVα (a1 , ..., ak ) ⇐⇒ φ(a1 , ..., ak )
In this case we say that Vα is a Σn elementary substructure of V , written
Vα ≺Σn V .
Proof. Apply the reflection theorem for the formula Truthn . There is an ordinal α
such that for any x, z ∈ Vα
(Truthn )Vα (x, z) ⇐⇒ Truthn (x, z).
 145B SET THEORY II: AN INTRODUCTION TO FORCING 11

Now for any Σn formula φ(x1 , ..., xk ), and any a1 , ..., ak ∈ Vα , let z = ha1 , ..., ak i.
φVα (a1 , ..., ak ) ⇐⇒ (Truthn )Vα ([φ], z) ⇐⇒ Truthn ([φ], z) ⇐⇒ φ(a1 , ..., ak ).
Remark 2.41. To be precise, in the left most “ ⇐⇒ ” above we applied Fact 2.39
inside Vα , even though Vα might not satisfy all axiom of ZF. This can be remedied as
follows. We proved Fact 2.39 using ZF. The proof, like any proof, used only finitely
many of the axioms of ZF. Let Φ be this finite collection. Using the reflection
theorem, we can find α such that Vα reflects Truthn and all sentences in Φ. In
particular, Fact 2.39 is true in Vα . (We will use this trick again, in particular when
talking about forcing)

2.11. Undefinablity of truth. [Not covered in class]
Theorem 2.42 (Tarski’s undefinability of truth). There is no formula Truth(x)
such that Truth(x) holds if and only if x is a code of a true sentence.
Proof. Assume otherwise that such formula exists. Let θ(y) be the formula ¬Truth([φy (y)]).
That is, θ(y) says “y is a code for a formula with one variable, and for the unique
x ∈ Vω such that x = [φy (y)], ¬Truth(x)”. (This can be done, in a similar way
to the exercises above. That is, we can define the relation for “substituting a
variable”.)
Let z = [θ]. Then θ(z) holds if and only if ¬Truth(φz (z)) if and only if
¬Truth(θ(z)) if and only if θ(z) fails. A contradiction. 
2.12. Ordinal Definability.
Definition 2.43. Say that a set A is ordinal definable (OD) if there is a formula
φ(x, x1 , ..., xn ) and ordinals α1 , ..., αn such that for any set a
a ∈ A ⇐⇒ φ(a, α1 , ..., αn )
Example 2.44. For any ordinal α, Vα is ordinal definable. For any cardinal κ,
H(κ) is ordinal definable.
Exercise 2.45. A is ordinal definable if and only if there is a formula φ(X, x1 , ..., xn )
and ordinals α1 , ..., αn such that A is the unique set for whoch φ(A, α1 , ..., αn ) is
true.
Definition 2.46. Say that a set A is hereditarily ordinal definable if every set
in the transitive closure of {A}Sis ordinal definable. That is, A is OD, the members
of A are OD, the members of A are OD, and so on...
Example 2.47. Every ordinal is hereditarily ordinal definable.
Lemma 2.48. A is ordinal definable if and only if there exists an ordinal α, a
formula φ, ordinals α1 , ..., αn < α such that
a ∈ A ⇐⇒ a ∈ Vα ∧ φVα (a, α1 , ..., αn )
In particular, being ordinal definable is a definable property: A is ordinal de-
finable if and only if “there is an ordinal alpha and ordinals α1 , ..., αn < α and a
set X such that X = Vα and a ∈ A ⇐⇒ φX (a, α1 , ..., αN ). The reason we can
definably quantify over all formulas is because we only quantify over ∆0 formulas.
Furthermore, truth for ∆0 formulas is definable. (It is Σ1 , and in fact ∆1 .)
Similarly, the property “A is a hereditarily ordinal definable set” is a definable
property.
12 ASSAF SHANI

Definition 2.49. Let HOD be the class of all hereditarily ordinal definable sets.
By definition HOD is a transitive class. That is, if A is in HOD and a ∈ A then
a is in HOD. This may not be the case for OD.
Theorem 2.50 (Assuming ZF). The class HOD satisfies ZFC.
Corollary 2.51 (Gödel). If ZF is consistent then ZFC is consistent. In other
words, we cannot refute the axiom of choice using ZF set theory.
Proof. We prove for example the union axiom. Suppose A is HOD. In particular
A is OD. Let φ(x, α1 , ..., αn ) be such that a ∈ A ⇐⇒ φ(a, S α1 , ..., αn ). Define
ψ(x, α1 , ..., αn ) as ∃y(φ(y, α1 , ..., αn ) ∧ S
x ∈ y). This shows that A is OD as well.
Furthermore,
S the transitive closure of A is contained in the transitive closure of
A, so A is hereditarily ordinal definable as well.
The rest of the ZF axioms can be verified in a similar way, and the proofs are
similar to those we have seen in H(κ) and Vα before. This is left for the reader.
The main point is showing that the axiom of choice holds in HOD, even without
assuming it in V. It suffices to show the following: given an OD set A there is an
OD relation < which is a well ordering of A. (If A is HOD then < will also be.)
Let A be ordinal definable. Fix α so that  for any a in A there is a formula
φ, ordinals α1 , ..., αn < α such that a = x ∈ Vα : φVα (x, α1 , ..., αn ) . We say
that a is defined via φ, α1 , ..., αn . (α is now fixed, and there could be many tuples
φ, α1 , ..., αn defining the same set.)
Recall that given well orders <1 , ..., <m on sets X1 , ..., Xm , the lexicographic
ordering on X1 × ... × Xm is defined as follows: (x1 , ..., xm ) < (y1 , ..., ym ) if and
only if for the first i such that xi 6= yi , xi <i yi .
We coded formulas as members of Vω , which is countable. (Fix some well ordering
of Vω , for example, via an enumeration of it.) The ordinal α is well ordered by the
membership relation ∈. Consider the lexicographic ordering on Vω × αn . 
We have a map from Vω ×α<ω sending h[φ], α1 , ..., αn i to ah[φ],α1 ,...,αn i = x ∈ Vα : φVα (x, α1 , ..., αn ) ,
where the image includes the transitive closure of A. Furthermore this map is de-
finable using the parameters ω and α. For a ∈ A let n(a) be the minimal n such
that a = ahφ,α1 ,...,αn i for some hφ, α1 , ..., αn i ∈ Vω × αn .
Finally, we can use this map to well order A: say that a < b if and only if either
n(a) < n(b) or n(a) = n(b) = n and the minimal tuple hφ, α1 , ..., αn i such that
a = ahφ,α1 ,...,αn i is lexicographically smaller than the minimal tuple hψ, β1 , ..., βn i
such that b = bhψ,β1 ,...,βn i . < well orders A and is ordinal definable. 
2.13. Lowenheim Skolem theorems. Recall:
Definition 2.52. Given a language L, a structure M and a substructure N of M ,
we say that N is an elementary substructure of M , denoted N ≺ M , if for any
formula φ(x1 , ..., xn ) and for any a1 , ..., an ∈ N ,
M |= φ(a1 , ..., an ) ⇐⇒ N |= φ(a1 , ..., an ).
(By definition, N is a substructure of M if N ⊆ M and the above holds for atomic
formulas. In the language of set theory, this simply means that N is contained in
M and they interpret ∈ the same way.)
Given the notation introduced above, if M is a model of set theory and N is a
submodel of M , then N ≺ M if and only if N ≺Σn M for each n.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 13

Lemma 2.53 (Tarski-Vaught test). Suppose N is a substructure of M . Then

N ≺ M if and only if for any formula φ(x, x1 , ..., xn ) and any a1 , ..., an ∈ N , if
there is a b in M such that M |= φ(b, a1 , ..., an ) then there exists a a ∈ N such that
M |= φ(a, a1 , ..., an ).
Theorem 2.54 (Using ZFC). Suppose M is a model.
(1) For any X ⊆ M there exists an elementary substructure N ≺ M such that
X ⊆ N and |N | = |X| + ℵ0 . (That is, if X is infinite then |N | = |X| and
if X is finite then |N | = ℵ0 .)
(2) For any cardinal κ ≥ |M | there is an elementary extension of M , M ≺ N
such that |N | = κ.
Part (1) will be more relevant for us, so we outline the proof.
S
Proof. We define N as N = n<ω Nn where Nn is defined recusively as follows.
Fix some choice function f defined on all non-empty subsets of M . Given a formula
φ(x, x1 , ..., xk ) and a1 , ..., ak in M let M (φ, a1 , ..., ak ) = {a ∈ M : M |= φ(a, a1 , ..., ak )}.
Let N0 = X and
[
Nn+1 = Nn ∪ {f (M (φ, a1 , ..., ak )) : φ is a formula and a1 , ..., ak ∈ Nn } .
This is a set, again using the fact that “truth in M ” can be defined by a formula,
and then using the axiom of replacement.
Now N satisfies the Tarski-Vaught test, and therefore N ≺ M . 
Remark 2.55. There is a subtlety here. This looks, and is, very similar to the
proof of the reflection principle. Why could we not guarantee Vα ≺ V there? The
point is that truth in V is not definable, and we had to limit our interest to Σn
formulas for a bounded n in order to define truth. However, since M is a set, truth
in M is always definable (in a ∆0 way), for all formulas.
Definition 2.56. Two models M and N are said to be elementary equivalent,
denoted N ≡ M , if for any sentence φ, M |= φ if and only if N |= φ.
Definition 2.57. Two models M and N are isomorphic if there is a bijective
function f : M → N such that for any formula φ(x1 , ..., xn ) and any a1 , ..., an in M
M |= φ(a1 , ..., an ) ⇐⇒ N |= φ(f (a1 ), ..., f (an )).
Note that if N ≺ M then N and M are elementary equivalent. Also if N and
M are isomorphic then they are elementary equivalent.
Recall:
Fact 2.58 (a corollary of the Mostowski collapse theorem). Suppose M is a set
and (M, ∈) satisfies the axiom of extensionality. Then there is a transitive set N
and an isomorphism π : M → N . Furthermore, if X is transitive and X ⊆ M then
π  X = id, that is, π(x) = x for any x ∈ X.
Proof. Since ∈ is well founded, have a rank function on ∈ in M :
• x ∈ M is of rank 0 if there is no y ∈ M such that y ∈ x.
• x ∈ M is of rank α if for all y ∈ M , if y ∈ x then y has rank < α.
Note that by extensionality there is precisely one set x in M of rank 0, and we
define π(x) = ∅. π is defined recursively by π(x) = {π(y) : y ∈ x}.

14 ASSAF SHANI

Corollary 2.59. For any transitive set M there is a countable transitive model N
which is elementary equivalent to N .
Proof. By Lowenheim Skolem we may find N 0 ≺ M which is countable. Applying
the mostowski collapse we find a transitive set (N, ∈) which is isomorphic to (N 0 , ∈).
So N is countable and is elementary equivalent to M . 

Exercise 2.60. Show that if N ≺ Vω2 and N is transitive then N is not countable.
Corollary 2.61. The property “κ is a cardinal” is Π1 but not Σ1 .
Proof. We saw that this is a Π1 property. It remains to show that it is not Σ1 . If
it were, then it would be absolute between transitive models of set theory.
Suppose first that we may find some transitive model of ZF, M . Then there is
a model N which is countable, transitive, and is elementary equivalent to M . In
particular N is also a model of ZF. There is an ordinal κ such that N |= “κ is the
first uncountable cardinal”. Note that κ > ω. Since N is countable and transitive,
then κ is in fact a countable ordinal. In particular, κ is not a cardinal.
Remark 2.62. What if we cannot find a transitive model satisfying ZF? The proof
can be remedied by using the finiteness of proofs. That is, if we could prove, using
ZF (or ZFC), that “κ is a cardinal” is a Σ1 property, this proof would following
from some finitely many axioms Φ ⊆ ZFC. By the reflection principle we may find
Vα |= Φ. So we may find a countable transitive model satisfying all axioms in Φ,
again leading to the same contradiction.


The same proof also shows that “|X| ≤ |Y |” is not Π1 .

Theorem 2.63 (Levy). Let κ be an uncountable cardinal. Then H(κ) ≺Σ1 V .
That is, for any Σ1 formula φ(x1 , ..., xn ) and any a1 , ..., an ∈ H(κ),
φH(κ) (a1 , ..., an ) ⇐⇒ φ(a1 , ..., an ).
(Note that we are not assuming that κ is regular.)

Proof. Since Σ1 formulas are “upwards absolute” between transitive models, it

suffices to show the implication ⇐. Let φ(x1 , ..., xn ) be ∃yψ(y, x1 , ..., xn ) where ψ
is a ∆0 formula. Assume that φ(a1 , ..., an ) holds, for a1 , ..., an ∈ H(κ). Fix b such
that ψ(b, a1 , ..., an ).
Fix α large enough so that a1 , ..., an , b ∈ Vα . Since ψ is a ∆0 formula and Vα is
transitive we have ψ Vα (b, a1 , ..., an ). Let X be the transitive closure of {a1 , ..., an }.
Then |X| < κ. By Lowenhein-Skolem, we may find an elementary substructure
M ≺ Vα such that X ∪ {b} ⊆ M and |M | = |X| + ℵ0 < κ. Applying Mostowski
collapse, there is a transitive set N and an isomorphism π : M → N . Furthermore,
π(x) = x for any x ∈ X.
Let c = π(b). It follows that N |= ψ(c, a1 , ..., an ). Finally, N ⊆ H(κ), and
they are both transitive, so they agree on ∆0 statements. That is, H(κ) |=
ψ(c, a1 , ..., an ), and therefore H(κ) |= φ(a1 , ..., an ).


Exercise 2.64. Show that Vω1 6≺Σ1 V .

 145B SET THEORY II: AN INTRODUCTION TO FORCING 15

3. Forcing
From now on we will assume that there exists a transitive set M such that
(M, ∈) is a model of ZFC. (We will discuss later how to avoid this additional
assumption. We have seen similar arguments.) By applying Lowenheim-Skolem,
and a Mostowski collapse, we may assume that there is a countable transitive set
M such that (M, ∈) is a model of ZFC.
Remark 3.1. In particular, we may calculate LM (L as calculated by M ). By
absoluteness of being L, it follows that LM is Lα for some ordinal α. So in fact we
have a countable ordinal α such that Lα satisfies ZFC.
Let α be the minimal ordinal such that Lα is a model of ZFC. Then in Lα there
is no transitive model of ZFC at all!
Again, this is evidence that in order to find a model in which, say, the continuum
hypothesis fails, we cannot rely on inner models. Instead we must find a way to go
outside a given model of set theory.
We start by just adding something, for example, to prove the consistency if
V 6= L. For example, we will want to take some set a ⊆ ω which is not in M , and
find a model M 0 such that M ⊆ M 0 , a ∈ M 0 and M 0 is again a model of ZFC. Not
any set a would work, and part of the work will be to find a’s that do work.
Recall that a set a ⊆ ω can be naturally identified with its characteristic function
χa : ω → {0, 1}, χa (k) = 1 ⇐⇒ k ∈ a.
Definition 3.2. An approximation to a subset of ω is a function p whose domain
is a finite subset of ω, and it take values in {0, 1}.
We say that an approximation p is stronger than q if p extends q as a function.
That is, dom(q) ⊆ dom(p) and p(k) = q(k) for any k ∈ dom(q). (p decides more
values of the set a we try to approximate.) In this case we write p ≤ q (smaller is
stronger).
More generally we will consider arbitrary partially ordered sets (P, ≤).
Definition 3.3. A set P is partially ordered by ≤ if ≤ is a transitive symmetric
relation on P. We usually assume that P has a maximal element (sometimes denoted
as 1P ). We call (P, ≤) a partially ordered set, or poset.
For example, let P be the set of all finite approximations to a subset of ω, and
define p ≤ q as above. The maximal element is the empty function ∅.
Definition 3.4. Let (P, ≤) be a partially ordered set. p, q ∈ P are compatible if
there exists r ∈ P such that r ≤ p and r ≤ q.
In our example, p and q are compatible if and only if they agree on their common
domain dom p ∩ dom q, which is true if and only if the set p ∪ q is a well defined
function whose domain is dom p ∪ dom q, a finite subset of ω.
Suppose we do find, as above, M ⊆ M 0 with a ∈ M 0 . Then, in M 0 , we can define
the set of all approximates of a
G = all approximations p such that χa extends p.
Note that we can also define a from G, as follows: k ∈ a if and only if there is some
p ∈ G such that k ∈ dom p and p(k) = 1.
Some properties of G:
16 ASSAF SHANI

Definition 3.5. Suppose (P, ≤) is a partially ordered set and G ⊆ P. Say that G
is a filter if it satisfies the following.
• If p ∈ G and p ≤ q then q ∈ G;
• If p, q ∈ G then there is r ∈ G such that r ≤ p and r ≤ q.
We will always assume that the filter G is not empty, in which case it must be
the case that 1P ∈ G.
An additional property that we needed to define a from G is that for any k ∈ ω
there is some p ∈ G such that k ∈ dom(p). We will in fact add the set a by adding
a filter G, and define a as above.
Fix a transitive model M , a partially ordered set (P, ≤) ∈ M and a filter G ⊆
P (most likely not in M !). We now describe a model M [G] extending M and
containing G.

3.1. Names.
Definition 3.6. Define recursively on the ordinals the names for P as follows.
• N0 = ∅;
• Nα+1 =S P(P × Nα );
• Nα = β<α Nβ if α is a limite ordinal.
Define N to be the union of all Nα where α is an ordial in M . (A more precise
notation would be N M (P), the class of P-names defined in the model M .) We say
that τ is a P-name if it is in N .
For example, N1 = {∅}. The members of N2 are subsets of P × {∅}, that is, they
are sets of pairs (p, ∅) where p ∈ P. Generally, a member of Nα+1 is a set of pairs
(p, τ ) where τ is in Nα .
Remark 3.7. The collection of all names for P, in M , is a definable class in M .
In fact the relation “X = Nα ” is definable in M in a ∆2 manner.
Definition 3.8. For a name τ say that its rank is α if α is the minimal ordinal
such that τ ⊆ P × Nα .
3.2. Extension. Let G ⊆ P be a filter. We define a model M [G] as follows.
Definition 3.9. Given a filter G ⊆ P and a P-name τ , we define its realization
according to G, τ [G], recursively on the rank as follows.
(1) If has rank 0, τ ⊆ P × ∅ = ∅. So τ = ∅ and we define τ [G] = ∅.
(2) Given τ of rank α + 1 define
τ [G] = {σ[G] : ∃p ∈ G((p, σ) ∈ τ )} .
We define the model M [G] as the collection of all τ [G] for τ ∈ N .
Lemma 3.10. M [G] is transitive.
Proof. Fix y ∈ x ∈ M [G]. Since x ∈ M [G], there is a name τ such that x = τ [G].
By definition of τ [G], there is a name σ and a condition p ∈ G such that (p, σ) ∈ τ
and y = σ[G]. In particular, y ∈ M [G]. 

It follows that M [G] satisfies the axioms of extensionality and foundation.

Lemma 3.11. M ⊆ M [G].
 145B SET THEORY II: AN INTRODUCTION TO FORCING 17

Proof. For each x ∈ M we define a canonical name x̌ recursively on rank, as

follows.
• ˇ∅ = ∅;
• Fix x and suppose y̌ was defined for all y ∈ x. By replacement, applied in
M , there must be some ordinal β such that for all y ∈ x, y̌ is of rank ≤ β.
Now define x̌ to be {(1P , y̌) : y ∈ x}, a name of rank β + 1.
Finally, we prove inductively that x̌[G] = x for all x ∈ M (independent of G).
Indeed, ˇ∅ = ∅ and by induction
x̌[G] = {σ[G] : ∃p ∈ G((p, σ) ∈ x̌)} = {y̌[G] : y ∈ x} = {y : y ∈ x} = x.


Lemma 3.12. G ∈ M [G].

Proof. We define a P-name Ġ so that for any filter G ⊆ P, Ġ[G] = G. Let Ġ =

{(p, p̌) : p ∈ P}. 

Exercise 3.13. Show that if G ∈ M then M [G] = M .

3.3. Some axioms in M [G].
Lemma 3.14. The union axiom holds in M [G].

S Suppose x ∈ M
Proof. [G], x = τ [G]. We want to find a name τ ? such that τ ? [G]
?
is x. That is, z ∈ τ [G] ⇐⇒ there is y ∈ x such that z ∈ y.
Note that y ∈ x if and only if y = σ[G] where (p, σ) ∈ τ for some p ∈ G. For
such y, z ∈ y if and only if z = ρ[G] where (q, ρ) ∈ σ for some q ∈ G.
Define τ ? to be the set of pairs (r, ρ) for which there are q, p ∈ P and a name σ
such that r ≤ p and r ≤ q and (q, ρ) ∈ σ and (p, σ) ∈ τ . [Note that if τ is of rank
β then τ ? is also of rank β.]
Finally, we claim that τ ? [G] = τ [G]. Assume first z ∈ τ [G]. Then z = ρ[G]
S S
and there is y = σ[G] such that z ∈ y ∈ τ [G]. That is, there are conditions p, q ∈ G
such that (p, σ) ∈ τ and (q, ρ) ∈ σ. Since G is a filter, there is a condition r ∈ G
which extends both p and q. We see now that (r, ρ) is in τ ? , and since r ∈ G,
z = ρ[G] ∈ τ ? [G].
For the other direction, assume that z ∈ τ ? [G]. So z = ρ[G] and there is some
r ∈ G such that (r, ρ) ∈ τ ? . By the definition of τ ? , there are p, q ∈ P such that
r ≤ p, q and a name σ such that (q, ρ) ∈ σ and (r, σ) ∈ τ . Since G is a filter and
r ∈ G, then both p and q are in G. It follows that z = ρ[G] ∈ σ[G] ∈ τ [G], as
required. 

Assume P is the poset of finite approximations of a subset of ω, a ⊆ ω and

G = Ga is the set of all p ∈ P such that a extends p. It follows
S from Lemma 3.12
and the above that a ∈ M [G], as it can be defined as a = G.
Exercise 3.15. Show that, for any filter G ⊆ P, M [G] satisfies
(1) the pairing axiom;
(2) the axiom of infinity.
Lemma 3.16. M and M [G] have the same ordinals.
18 ASSAF SHANI

Proof. We saw that M ⊆ M [G], so every ordinal of M is an ordinal in M [G]. We

prove by induction on the rank of names that if τ is a name of rank β and τ [G] is
an ordinal then τ [G] ≤ β.
Indeed if τ [G] is an ordinal then for any (p, σ) ∈ τ , if p ∈ G then σ[G] is an
ordinal as well. By the inductive assumption we get in this case that σ[G] < β. So
τ [G] is a set of ordinal, each of which is < β, thus τ [G] ≤ β. 
3.4. A “bad” filter. Recall that M is a countable transitive model of ZFC. Let
κ = M ∩ Ord, all the ordinals in M . Since M is transitive, κ is an ordinal, and it
is countable. Fix a bijection f : ω → κ.
We can “code” f as a subset of ω as follows. First, f can be coded as a relation
R ⊆ ω × ω defined by R(i, j) ⇐⇒ f (i) ∈ f (j). Next, we can code a relation
R ⊆ ω × ω as a subset of ω via some injective map ω × ω → ω. For example, define
k ∈ a ⇐⇒ k = 2i · 3j where (i, j) ∈ R. (Alternatively use a “snake enumeration”
of ω × ω.)
Let G = Ga be the set of all finite approximations of a. Then the axiom of
replacement fails in M [G]. STo see this, recall first that G ∈ M [G]. As the union
axiom holds in M [G], f = G is in M [G] as well, where f : ω → {0, 1}.
Assume towards a contradiction, that the axioms of replacement and compre-
hension hold in M [G]. It follows that that a ∈ M [G], and therefore R ∈ M [G].
Note that for each i ∈ ω we may consider R  {j ∈ ω : (j, i) ∈ R}, which is a
well ordering of ω, isomorphic to f (i). Specifically the Mostowski collapse of
R  {j ∈ ω : (j, i) ∈ R} is f (i).
Now consider the formula φ(n, α) saying that α is an ordinal which is the
mostowski collapse of R  {j ∈ ω : (j, n) ∈ R}. Then in M [G], φ defines a function
with domain ω, yet its range is not bounded, as it includes all the ordinals of M [G].
3.5. Generic filters. Let (P, ≤) be a poset. Given p ∈ P define Pp = {q ∈ P : q ≤ p},
the set of all conditions that extend p.
Definition 3.17. A set D ⊆ P is open if for any p ∈ D, if q ≤ p then q ∈ D.
In other words, if p ∈ D then Pp ⊆ D. We can view the sets Pp is “basic open
sets”. Then any open set is a union of basic open sets.
Definition 3.18. A set D ⊆ P is dense if for any p ∈ P there is q ≤ p such that
q ∈ D.
Example 3.19. Let P be the poset of all finite approximations for a subset of ω.
(1) The set of all p ∈ P such that the domain of p is equal to some n ∈ ω, is
dense.
(2) The set of all p ∈ P such that 3, 5 ∈ dom p and p(3) = 1 − p(5) is open.
(3) The set of all p ∈ P such that there is some n ∈ ω for which n, n + 1, n + 2 ∈
dom p and p(n) = p(n + 1) = p(n + 2) = 1, is dense and open.
(4) Fix n ∈ ω. The set of all Dn of all p ∈ P such that there is some m ∈ ω
for which p(2m · 3n ) = 1, is a dense open set. (That is, the binary relation
coded by the subset approximation by p has the pair (m, n) in it.)
Definition 3.20. Fix M and (P, ≤) ∈ M . A filter G ⊆ P is generic over M if
G ∩ D 6= ∅ for any dense open set D ∈ M .
Example 3.21. Let G = Ga ⊆ P be the “bad” filter from Section 3.4. Fix n ∈ ω
such that f (n) = 0. Then there is no i ∈ ω such that (i, n) ∈ R, and so there is
 145B SET THEORY II: AN INTRODUCTION TO FORCING 19

no i ∈ ω such that 2i · 3n ∈ a. So G ∩ Dn = ∅ for the dense open set Dn from

Example 3.19 part (4).
Exercise 3.22. The intersection of finitely many dense open subsets of P is dense
and open.
Exercise 3.23. Let P be the poset of all finite approximations for a subset of ω.
Suppose G ⊆ P is generic over M .
S∈
(1) Prove that G / M.
(2) Prove that G is a well defined function from ω to {0, 1}.
Claim 3.24. The following are equivalent:
• G ⊆ P is generic over M ;
• G ∩ D 6= ∅ for any dense set D ∈ M .
Proof. Suppose D ⊆ P is dense. Let D∗ be all conditions q which extend some
condition in D. Then D∗ is dense and open, and contains D.
Suppose that G ⊆ P is a generic filter. We must show that it intersects all dense
subsets in M . Given a dense set D ∈ M , we know that G∩D∗ 6= ∅. Fix q ∈ G∩D∗ .
By definition there is some p ∈ D such that q ≤ p. Since G is a filter, p ∈ G, so
p ∈ G ∩ D, as desired. 
Lemma 3.25. Let M be a countable transitive model and P a poset in M . Then
there is a filter G ⊆ P which is generic over M .
Proof. Let D0 , D1 , D2 , ... be an enumeration of all sets D ∈ M such that D ⊆ P is
dense and open. We prove a stronger version of the lemma: that for every condition
p ∈ P there is a filter G ⊆ P such that p ∈ G and G is generic over M .
We define a sequence of conditions in P, p0 , p1 , ... such that p0 ≥ p1 ≥ p2 ≥ ...,
as follows:
• let p0 = p;
• given pn , let pn+1 be a member of Dn which extends pn .
This is possible by the density of each Dn .
Finally, let G be the set of all q ∈ P such that q ≥ pn for some n. Then G is a
filter. For any n, pn+1 ∈ G ∩ Dn . Thus G intersects all dense open subsets of P
which are in M , and is generic. 
Given a filter G which is generic over M , we will call M [G] a generic extension
of M .
3.6. The forcing relation.
Definition 3.26 (The forcing relation). Let φ(x1 , ..., xn ) be a formula in the lan-
guage of set theory, p a condition in P, and τ1 , ..., τn P-names. Say that p forces
φ(τ1 , ..., τn ), written p φ(τ1 , ..., τn ), if for any generic filter G ⊆ P over M , if
p ∈ G then M [G] |= φ(τ1 [G], ..., τn [G]).
Example 3.27. For any poset P and any p ∈ P, we defined a name τ = Ġ and
showed that τ [G] = G for any filter G. So for any filter G, if p is in G then
p̌[G] ∈ τ [G]. Thus p p̌ ∈ τ .
Our goal is to establish the following fundamental theorem about the forcing
relation.
20 ASSAF SHANI

Theorem 3.28 (Truth and definability for the forcing relation). Fix a countable
transitive model M and a poset (P, ≤) in M .
• [Truth] If G ⊆ P is a generic filter over M , φ(x1 , ..., xn ) is a formula in the
language of set theory, and τ1 , ..., τn are names for P in M , then

M [G] |= φ(τ1 [G], ..., τn [G]) ⇐⇒ (∃p ∈ G)p φ(τ1 , ..., τn ).

• [Definability] For any formula φ(x1 , ..., xn ) in the language of set theory
there is a formula ψφ (P, ≤, p, z1 , ..., zn ) such that for any p and any τ1 , ..., τn

p φ(τ1 , ..., τn ) ⇐⇒ M |= ψφ (P, ≤, p, τ1 , ..., τn ).

From the definition of , it is not clear immediately that there are many instance
of conditions forcing statements. The first clause above shows that in fact anything
that is true in some generic extension is forced by some condition. The second
clause is even more remarkable. The definition of takes into consideration all
possible generic extensions of M . A process one can certainly not define inside M .
However, it turns out to be completely definable in M !
Before proving Theorem 3.28 let us see how it is used. We show that for a model
M of ZF, any generic extension M [G] satisfies ZF, and if M satisfies the axiom of
choice then so does M [G].

3.6.1. The axiom of replacement. Let M , P be as above and G ⊆ P a generic filter

over M . We show that M [G] satisfies the axiom of replacement. Fix a1 , ..., an ∈
M [G], a formula φ(x, y, z1 , ..., zn ) and a set X ∈ M [G] such that

M [G] |= (∀x ∈ X)(∃!y)φ(x, y, a1 , ..., an ).

We must find a set Y ∈ M [G] such that M [G] |= (∀x ∈ X)(∃y ∈ Y )φ(x, y, a1 , ..., an ).
Fix names ρ1 , ..., ρn and τ such that X = τ [G] and ai = ρi [G]. Given p ∈ P
and a P-name µ, define α(p, µ) to be the minimal ordinal α such that there is some
name η of rank α with p φ(µ, η, ρ1 , ..., ρn ).
Let β be the rank of τ . Since M satisfies replacement, there is an ordinal α∗
such that for any name µ of rank < β and for any p ∈ P, α(p, µ) < α∗ . Here we
use the definability clause of Theorem 3.28 to argue that the map p, µ 7→ α(p, µ) is
definable in M .
Finally, let σ be the name of all pairs (p, η) with α(p, η) < α∗ such that there
is a name µ of rank < β and there is a q ∈ P such that p ≤ q, (q, µ) ∈ τ and
p φ(µ, η, ρ1 , ..., ρn ). We claim that σ[G] is the set of all y for which there is
x ∈ τ [G] such that φM [G] (x, y, a1 , ..., an ) holds.
First, if y ∈ σ[G], y = η[G] where p ∈ G and (p, η) ∈ σ. Then there is a p ≤ q
and (q, µ) ∈ τ such that p φ(µ, η, ρ1 , ..., ρn ). Then p, q are both in G, and so
x = µ[G] ∈ τ [G] and φM [G] (x, y, a1 , ..., an ) holds.
Conversely, fix x ∈ τ [G]. Then there is a pair (q, µ) ∈ τ with q ∈ G and µ[G] = x.
In particular µ is of rank < β. By assumption, there is some y ∈ M [G] such that
M [G] |= φ(x, y, a1 , ..., an ). Fix η 0 such that y = η 0 [G]. By Theorem 3.28 there is
some condition p0 ∈ G forcing that φ(µ, η 0 , ρ1 , ..., ρn ). By choice of α∗ , we may find
η so that p0 φ(µ, η, ρ1 , ..., ρn ) and α(p0 , η) < α∗ . Since p0 , q ∈ G, there is a p ∈ G
with p ≤ p0 and p ≤ p. Now (p, η) ∈ σ, and so y = η[G] ∈ σ[G], as required.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 21

3.7. Proof of the forcing theorem.

Definition 3.29 (Strong forcing). For a condition p ∈ P, a sentence φ in the
forcing language, we define the relation p ∗ φ (read “p strongly forces φ”). More
specifically, one can think of p ∗ φ as “p directly witnesses that φ must hold”.
First, consider atomic sentences and their negations. We define recursively on
the ranks of the names:
(1) p ∗ σ ∈ τ if there is a q ∈ P and a name λ such that p ≤ q and (q, λ) ∈ τ
and p ∗ λ = σ;
(2) p ∗ σ ∈ / τ if there is no q ≤ p such that q ∗ σ ∈ τ .
∗
(3) p σ 6= τ if either
• there is a q ∈ P and a name λ such that p ≤ q and (q, λ) ∈ σ and
p ∗ λ 6∈ τ , or
• there is a q ∈ P and a name λ such that p ≤ q and (q, λ) ∈ τ and
p ∗ λ 6∈ σ, (or both);
∗
(4) p σ = τ if there is no q ≤ p such that q ∗ σ 6= τ .
(So, p witnesses that σ = τ if there is no way to extend p and witness that some
name is going to be in one set but not the other.)
We continue to define the relation ∗ on all formulas, this time by recursion on
the construction of formulas:
(5) p ∗ ¬φ(τ1 , ..., τn ) if there is no q ≤ p such that q ∗ φ(τ1 , ..., τn );
(6) p ∗ φ(τ1 , ..., τn ) ∨ ψ(τ1 , ..., τn ) if p ∗ φ(τ1 , ..., τn ) or p ∗ ψ(τ1 , ..., τn );
(7) p ∗ ∃xφ(x, τ1 , ..., τn ) if there is a name σ such that p ∗ φ(σ, τ1 , ..., τn ).
Lemma 3.30. If p ∗ φ(τ1 , ..., τn ) and r ≤ p then r ∗ φ(τ1 , ..., τn ). That is, if p
knows that φ will hold, and r has more information than p, then r also knows that
φ must hold.
Lemma 3.31. For any formula φ(x1 , ..., xn ) and names τ1 , ..., τn , the set D of all
conditions p ∈ P such that either p ∗ φ(τ1 , ..., τn ) or p ∗ ¬φ(τ1 , ..., τn ), is dense
and open in P.
Proof. That D is open follow from the preceding lemma. Now for any condition p,
either there is some q ≤ p for which q ∗ φ(τ1 , ..., τn ), in which case q ∈ D, or there
is no such q, in which case p ∗ ¬φ(τ1 , ..., τn ) by definiton, and so p ∈ D. 
Theorem 3.32. Let M be a countable transitive model, (P, ≤) a poset in M and
G ⊆ P a generic filter over M . For any formula φ(x1 , ..., xn ) and names τ1 , ..., τn ,
∗
M [G] |= φ(τ1 [G], ..., τn [G]) ⇐⇒ (∃p ∈ G)p φ(τ1 , ..., τn ).
In particular, if p ∗ φ then φ holds in any generic extension M [G] such that
p ∈ G, and so p φ. In particular, if M [G] |= φ(τ1 [G], ..., τn [G]), then there is some
p ∈ G such that p ∗ φ(τ1 , ..., τn ) and so p φ(τ1 , ..., τn ). So the Truth clause of
Theorem 3.28 follows.
Proof. We first prove the theorem for atomic formulas and their negations, by induc-
tion on the rank of names. Then for all formulas by induction on the construction
of formulas.
(1) Assume first p ∗ σ ∈ τ , then there is a q ∈ P and a name λ such that
p ≤ q and (q, λ) ∈ τ and p ∗ λ = σ. For any generic filter G ⊆ P over
M , if p ∈ G then also q ∈ G, and so λ[G] ∈ τ [G] by definition. Since
22 ASSAF SHANI

the rank of λ is smaller than the rank of τ , it follows from the inductive
assumption, since p ∈ G and p ∗ σ = λ, that σ[G] = λ[G]. We conclude
that σ[G] ∈ τ [G], as required.
Assume now that G ⊆ P is a generic filter over M and M [G] |= σ[G] ∈
τ [G]. By definition, there is some (q, λ) ∈ τ with q ∈ G and λ[G] = σ[G].
Since the rank of λ is smaller than the rank of τ , it follows from the inductive
hypothesis that there is some p0 ∈ G such that p0 ∗ λ = σ. Since G is a
filter, we may find p ∈ G with p ≤ p0 and p ≤ q. Now p ≤ q, (q, λ) ∈ τ and
p ∗ λ = σ, so p ∗ σ ∈ τ and p ∈ G, as required.
(2) The proof is the same as in (5), we we assume the theorem holds for φ and
prove it for ¬φ.
(3) Assume first that p ∈ G and p ∗ σ 6= τ . Assume that there is a condition
q ∈ P and a name λ such that p ≤ q and (q, λ) ∈ σ and p ∗ λ ∈ / τ.
(In the other case the proof is the same, replacing the roles of σ and τ .)
Then q ∈ G, so by the inductive assumption λ[G] ∈ / τ [G]. Furthermore, by
definition λ[G] ∈ σ[G], so σ[G] 6= τ [G].
Assume now that G ⊆ P is a generic filter over M and M [G] |= σ[G] ∈ /
τ [G]. Assume without loss of generality that there is some x ∈ σ[G] \ τ [G].
By definition there is some (q, λ) ∈ σ with q ∈ G and λ[G] = x. By the
inductive assumption, there is some p0 ∈ G such that p0 ∗ λ ∈ / τ . Take
p ∈ G with p ≤ p0 , q, then p ∗ σ 6= τ .
(4) The proof is the same as in (5), we we assume the theorem holds for φ and
prove it for ¬φ.
(5) Assume that p ∈ G and p ∗ ¬φ(τ1 , ..., τn ). Then there is no q ≤ p such that
q ∗ φ(τ1 , ..., τn ). It follows that M [G] |= ¬φ(τ1 [G], ..., τn [G]). Otherwise,
M [G] |= φ(τ1 [G], ..., τn [G]), and so by the inductive assumption there is
some q 0 ∈ G with q 0 ∗ φ(τ1 , ..., τn ). Find q ∈ G with q ≤ q 0 , p. This
contradicts our assumption.
Now assume M [G] |= ¬φ(τ1 [G], ..., τn [G]). The set D of all conditions
p ∈ G for which either p ∗ φ(τ1 , ..., τn ) or p ∗ ¬φ(τ1 , ..., τn ) is open
and dense, and therefore intersects G. By the inductive assumption, if
p ∈ G and p ∗ φ(τ1 , ..., τn ), then M [G] |= φ(τ1 [G], ..., τn [G]), which cannot
happen. Thus there must be some p ∈ G with p ∗ ¬φ(τ1 , ..., τn ), as
required.
(6) Left as an exercise.
(7) Left as an exercise.


Finally, we see that the difference between forcing and strong forcing is a double
negation.
∗
Theorem 3.33. p φ(τ1 , ..., τn ) ⇐⇒ p ¬¬φ(τ1 , ..., τn ).
∗
Since was defined, in M , the definability of follows immediately.

Proof. Assume first that p ∗ ¬¬φ(τ1 , ..., τn ). By Theorem 3.32, if G is a generic fil-
ter with p ∈ G then M [G] |= ¬¬φ(τ1 [G], ..., τn [G]), and so M [G] |= φ(τ1 [G], ..., τn [G]).
By definition, p φ(τ1 , ..., τn ).
On the other hand, assume p φ(τ1 , ..., τn ), that is, for any generic filter G with
p ∈ G, M [G] |= φ(τ1 [G], ..., τn [G]). Then there is no q ≤ p with q ∗ ¬φ(τ1 , ..., τn ),
 145B SET THEORY II: AN INTRODUCTION TO FORCING 23

as we can always find a generic filter which contains q (and p). By definition,
p ∗ ¬¬φ(τ1 , ..., τn ). 
It follows from Theorem 3.33 that the forcing relation is definable in M ,
concluding the Definability clause of Theorem 3.28, and so concluding the proof of
Theorem 3.28.
3.8. The remaining ZFC axioms in M[G].
3.8.1. The powerset axiom.
Definition 3.34. Let τ be a P-name. Say that µ is a canonical name for a
subset of τ if for any (p, ρ) ∈ µ there is a q ∈ P with p ≤ q and (q, ρ) ∈ τ .
Exercise 3.35. If µ is a canonical name for a subset of τ then for any filter G,
µ[G] ⊆ τ [G].
Note that if µ is a canonical name for a subset of τ then the rank of µ is smaller
or equal to the rank of τ .
Lemma 3.36. Suppose τ, µ are P-names, G ⊆ P is a generic filter and µ[G] ⊆ τ [G].
Then there is a canonical name for a subset of τ , µ∗ , such that µ∗ [G] = µ[G].
Proof. Define µ∗ as the set of all pairs (q, ρ) such that there is some q ≤ p with
(p, ρ) ∈ τ and such that q ρ ∈ µ. The definability clause of Theorem 3.28 allows
us to define µ∗ in M . Furthermore, by definition µ∗ is a canonical name for a subset
of τ .
It remains to show that µ[G] = µ∗ [G]. Suppose first x ∈ µ∗ [G]. Then x = ρ[G]
where (q, ρ) ∈ µ∗ for some q ∈ G. By definition, there is some p ∈ P such that
q ≤ p, (p, ρ) ∈ τ and q ρ ∈ µ. We conclude that x = ρ[G] ∈ µ.
For the converse, assume that x ∈ µ[G]. By assumption, x ∈ τ [G], so there is
some name ρ such that ρ[G] = x and (p, ρ) ∈ τ for some p ∈ G. Since ρ[G] ∈ µ[G],
it follows from the truth clause of Theorem 3.28 that there is some q 0 ∈ G such
that q 0 ρ ∈ µ. Since G is a filter, we may find q ∈ G such that q ≤ q 0 and q ≤ p.
Now (q, ρ) ∈ µ∗ and so x = ρ[G] ∈ µ∗ [G], as required. 
Lemma 3.37. Suppose M is a countable transitive model of ZF, (P, ≤) is a poset
in M and G ⊆ P is a generic filter over M . Then M [G] satisfies the powerset axiom.
Proof. Fix a name τ . We must find a name σ such that M [G] |= σ[G] = P(τ [G]).
Define σ to be the name of all pairs (1P , µ) where µ is a canonical name for a subset
of τ . Note that if τ has rank β then σ has rank β + 1.
Note that σ[G] is equal to the set of all µ[G] where µ is a canonical name for a
subset of τ . It follows that and member of σ[G] is contained in τ [G].
Finally, suppose x ⊆ τ [G] and x ∈ M [G]. Then x = µ[G] for some name µ.
By the lemma, there is a canonical name for a subset of τ , µ∗ such that µ∗ [G] =
M [G] = x. Thus x ∈ σ[G]. 
3.8.2. The axiom of choice. We note first that in the proofs so far it was not nec-
essary for M to satisfy the axiom of choice.
Lemma 3.38. Suppose M is a countable transitive model of ZF, (P, ≤) is a poset
in M and G ⊆ P is a generic filter over M . If M also satisfies the axiom of choice,
then so does M [G].
24 ASSAF SHANI

Proof. To prove that the axiom of choice holds, it suffices to show that for each
M [G]
ordinal α there is a well ordering of Vα . Let M [G]α be Vα , that is, Vα as
calculated in M [G].
By Lemma 3.36 the map τ 7→ τ [G] from NαM (the set of names of rank α in M )
to M [G]α is surjective. Furthermore, this map is in M [G]. Since M satisfies the
axiom of choice, then there is a well ordering of NαM .
Finally, recall that given a set X and a well ordering of X, and a surjective map
g : X → Y , we may injectively map Y into X by sending y ∈ Y to the minimal
element in g −1 (y). Furthermore, this injective map from Y to X induces a well
ordering of Y from the well ordering on X. 

Corollary 3.39. Assuming that ZF is consistent, then ZFC+V 6= L is consistent

is well. In other words, ZFC does not prove that every set is construcible.
Proof. As we have seen, we may find a countable transitive model M satisfying
ZFC and V = L. (If we somehow find such M that satisfies V 6= L, then we are
done.) Let P be the poset for all finite approximations of a subset of ω, and fix a
filter G ⊆ P which is generic over M .
By Exercise 3.23 the generic filter G is not in M . Furthermore, as M and M [G]
have the same ordinals, LM [G] = LM = M . More specifically: for each ordinal α
in M , M thinks that “LM α is Lα ”. Since the latter is a ∆1 statement, and M and
M [G] are transitive models, it is true in M [G] as well. So M [G] thinks that “LMα
is Lα ”.
So in M [G] there is a set G such that M [G] |= G ∈ / L, soSM [G] thinks that
V 6= L. (Equivalently, G defines a characteristic function fG = G, which defines
a subset of ω, a = {n ∈ ω : fG (n) = 1}, and a ∈ / L.) 

The extension M [G] above, where P is the poset of finite approximations to a

subset of ω and G ⊆ P is generic over M , is often called a “generic extension by a
single Cohen subset of ω”, and the poset P is called “Cohen forcing”. In M [G] we
have the set a = {n ∈ ω : (∃p ∈ G)p(n) = 1}, often called the “generic Cohen set”.
We show that this set a, or alternatively the filter G, are not ordinal definable
in M [G]. In fact, the model HODM [G] (HOD as calculated in the model M [G]), is
contained in M . (So if M |=“V=L” then HODM [G] = LM [G] = LM = M .
Definition 3.40. Let (P, ≤P ), (Q, ≤Q ) be posets. Say that f : P → Q is an iso-
morphism if it is a bijection and satisfies
p ≤P q ⇐⇒ f (p) ≤Q f (q),
for any p, q ∈ P.
Note that if f is such an isomorphism then f (1P ) = 1Q . Furthermore f −1 is an
isomorphism from Q to P.
Lemma 3.41. Suppose f : P → Q is an isomorphism, f, P, Q ∈ M , and G ⊆ P is
generic over M . Define H = {f (p) : p ∈ G}. Then H ⊆ Q is generic over M and
M [G] = M [H].
Proof. Fix a dense subset D ⊆ Q with D ∈ M . First we show that f −1 (D) ⊆ P
is dense. Fix some p ∈ P. By assumption there is a q ≤ f (p) with q ∈ D. Now
p0 = f −1 (q) ∈ D and p0 ≤ p since f is an isomorphism.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 25

Since f is in M then f −1 (D) is in M as well and so there is some p ∈ G∩f −1 (D).

Now by definition f (p) ∈ H ∩ D, as required.
Finally, note that H ∈ M [G], since it is defined from f and G, and similarly
G ∈ M [H]. The following exercise therefore concludes the proof.
Exercise 3.42. Let M be a countable transitive model, (P, ≤) a poset in M and
G ⊆ P generic over M . Suppose N is a transitive model of ZF such that M ⊆ N
and G ∈ N . Then M [G] ⊆ N .

Lemma 3.43. Suppose X ∈ M [G], X ⊆ M and X is ordinal definable in M [G].
Then X ∈ M .
Proof. By assumption, there are ordinals α1 , ..., αn , a formula φ(x, z1 , ..., zn ) such
that
x ∈ X ⇐⇒ φM [G] (x, α1 , ..., αn ).
By assumption also any x ∈ X is in M .
Claim 3.44. For any formula ψ and x1 , ..., xn ∈ M , if p ψ(x̌1 , ..., x̌n ) then
∅ ψ(x̌1 , ..., x̌n ) (where ∅ is 1P here).
Proof. Assume towards a contradiction that ∅ does not force ψ(x̌1 , ..., x̌n ). Then
there is some condition q ∈ P such that q ψ(x̌1 , ..., x̌n ) (important step!)
Find n large enough such that both dom p and dom q are contained in n =
{0, ..., n − 1}. Extend p and q to p0 ≤ p and q 0 ≤ q with dom p0 = dom q 0 = n. Let
∆ = {k < n : q 0 (k) 6= p0 (k)} ⊆ n.
Define a map f : P → P as follows. Given r ∈ P, dom(f (r)) = dom r and for any
k ∈ dom r
• if k ∈ ∆, f (r)(k) = 1 − r(k) and
• if k ∈
/ ∆, f (r)(k) = r(k).
Then f is a bijection (f is its own inverse) and it is an isomorphism from P to P
(which we call an automorphism of P). Note also that f (p0 ) = q 0
Now fix a generic filter G ⊆ M such that p0 ∈ G. Let H = {f (r) : r ∈ G}. Then
0
q ∈ H and so q ∈ H. Applying the forcing theorem twice we conclude
• M [G] |= ψ(x1 , ..., xn ), as p ∈ G and p ψ(x̌1 , ..., x̌n );
• M [H] |= ¬ψ(x1 , ..., xn ), as q ∈ H and q ¬ψ(x̌1 , ..., x̌n ).
Finally, this is a contradiction as M [G] = M [H]. 
Back to the proof of the lemma: if x ∈ X then there is some p ∈ G forcing
φ(x̌, α̌1 , ..., α̌n ) (by the forcing theorem), and so ∅ φ(x̌, α̌1 , ..., α̌n ). Also, if x ∈ M
and x ∈ / X, then there is some p ∈ G forcing ¬φ(x̌, α̌1 , ..., α̌n ) (by the forcing
theorem), and so ∅ ¬φ(x̌, α̌1 , ..., α̌n ).
In conclusion, X can be defined as
{x : ∅ φ(x̌, α̌1 , ..., α̌n )} ,
and this set is definable in M as is definable in M .
[Of course, to apply comprehension we need to bound all the x’s in a single set
in M . As always, consider the map X 3 x 7→ minimal α such that x ∈ VαM . This
is definable in M [G], and the domain is a set X, so by replacement there must be
a bound. In other words, if X ⊆ M then X ⊆ Mα = VαM for some ordinal α. Now
define in M the set X as {x ∈ Mα : ∅ φ(x̌, α̌1 , ..., α̌n )}, using comprehension.]
26 ASSAF SHANI

4. Independence of the Continuum Hypothesis

In the generic extension M [G] discussed so far, adding “a Cohen subset a ⊆ ω”,
we added of course many different new subsets of ω (e.g. ω \ a). It turns out
however that if M satisfies the continuum hypothesis, then so would M [G]. To find
a model in which the continuum hypothesis fails we will add many subsets of ω.

Definition 4.1. For an ordinal κ let Pκ be the poset of all finite function p : dom p →
{0, 1} with dom p ⊆ κ × ω. Say that p ≤ q if p extends q as a function. That is,
dom q ⊆ dom p and p  dom q = q.

The idea is that for each α < κ, p(α, ·) : ω → {0, 1} codes a new subset of ω, and
we add κ of those this time.

Lemma 4.2. Suppose M S is a countable transitive model, κ ∈ M and G ⊆ Pκ is

generic over M . Then f = G is a well defined function from κ × ω to {0, 1}. For
α < κ, let xα = {k ∈ ω : f (α, k) = 1}. Then for α 6= β < κ, xα 6= xβ .

Proof. This is a “standard density argument”. First note that for each n ∈ ω and
α < κ the set of all conditions p ∈ Pκ for which (α, n) ∈ dom p is a dense subset of
Pκ . So by genericity there is some p ∈ G with (α, n) ∈ dom p, so (α, n) ∈ dom f .
Furthermore, f is a well defined function since G is a filter.
Finally, for any α 6= β < κ, the set of all p ∈ Pκ for which there is some m such
that (α, m) ∈ dom p and (β, m) ∈ dom p and p(α, m) 6= p(β, m), is dense in Pκ . It
follows that for each α 6= β there is some m and p ∈ G as above, and therefore
m ∈ xα ⇐⇒ m ∈ / xβ . 

We conclude that, by forcing with Pκ , κ many distinct subsets of ω are added.

So, if we let κ = ω2M and force with Pκ , we will get a model in which there are ω2
many subsets of ω, so CH fails? Not so fast!
We know that M and M [G] have the same ordinals, but in general they do
not necessarily agree on the cardinals. For example, we know that ω2M is just a
countable ordinal, so maybe we added a countable enumeration of it to M [G]. In
this case, the new “ω2 -many” subsets of ω that we added, in M [G], would just be
countably many subsets of ω...

Example 4.3. Let κ be a cardinal. Let Col(ω, κ) be all finite functions p : dom p →
κ where dom p ⊆ ω is finite. We consider Col(ω, κ) as a poset with the partial order
p ≤ q if p extends q as a function.

Exercise 4.4. Let M be a countable transitive model, κ a cardinal in M (for

M
S κ = ω7 ), and suppose G ⊆ Col(ω, κ) is a generic filter over M . Then
example,
f = G is a well defined function and f : ω → κ is surjective. It follows that κ is
countable in M [G].

For example, if κ = ω1M , then M [G] |=“κ is a countable ordinal, that is, κ < ω1 .
M [G]
There is some other ordinal λ = ω1 . Necessarily in M : “λ is a cardinal greater
than ℵ1 ”.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 27

4.1. Chain condition. The concept of cardinality, and of being a cardinal, is not
preserved between generic extensions in general. Nevertheless, Cohen’s forcing to
add (many) subsets of ω is “mild” enough, and in fact does preserve cardinals. The
central notion is that of anti-chains.
Fix a poset P. Recall that two conditions p, q ∈ P are compatible if there is
some r ∈ P with r ≤ p and r ≤ q. In this case we write p k q. p and q are
incompatible if there is no r ∈ P with r ≤ p and r ≤ q. In this case, there can be
no filter G containing both p and q, and we write p ⊥ q.
Definition 4.5. Let P be a poset and A ⊆ P.
• Say that A is an antichain if for any p, q ∈ A, if p 6= q then p and q are
not compatible.
• An antichain A ⊆ P is maximal if for any p ∈ P there is some q ∈ A such
that p and q are compatible.
Recall that, assuming the axiom of choice, for any antichain A ⊆ P, there is a
maximal antichain A ⊆ A0 ⊆ P.
In fact, the arguments in this section, involving chain conditions, do rely on the
model M to satisfy the axiom of choice.
Definition 4.6. Say that a poset P satisfies the countable chain condition (“P
is c.c.c.”) if all of its antichains are at most countable. (That is, there are no
uncountable antichains in P.)
Example 4.7. The poset P = Pω of finite approximation for a subset of ω satisfies
the countable chain condition, since P is countable.
Example 4.8. Let P be the set of all non-empty intervals (α, β) where α < β ∈ R.
Consider P as a poset with the partial order p ≤ q if p ⊆ q. Then P satisfies the
countable chain condition.
Theorem 4.9. Suppose M is a countable transitive model of ZFC, (P, ≤) is a poset
in M , and M |=“P is c.c.c.”. Then M and M [G] agree on cardinals.
Proof. We need to show that for any ordinal κ ∈ M , M |=“κ is a cardinal” if and
only if M [G] |=”κ is a cardinal”. The ⇐ implication is immediate, as Π1 statements
are downwards-absolute.
Assume now κ is a cardinal in M . Suppose f ∈ M [G], f : α → κ for some ordinal
α < κ. We need to show that f is not surjective. Fix a name τ such that τ [G] = f .
For each β < α, let Rβ = {ζ < κ : (∃p ∈ P)p τ (β) = ζ ∧ τ is a function}.
Claim 4.10. Rβ is countable
Proof. Using the axiom of choice, in M , choose a sequence hpζ : ζ ∈ Rβ i of condi-
tions such that pζ τ (β) = ζ. Note that {pζ : ζ ∈ Rβ } is an antichain of P, and
so must be countable by assumption. 
S
Define (in M ) R = β<α Rβ . R is the union of α many countable sets, and so
its size is at most |α| × ℵ0 = |α| (assume α is infinite). Since κ is a cardinal in M ,
there is some ζ ∈ κ \ R.
Note that for any p ∈ P and any β < α, p does not force τ (β) = ζ. In particular,
no p ∈ G forces that, so f (β) 6= ζ for all β < α. That is, f is not surjective. 
28 ASSAF SHANI

Exercise 4.11 (ZFC). Suppose M is a countable transitive model of ZFC, (P, ≤)

is a poset in M , and M |=“P is c.c.c.”. Then M and M [G] agree on cofinalities.
That is, if M [G] thinks κ is a cardinal with cofinality λ, then M thinks that the
cofinality of κ is λ as well.
Exercise 4.12. Suppose κ is an uncountable cardinal. Find an uncountable an-
tichain A ⊆ Col(ω, κ).
Theorem 4.13 (ZFC). Fix a cardinal κ. Let Pκ be the poset of all finite function
p : dom p → {0, 1} with dom p ⊆ κ × ω. Then Pκ satisfies the countable chain
condition.
Proof. Suppose A ⊆ Pκ is an uncountable antichain. Fix a regular cardinal θ >
κ for example, θ = κ+ ). Apply Downwards LS to find a countable elementary
submodel M ≺ H(θ) such that κ ∈ M , Pκ ∈ M , and A ∈ M . [M is not transitive!]
For any p ∈ A consider p ∩ M , which is the function p restricted to the domain
dom p ∩ M . Note that p ∩ M is in M (any finite subset of M is in M ). Since M
is countable and A uncountable, there is a condition p ∈ A \ M . Let r = p ∩ M .
Note that p 6= r and r ∈ M .
Now H(θ) |= “∃t(t ∈ A ∧ t ≤ r)” (this is a statement about A and r). Since
M ≺ H(θ), A, r ∈ M , M |=“∃t(t ∈ A ∧ t ≤ r)” as well. Fix p0 ∈ M such that
M |= p0 ∈ A and p0 ≤ r. Note that this p0 is in fact in A, and extends r as a
function.
Since dom p0 is finite and in M , then dom p0 ⊆ M . So the only common domain
of p and p0 is dom r, on which they both agree. So p and p0 are compatible,
contradicting the assumption that A is an antichain. 
A collection F of sets is called a ∆-system if there is a set r such that for any
x, y ∈ F, x ∩ y = r.
Lemma 4.14 (The ∆-system lemma). Suppose F is a set of finite sets and F is
uncountable. Then there is a F 0 ⊆ F such that F 0 is uncountable and F 0 forms a
∆-system.
Exercise 4.15. (1) Prove the ∆-system lemma.
(2) Use the ∆-system lemma to prove that Pκ satisfies is c.c.c.
4.2. The precise size of the continuum. We have shown that in a generic
extension by Pκ , M [G] thinks that there are at least κ-many subsets of ω, and the
cardinals in M and in M [G] are the same. In particular, if κ = ω2M then M [G]
thinks “there are at least ℵ2 -many subsets of ω, and so CH fails. Next we show that
we did not add “too many” subsets of ω, and in this model in fact |P(ω)| = ℵ2 .
Lemma 4.16 (ZFC). Let M be a transitive model, (P, ≤) ∈ M , and G ⊆ P a
filter. The following are equivalent.
• G is generic over M ;
• For any maximal antichain A ⊆ P in M , G ∩ A 6= ∅.
Proof. Given a maximal antichain A ⊆ P, let DA be all p ∈ P with p ≤ a for some
a ∈ A. Then DA ⊆ P is dense: for any q ∈ P there is some a ∈ A with q k a. By
definition, there is some p ∈ P with p ≤ a and p ≤ q. So p ∈ DA .
Assume now G is generic and A ∈ M is a maximal antichain. Then DA ∈ M is
dense, so there is some p ∈ G ∩ DA . By definition, there is some a ∈ A with p ≤ a.
Therefore a ∈ G, and so G ∩ A 6= ∅.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 29

Assume now that the second clause holds and D ∈ M is some dense open set.
Let A ⊆ D be a maximal antichain. That is, A ⊆ D is an antichain and any p ∈ D
is compatible with some a ∈ A. (Such A exists by Zorn’s lemma.) We claim that
A is a maximal antichain in P. For any q ∈ P, there is some p ∈ D with p ≤ q.
It follows that p k a for some a ∈ A, and therefore q k a. Finally, by assumption
A ∩ G 6= ∅, so D ∩ G 6= ∅, as A ⊆ D. 
Given a formula φ(x1 , ..., xn ) and P-names τ1 , ..., τn , say that p ∈ P decides
φ(τ1 , ..., τn ) if either p φ(τ1 , ..., τn ) or p ¬φ(τ1 , ..., τn ). Recall that the set
Dφ(τ1 ,...,τn ) of all p ∈ P such that p decides φ(τ1 , ..., τn ) is dense and open in P.
So if A is a maximal antichain of conditions which decide φ(τ1 , ..., τn ), then A is
maximal in P.
Corollary 4.17. Let A ∈ M be a maximal antichain among all conditions that
force φ(τ1 , ..., τn ). If G is generic over M then
M [G] |= φ(τ1 [G], ..., τn [G]) ⇐⇒ G ∩ A 6= ∅.
Proof. The implication ⇐ is clear. For the other direction, note that there is some
p ∈ G which decides φ(τ1 , ..., τn ). So if G∩A = ∅, it must be that p ¬φ(τ1 , ..., τn ),
and so M [G] |= ¬φ(τ1 [G], ..., τn [G]). 
Theorem 4.18 (ZFC). Suppose λ ∈ M is a cardinal. In M : define F to be the
set of all functions f with dom f = λ and with the range of f being an antichain
in P. Then in M [G]
2λ ≤ |F |.
Note that the |F | above is calculated in M [G] and, as ordinals, |F |M [G] ≤ |F |M .
Proof. Say that a P-name τ is a simple name for a subset of λ if

• τ ⊆ P × β̌ : β < λ and
• for any β < λ the set Aβ of all p ∈ P with (p, β̌) ∈ τ , is an antichain in P.
Note that if τ is a simple name for a subset of λ then τ is in particular a canonical
name for a subset of λ̌, and τ [G] ⊆ λ for any filter G.
Given f ∈ F it corresponds to a simple name τ = (p, β̌) : p ∈ f (β) . Further-
more, any simple name for a subset of λ is of this form.
Claim 4.19. If G ⊆ P is generic over M , x ∈ M [G] is a subset of λ, then there is
a simple name τ such that x = τ [G].
Proof. Let x = σ[G]. For each β < λ, choose a maximal antichain Aβ among all
conditions that force β ∈ σ. Let τ = (p, β̌) : p ∈ Aβ .
As we have seen above, β ∈ x = σ[G] if and only if G ∩ Aβ 6= ∅. It follows that
x = τ [G]. 
In M there is a bijetion f 7→ τf between F and simple names for subsets of λ.
In M [G] the map f 7→ τf [G] is onto P(λ) and therefore 2λ ≤ |F |.

Let us go back to a generic extension M [G] of M by Pκ . Note that |Pκ | =
κ. Furthermore, Pκ satisfies the c.c.c., so there are at most |Pκ |ℵ0 = κℵ0 many
antichains in Pκ . Consider F as above with λ = ℵ0 . We conclude that, in M
|F | ≤ (κℵ0 )ℵ0 = κℵ0 ×ℵ0 = κℵ0 .
30 ASSAF SHANI

ℵ0
Suppose M satisfies CH and κ = ℵM 2 . Then in M , ℵ2 = ℵ2 . [Recall that
ℵ0
assuming CH, ℵ1 = ℵ1 . Now since any function from ω to ω2 is bounded below
ω2 , we get |ω2ω | ≤ | γ<ω2 γ ω | = γ<ω2 |γ|ℵ0 = γ<ω2 ℵℵ1 0 = γ<ω2 ℵ1 = ℵ2 .]
S P P P

Finally, |F | ≤ ℵ2 in M , and so |F | ≤ ℵ2 in M [G] as well. We conclude that

|2ℵ0 | = ℵ2 in M [G].
More generally:
Claim 4.20. Assume GCH. Then for any cardinal λ,
(
ℵ0 λ cfλ > ℵ0 ;
λ = +
λ cfλ = ℵ0 .

Proof. Note that if cfλ = ℵ0 then λ+ ≤ λℵ0 ≤ (2λ )ℵ0 = 2λ = λ+ , so the claim
follows. For λ with cfλ > ℵ0 We prove the claim by induction. If cfλ > ℵ0 then
any function from ω to λ is bounded below λ. Therefore
[ X
λℵ0 = |λω | = | γω | ≤ γ ℵ0 ≤ sup γ + ≤ λ.
γ<λ
γ<λ γ<λ

Assume now that M satisfies the GCH (for example, if M satisfies “V=L”). Let
κ be a cardinal in M such that cfκ > ω and G be generic over M for Pκ . Let F
be the set of all functions with domain ω whose range is an antichain in Pκ . Then,
in M , |F | = |(κω )ω | = κℵ0 = κ. Therefore in M [G], |F | ≤ κ. Finally, in M [G] we
conclude that 2ℵ0 ≥ κ and also that 2ℵ0 ≤ κ, and so 2ℵ0 = κ.
So for the value of the continuum can be any cardinal with cofinality > ω. This
is optimal, as cf2ℵ0 > ω.

5. A change of notation / perspective

As we noted many times, all the “action” in the forcing arguments happen in
the countable transitive model M . That is, the names are defined in M and forcing
relation is defined in M .
For example, we proved that after forcing with P = Pω2M we get a model with
the failure of CH. In other words, we proved that 1P ¬CH, and the latter holds
in M . The only place where we needed M to be a small countable model was to
find an actual generic filter. However, even in M , where such filters do not exists,
it knows that 1P ¬CH, so it knows about the consistency of the negation of CH.
In other words, M can “imagine” the world M [G] where ZFC+¬CH holds, even if
in M there are no means to construct such a model.
If we take P = Pω2 (in the universe V ), then we know that 1P ¬CH. Formally,
this can only be expressed in terms of the strong forcing relation. This time we
cannot find filters which are generic over V . However, we will imagine such filter
and consider the statement 1P ¬CH as “if G ⊆ P is a filter which is generic over
V , then CH fails in V [G]”. Similarly, we proved that 1P “the universe is not L”,
which we will now think of as “if G is generic over V , then in V [G] the “Axiom of
Constructibility” fails.
In practice, we will even go as far as saying “fix a filter G which is generic over
V ...” and go on to study the model V [G]. If one is ever worried about these issues,
at any point we can find a countable transitive model M which is sufficiently similar
 145B SET THEORY II: AN INTRODUCTION TO FORCING 31

to V (Σ1000 -elementary equivalent) and conclude for M [G] whatever we imagined

for V [G].
Sometimes we will force over different (non countable) models. For example,
we may say “let G be generic over L, and consider L[G]...” So instead of saying
“assuming M is a countable transitive model satisfying “V=L” ... then in M [G]
“V=L” fails”, we can say: in L[G] the axiom “V=L” fails. Also, instead of saying
“LM [G] = LM ”, we simply have LL[G] = L, and more generally LV [G] = L.

6. Independence of the Axiom of Choice

Next we proceed to construct a model of ZF where the axiom of choice fails,
show that the axiom of choice is independent of the axioms of ZF. This result
also appeared in Paul Cohen’s seminal paper where the method of forcing was
introduced.
Recall that if V satisfies ZFC, P is a poset in V and G ⊆ P is generic over V ,
then V [G] satisfies ZFC as well. So, unlike the axiom of constructibility, and the
size of the continuum, we cannot “force to change the value of AC”. Instead, we
will find intermediate models V ⊆ M ⊆ V [G] in which ZF holds yet the axiom of
choice fails.
This idea goes back to Fraenkel in the 1920’s. Very roughly speaking, Fraenkel’s
idea to find a model in which the axiom of choice fails was as follows. Fraenkel
considered a theory of “set theory with atoms”, ZFA. In this theory we assume
ZF, yet omit the axiom of extensionality. Moreoever, we stipulate the existence of
infinitely many “atoms”, a0 , a1 , .... These atoms have no members (so in ZF-terms
they look like the emptyset), yet are distinct. Finally, consider the unordered set
A = {ai : i ∈ ω} of these atoms, and let M be a model of all sets “definable from
A”. For example, we can take something like L(A) or HOD(A). The point is now
that a well ordering of the atoms cannot be recovered from the unordered set A
alone, as they all “look the same”.
While actual distinct sets can never be atoms, Cohen noticed that his “generic
subsets of ω” all look “sufficiently similar” to reproduce Fraenkel’s argument within
ZF.

6.1. The basic Cohen model. Let P = Pω be the poset of all finite functions
p : ω × ω → {0, 1}, where p ≤ q if p extends q as a function. Suppose G ⊆ P is a
generic filter (over V ). In V [G] we defined x(n) = {k ∈ ω : (∃p ∈ G)p(n, k) = 1}.
Let A = {x(n) : n ∈ ω}. Let ẋ be the name {(p, (n, k)) : (n, k) ∈ dom p ∧ p(n, k) = 1}
(so ẋ[G] = x), let ẋ(n) be the name {(p, k) : (n, k) ∈ dom p ∧ p(n, k) = 1} (so
ẋ(n)[G] = x(n), and let Ȧ be the name {(1P , ẋ(n)) : n ∈ ω} (so Ȧ[G] = A). Note
that 1P forces that Ȧ is the unordered set of subsets of ω which is enumerated by
ẋ.
The following automorphisms of P will be useful. Suppose π : ω → ω is a per-
mutation. We define an automorphism Π : P → P. For p ∈ P, define Π(p) ∈ P as
follows.
• (n, k) ∈ dom Π(p) ⇐⇒ (π −1 (n), k) ∈ dom p;
• Π(p)(n, k) = p(π −1 (n), k).
That is, Π permutes the ordering of x0 , x1 , ... according to π.
Exercise 6.1. Check that Π is an automorphism.
32 ASSAF SHANI

Note that if G ⊆ P is generic, its image G0 = Π[G] ⊆ P is generic, and

A = Ȧ[G] = Ȧ[G0 ]. Furthermore, for each m ∈ ω, ẋ(m)[G0 ] = ẋ(π −1 (m))[G] =
x(π −1 (m)).
Consider the model L(A), the minimal transitive model of ZF containing all the
ordinals and the set A. (We get L(A) by transfinite recursion where Lα+1 (A) is
the set of all subsets of Lα (A) which are definable over (Lα (A), ∈). The difference
with the usual L-construction is that instead of starting with L0 = ∅, we being
with L0 (A) = A.) We show that the axiom of choice fails in L(A). In fact it fails
in a very strong way.
Definition 6.2. Say that a set X is Dedeind-finite if there is no injective map
from ω to X. (That is, there are no infinite sequences in X.)
Recall that using the axiom of choice, a set is Dedekind-finite if and only if it is
finite. (Where a set is finite if and only if there is a bijection between it and some
member of ω.)
Theorem 6.3. In L(A), the set A is infinite and Dedekind-finite.
The proof relies on the fact that sets in L(A) are definable from A, and no
infinite sequence of members of A can be definable in such a way. It will be useful
to consider our generalization of ordinal definability.
Lemma 6.4. Suppose X is in L(A). Then there are finitely many x1 , ..., xn ∈ A,
finitely many ordinals α1 , ..., αk and a formula φ such that in L(A), X is the unique
set satisfying φ(X, A, a1 , ..., an , α1 , ..., αk ).
Equivalently, there is a ψ such that in L(A):
x ∈ X ⇐⇒ ψ(x, A, a1 , ..., an , α1 , ..., αk ).
Proof. Work in L(A), and consider the model HODL(A) (A). Recall that this is a
transitive model containing A and all of the ordinals. By minimality, it must be
equal to L(A). So any set in L(A) is in HODL(A) , which is precisely the statement
of the lemma. 

Proof of Theorem 6.3. Assume towards a contradiction that there is some f ∈ L(A)
such that f : ω → A is injective. Fix a formula φ, finitely many a1 , ..., an from A
and some v ∈ L such that in L(A):
f (n) = x ⇐⇒ φ(n, x, A, a1 , ..., an , v).
(v can be a finite sequence of ordinals.) Fix l1 , ..., lm ∈ ω such that ali = x(li ).
Since f is injective, there is some k such that f (k) 6= a1 , ..., an . Fix m such that
f (k) = x(m). Finally, fix a condition p ∈ G forcing that
φL(Ȧ) (k, ẋ(m), Ȧ, ẋ(l1 ), ..., ẋ(ln ), v̌).
(Technically we should also write ǩ, but we avoid that.) Given t ∈ ω, consider the
permutation π : ω → ω swapping m and t. This in turn gives us a permutation Π
of P and a generic Π[G].
We want to find such t so that p ∈ Π[G] as well (this is the only condition at
the moment which we know forces something interesting). This is possible since G
is generic. That is, for any N ∈ ω, the set of conditions q for which there is some
t ∈ ω such that for any k < N , q(m, k) = q(t, k), is a dense subset of P. Let N be
 145B SET THEORY II: AN INTRODUCTION TO FORCING 33

large enough such that for any k, (m, k) ∈ dom p =⇒ k < N . We may find q and
t ∈ ω as above with q ≤ p and q ∈ G.
Finally, we have G0 = Π[G] 3 p, as p ≥ Π(q). Working now in M [G0 ] we conclude
that
0
φL(Ȧ[G ]) (k, ẋ(t)[G0 ], Ȧ[G0 ], ẋ(l1 )[G0 ], ..., ẋ(ln )[G0 ]).
Recall that Ȧ[G0 ] = Ȧ[G] = A, ẋ(li )[G0 ] = ẋ[π −1 (li )][G] = ẋ[li ][G] = ai , and
ẋ(m)[G0 ] = ẋ(π −1 (m))[G] = ẋ(t)[G] = x(t). Thus in M [G0 ] we conclude:
φL(A) (k, x(t), A, a1 , ..., an )
and so in L(A), φ(k, x(t), A, a1 , ..., an ) holds. However, also φ(k, x(m), A, a1 , ..., an )
holds. This contradicts the fact that f , which is defined by φ(−, −, A, a1 , ..., an ), is
a function, since x(m) 6= x(t). 
Remark 6.5. In the proof above we showed that for any formula φ and for any
parameter v ∈ L, given distinct a, a1 , ..., an ∈ A, if φL(A) (A, v, a1 , ..., an , a) then
there are infinitely many a0 ∈ A such that φL(A) (A, v, a1 , ..., an , a0 ).
So the set A in L(A) is infinite, yet Dedekind-finite, and so the axiom of choice
fails in L(A).
Remark 6.6. L(A) satisfies the linear-ordering principle. That is, for any set X
there is some linear ordering of X.
6.2. Choice for socks. Recall Russell’s famous metaphor for the necessity of the
axiom of choice. Given an infinite sequence of pairs of shoes, it is easy to choose
one shoe out of each pair in a uniform manner, we simply choose the left shoe of of
each pair. However, given the same task with pairs of socks this time, we are left
with no way to distinguish between the two socks in each pair, and we need the
axiom of choice to find a way to choose one out of each pair.
We show next that the axiom of choice can indeed fail that badly. That is, there
could be a countable sequence of sets of size 2 without a choice function.
Let P be the poset of all finite partial functions p : dom p → {0, 1} where dom p is
a finite subset of ω ×(ω ×{0, 1}). Let G ⊆ P be a generic filter over V . For i ∈ {0, 1}
and n ∈ ω letai (n) = {k ∈ ω : (∃p ∈ G)p(n, k, i) = 1} (the “generic (n, i) column”).
Define Ain = ai (n)∆X : X ⊆ ω finite , where ∆ is the symmetric difference. That
is, Ain is the set of all subsets of ω which differ from a(n) only finitely.
Let An = {A0n , A1n }, and let A = hAn : n < ωi, the sequence of the sets An .
Finally, we consider the model L(A), the minimal transitive model of ZF which has
the set A as a member.
First note that our proof of Lemma 6.4 works in the following general context.
Lemma 6.7. Let N be some model of ZFC extending V . Let A be a transitive set
in N . Working in N form the relative constructible universe L(A).
Suppose X is in L(A). Then there are finitely many x1 , ..., xn ∈ A, finitely many
ordinals α1 , ..., αk and a formula φ such that in L(A), X is the unique set satisfying
φ(X, A, a1 , ..., an , α1 , ..., αk ).
Equivalently, there is a ψ such that in L(A):
x ∈ X ⇐⇒ ψ(x, A, a1 , ..., an , α1 , ..., αk ).
Proof. Work in L(A), and consider the model HODL(A) (A). Recall that since A is
transitive, this is a transitive model containing A as a set and all of the ordinals.
34 ASSAF SHANI

By the minimality of L(A), it must be equal to L(A). So any set in L(A) is in

HODL(A) , which is precisely the statement of the lemma. 
Q
Theorem 6.8. In L(A), n An is empty. That is, there is no choice sequence f
with domain ω such that f (n) ∈ An for each n ∈ ω.
By applying Lemma 6.7 to the transitive closure of A, we see that the members
of L(A) are all definable using A and members of the transitive closure of A. What
is in the transitive closure of A? Each set An is, each Ain , and each ai (n). Anything
else is simply definable from one of those (for example, a finite change of ai (n), or
{An }). Note that Ain is definable from ai (n), each An is definable from A, and A1n
is definable from A and A0n (as the only other member of An ), and vice versa.
As before, the proof of Theorem 6.8 relies on analysing definability questions in
L(A).
Proposition 6.9. Fix n ∈ ω, a formula φ, and v ∈ V . In L(A), for any k > n:
φ(A, a00 , a10 , ..., a0n , a1n , A0k , v) ⇐⇒ φ(A, A00 , ..., A0n , A1k , v).
Proof. We assume that φL(A) (A, a00 , a10 , ..., a0n , a1n , A0k , v) holds and show that φL(A) (A, a00 , a10 , ..., a0n , a1n , A1k , v)
holds as well. Fix names ȧim , Ȧim , Ȧm , Ȧ such that i i i i
 ȧm [G] = am , Ȧm [G] = Am ,
i
Ȧm [G] = Am , Ȧ[G] = A. For example, ȧ (n) = (p, ǩ) : p(n, k, i) = 1 . Fix a
L(Ȧ)
condition p ∈S P forcing that φ (Ȧ, ȧ00 , ȧ10 , ..., ȧ0n , ȧ1n , Ȧ0k , v̌).
Let f = G : ω × ω × {0, 1} → {0, 1}. Define f 0 : ω × ω × {0, 1} → {0, 1} by
f (k, m, 0) = f (k, m, 1) and f 0 (k, m, 1) = f (k, m, 0), and f 0 agrees with f otherwise.
0

0 0
S 6.10. There is a filter G ∈ V [G] such that G ⊆ P is generic over V and
Exercise
f 0 = G0 .
Then
• Ȧ1k [G0 ] = Ȧ0k [G] = A0k ;
• Ȧ0k [G0 ] = Ȧ1k [G] = A1k ;
• Ȧim [G0 ] = Ȧim [G] = Aim for m 6= k;
• Ȧm [G0 ] = Ȧm [G] = Am for all m < ω;
• Ȧ[G0 ] = Ȧ[G] = A.
Define now f˜ by f˜(l, m, i) = p(l, m, i) whenever (l, m, i) ∈ dom p, and f˜(l, m, i) =
f 0 (l, m, i) otherwise.
Exercise 6.11. There is a filter G̃ ∈ V [G] such that G̃ ⊆ P is generic over V and
f˜ = G̃. Furthermore, as f˜ extends p as a function, p is in G̃.
S

For each l, ȧil [G̃] and ȧil [G0 ] differ by only a finite amount, so
• Ȧil [G̃] = Ȧil [G0 ];
• Ȧ[G̃] = Ȧ[G0 ] = A.
Finally, since p is in the generic G̃, working in V [G̃] we conclude that
φL(Ȧ[G̃]) (Ȧ[G̃], ȧ00 [G̃], ȧ10 [G̃], ..., ȧ0n [G̃], ȧ1n [G̃], Ȧ0k [G̃], v̌[G̃])
holds, that is,
φL(A) (A, a00 , a10 , ..., a0n , a1n , A1k , v)
holds, as desired. 
 145B SET THEORY II: AN INTRODUCTION TO FORCING 35

Proof of Theorem 6.8. Suppose towards a contradiction that there is some f ∈

L(A) with dom f = ω and f (n) ∈ An for each n. There is some n, a formula φ and
v ∈ L such that f is defined in L(A) by
f (k) = Aik ⇐⇒ φ(k, Aik , A, a00 , a10 , ..., a0n , a1n , v).
Fix k > n, then we get from the previous proposition that f (k) = A0k ⇐⇒ f (k) =
A1k , contradicting that f is a function. 
Remark 6.12. About the names. We wrote above the name ȧin such that for
i
any
S generic G the name ȧn [G] is precisely the subset of ω defined by the function
G(n, −, i), and this was used to understand precisely how the names are realized
according to the other filters.
Given a finite set X ⊆ ω, you can write explicitly, in the same manner, a name
ȧin (X) such that for any G, ȧin (X)[G] = ȧin [G]∆X. (Exercise!) Now a good name
for Ȧin would be (1P , ȧin (X)) : X ⊆ ω finite .
We can also avoid worrying about the names for Ain and An . Simply, in any
statement above replace the set Ain by its definition using ain . So any statement
φ(Ain ) can be translated to a statement ψ(ain ), and we can then talk about forcing
this statement using the name ȧin .
More generally, if we have a name τ and we care about some object definable
from τ , we do not really need to worry about finding a name for this object. For
example, given a name τ , instead of fixing a different name σ such that σ is always
interpreted
S as the union of τ (we saw how to find such a name), we will simply
write τ instead of σ.

Remark 6.13. In L(A), there is no linear ordering of the set n<ω An = Ain : i ∈ {0, 1}, n ∈ ω .
S
Otherwise, we could have chosen “f (n) is the smaller among the two elements of
An ”.
Exercise 6.14 (ZF). For any ordinal η there is a total linear order on the set P(η).

7. Collapsing
Definition 7.1. Given cardinals κ ≤ λ. Let Col(κ, λ) be the poset of all functions
p : dom p → λ where dom p is a subset of κ of size < κ. Define p ≤ q if p extends q
as a function.
S
Exercise 7.2. If G ⊆ Col(κ, λ) is generic then in V [G], g G is a function from κ
onto λ.
Definition 7.3. Let κ be a cardinal. A poset (P, ≤) is called κ-closed if any
descending sequence of conditions of length less than κ has a lower bound. That
is, given ρ < κ and a sequence hpα : α < ρi of conditions pα ∈ P such that for
α < β < ρ, pβ ≤ pα , then there exists some condition p ∈ P such that p ≤ pα for
all α < ρ.
Say that (P, ≤) is σ-closed if it is ω1 -closed.
Example 7.4. Suppose κ is a regular cardinal, then Col(κ, λ) is κ-closed.
Proof.
S Given a descending sequence of conditions hpα : α < ρi for ρ < κ, let p =
α<ρ pα . Since the sequence is descending, any two conditions S
are compatible, and
so p is a well defined function from dom p to λ, where dom p = α<ρ dom pα . Since
36 ASSAF SHANI

κ is a regular cardinal, dom p has size < κ, as a union of < κ many sets of size
< κ. 

Lemma 7.5 (ZFC). Suppose (P, ≤) is ω1 -closed and G ⊆ P is generic. If f ∈ V [G]

is a function f : ω → θ, for some ordinal θ, then f ∈ V .
Proof. Suppose τ is a name in V such that τ [G] : ω → λ. We need to show that
τ [G] is a set in V already.
Fix a condition q ∈ P and suppose that q forces that τ is a function with domain
ω and it takes ordinal values. Define a sequence of conditions pn , n < ω such that
• p0 ≤ q and pn+1 ≤ pn ;
• there is an ordinal β such that pn τ (n) = β.
Since P is σ-closed, there is some condition p ∈ P such that p ≤ pn for each n < ω.
We showed that the set
D = {p ∈ P : ∀n ∈ ω∃β(p τ (n) = β ∨ p “τ is not a function...”}
is dense in P. Since G is generic there is some p ∈ D ∩ G. Since τ [G] is a function
with domain ω and ordinal values, p must satisfy the first option in the definition
of D.
Define in V a function h by h(n) = β if and only if p τ (n) = β. Then
h = τ [G] = f is in V , as required. 

Corollary 7.6 (ZFC). If P is σ-closed then no new subsets of ω are added when
forcing with P.
Corollary 7.7 (ZFC). If P is σ-closed then ω1 is not collapsed when forcing by P.
V [G]
That is, ω1V = ω1 for any generic filter G ⊆ P.
Similarly, if P is κ-closed then no cardinal ≤ κ is collapsed and no new subsets
of α are added for any α < κ.
Using collapsing we can give an alternative proof for the consistency of CH with
ZFC. Assume V is some model of ZFC, where CH might fail. Let κ = 2ℵ0 and
consider P = Col(ω1 , κ). Let G ⊆ P be a filter generic over V .
Since P is σ-closed, V [G] has no new subsets of ω. So in V [G] we have |P(ω)| = κ
(there is a bijection in V between P V (ω) and κ, and P V (ω) = P V [G] (ω)). Also, in
V [G], |κ| = ℵ1 , so 2ℵ0 = ℵ1 .

8. Mutual genericity
Lemma 8.1. Suppose M ⊆ N are transitive models of ZF. Let P be a poset in M ,
and suppose G ⊆ P is generic over N . Then M [G] ∩ N = M .
Remark 8.2. Note that in this situation G ⊆ P is generic over M as well. Note
however that forcing with P over M and over N can be very different. For example,
if P is σ-closed in M it is not necesarily so in N , and if P is c.c.c. in M it is not
necessarily so in N .
Proof. First note that for any name τ ∈ M , and any filter H ⊆ P generic over
N , τ [H] is the same as calculated over M or over N . Also, for any x ∈ M , the
canonical name x̌ is the same as calculated in M or in N .
 145B SET THEORY II: AN INTRODUCTION TO FORCING 37

Fix a P-name τ in M , and suppose that τ [G] is in N . Assume first that τ [G] ⊆
VαM for some ordinal α in M . Fix X ∈ N with τ [G] = X. Note that τ is a P-name
in N as well. By the forcing theorem (applied in N ), there is some p ∈ G such that
N |= p τ = X̌.
Define in M
X 0 = {x ∈ Vα : p x̌ ∈ τ } .
0
Then X is in M by comprehension, and the definability of forcing. We claim that
X 0 = X.
First note that for p ∈ P and x ∈ M ,
M |= p x̌ ∈ τ ⇐⇒ N |= p x̌ ∈ τ.
The =⇒ direction is clear, as any filter generic over N is generic over M as well.
For the reverse direction, recall that p φ if and only if there is no q ≤ p forcing
¬φ. Now, if M |= p 6 x̌ ∈ τ , then there is some q ≤ p such that M |= q x̌ ∈ / τ.
By the previous argument it follows that N |= q x̌ ∈ / τ . So N |= p 6 x̌ ∈ τ as
well.
Finally, since in N , p τ = X̌, we see that in N , for any x, p x̌ ∈ τ ⇐⇒ x ∈
X. Therefore this is true in M as well, and we conclude that X 0 = X.
To deal with the assumption that X ⊆ VαM for some α: the proof is carried
by induction on the rank of τ . Assume that for any σ of rank smaller than τ , if
σ[G] ∈ N then σ[G] ∈ M . Then if τ [G] ∈ N is of rank α, it follows from the
inductive assumption that τ [G] ⊆ VαM , and we are done. 

Corollary 8.3. Suppose P and Q are posets in V and K ⊆ P × Q is generic over

V . As we have seen in the homework, K = G × H where H is Q-generic over V [G]
and G is P-generic over V [H]. Then V [G] ∩ V [H] = V .
Proof. Apply Lemma 8.1 with M = V and N = V [G]. 

9. The Feferman-Levy model

We will now construct a model with the following extreme failure of the axiom
of choice: the cofinality of ω1 is ω, and in fact P(ω) can be written as a countable
union of countable sets.
Define P as the poset of all partial functions p : dom p → ℵω such that dom p ⊆
ω × ω is finite and for all (n, k) ∈ dom p, p(n, k) ∈ ℵn . S
Let G ⊆ P be a generic filter over V . Define f = G, and fn : ω → ℵVn by
fn (k) = f (n, k).
Exercise 9.1. Each fn is onto ℵVn .
In L[G], each ℵVn , and also ℵVω , are countable ordinals. We will find a submodel
L(A) in which each ℵVn is countable, yet it does not “see” any countable enumeration
of ℵVω . Thus in this model ℵVω will be the smallest uncountable cardinal, that is,
ω1 .
Let f, g be two functions from ω to κ. Say that f and g are similar if there are
only finitely many m ∈ ω for which f (m) 6= g(m).
For f : ω → κ, define
[f ] = {g : g : ω → κ is similar to f } .
38 ASSAF SHANI


Back to our model L[G], define An = [fn ] = g : ω → ℵVn : g is similar to f ,
and A = hAn : n < ωi. The model of interest will be L(A).
• For n < ω and a finite function t : m → ℵn , define f˙t to be all pairs
n
(p, (ǩ, α̌)) such that either k ≥ m and p(n, k) = α or k < m and t(k) = α.
Let f˙n = f˙nt where t is the empty function. Then f˙n [G] = fn and f˙nt [G] is
the finite
n change of fn accordingo to t.
˙t
• Ȧn = (1P , fn ) : t ∈ (ℵn ) <ω
. Then Ȧn [G] = An .
n o
• Ȧ = (1P , (ň, Ȧn )) : n < ω . Then Ȧ[G] = A.
(Above when we write (ň, Ȧn ) we mean a name σ such that σ[H] = (n, Ȧn [H]) for
any filter H.)
The following automorphisms of P will be crucial for the analysis of L(A). Given
two functions t, s : m → ℵn , define a = an (t, s) : P → P by sending p to a(p) where
• dom a(p) = dom p,
• if p(n, i) = t(i) then a(p)(n, i) = s(i), and if p(n, i) = s(i) then a(p)(n, i) =
t(i),
• otherwise a(p)(n, i) = p(n, i),
• for n0 6= n, a(p)(n0 , j) = p(m0 , j).
Exercise 9.2. Show that a is an automorphism of P. Furthermore, if G is generic
over L and G0 = a[G]. Then
• f˙m [G0 ] is similar to f˙n [G] = fn .
• f˙m [G0 ] = f˙m [G] = fn if m 6= n;
• Ȧm [G0 ] = Ȧm [G] = Am for all m;
• Ȧ[G0 ] = Ȧ[G] = A.
We will also apply automorphisms which change finitely many fn ’s. This can
be done by composing the an (t, s)’s. Given t1 , s1 , ..., tk , sk and n1 , ..., nk , then
a = ank (tk , sk ) ◦ ... ◦ an1 (t1 , s1 ) is an automorphism of P. By applying this a we
only change fn when n is one of n1 , ..., nk and all Am ’s are preserved, as well as A.
For m < ω, let P<m be the set of all p ∈ P whose domain is contained in
m × ω = {0, ..., m − 1} × ω. Let P≥m be the set of all p ∈ P whose domain is
contained in (ω \ m) × ω = {m, m + 1, ...} × ω. Given p ∈ P let p<m be the
restriction of p to m × ω and let p≥m be the restriction of p to (ω \ m) × ω.
Exercise 9.3. The map P → P<m × P≥m sending p to (p<m , p≥m ) is an isomor-
phism.
Given G ⊆ P generic over L, let G<m = G ∩ P<m and G≥m = G ∩ P≥m . Then
G<m ⊆ P<m is generic over L and G≥m ⊆ P≥m is generic over L[G<m ].
Note that |P<m | = ℵm−1 .
Proposition 9.4. Suppose g ∈ L(A), g : λ → θ where λ and θ are ordinals. Assume
further g is definable as
g(α) = β ⇐⇒ φL(A) (α, β, A, f0 , ..., fm−1 , v),
where v ∈ L. Then g ∈ L[G<m ].
Before proving the proposition, let us see how to deduce the main result from it.
Theorem 9.5. In the model L(A):
 145B SET THEORY II: AN INTRODUCTION TO FORCING 39

(1) ω1 has cofinality ω. In fact, ω1 is ℵL

ω;
(2) P(ω) is a countable union of countable sets.
Proof. For (1), note first that each of the cardinals ℵL n are in fact countable in
L(A), so it suffices to prove that ℵLω is not countable in L(A). Indeed, suppose for a
contradiction that g : ω → ℵL ω were a surjective map in L(A). Then g can be defined
in L(A) using A, finitely many f0 , ..., fm−1 , and ordinals. By Proposition 9.4 we
conclude that g ∈ L[G<m ]. However, L[G<m ] is a P<m -generic extension of L.
Working in L: P<m satisfies the ℵm -c.c. (as |P<m | < ℵm ). So ℵL L L
m , ℵm+1 , ..., ℵω
must remain cardinals in L[G<ω ], and therefore cannot be countable.
Next we prove part (2). As usual, we identify P(ω) with 2ω , all functions from
ω to {0, 1}. So by Proposition 9.4 every x ∈ P(ω) is in L[G<m ] for some m < ω.
Let Xm be the set of all x ∈ P(ω) with x ∈ L(G<m ). (Equivalently, the set of all
x ∈ L(hAi : i < mi) ∩ P(ω).)
Note that the sequence hXn : n < ωi is in L(A), by an application of compre-
hension. (We use the fact that we have a single formula defining when Y = Lβ (B).)
Finally, what is the size of L[G<m ]∩P(ω)? It is bounded below ℵℵm0 , as calculated
in L. (The number of functions from ω to antichains in P.) Since L satisfies the
GCH, ℵℵm0 = ℵm (for m > 0). So in L[G<m ], |Xm | ≤ ℵL m . In L[G] however, ℵm is
L

countable, so Xm is countable. S
Finally, in L(A), P(ω) = m<ω Xm is a countable union of countable sets. 

The proof of the proposition relies on the following key lemma.

Lemma 9.6. Let φ be a formula, v ∈ V and p ∈ P such that
p φL(Ȧ) (Ȧ, v̌, f˙0 , ...f˙m−1 ).
Then
(1) p<m φL(Ȧ) (Ȧ, v̌, f˙0 , ...f˙m−1 ).
(Note that both forcing relations above are referring to the poset P. We
consider in this lemma p<m as a condition in P.)

Proof. It suffices to show that for any q ∈ P, if q ≤ p<m , then q does not force
¬φL(Ȧ) (Ȧ, v̌, f˙0 , ...f˙m−1 ). Assume towards a contradiction that q is such a condition.
Assume both q and p have domains contained in l×ω, l > m. For each m ≤ n < l,
let tn (i) = p(n, i) and sn (i) = q(n, i). Consider the automorphism a of P which is
the composition of an (tn , sn ) for m ≤ n < l.
Now take a generic H ⊆ P which contains the condition q. The automorphism a
was chosen precisely so that p is in the generic filter a[H]. Now, working in V [H]
we get
¬φL(A) (A, v, f0 , ..., fm−1 ),
as it is forced by q. On the other hand, in M [a[H]] we conclude
φL(A) (A, v, f0 , ..., fm−1 ),
as p forces this. A contradiction! 

Proof of Proposition 9.4. Suppose g ∈ L(A), g : λ → θ is defined in L(A) by

g(α) = β ⇐⇒ φL(A) (α, β, A, f0 , ..., fm−1 , v).
40 ASSAF SHANI

By the previous lemma, for any α, β and any p ∈ P,

p φL(Ȧ) (α̌, β̌, Ȧ, f˙0 , ..., f˙m−1 , v̌) ⇐⇒ p<m φL(Ȧ) (α̌, β̌, Ȧ, f˙0 , ..., f˙m−1 , v̌).
In other words, g(α) = β if and only if there is p ∈ G forcing φL(Ȧ) (α̌, β̌, Ȧ, f˙0 , ..., f˙m−1 , v̌),
if and only if there is p ∈ G such that p<m forces φL(Ȧ) (α̌, β̌, Ȧ, f˙0 , ..., f˙m−1 , v̌), if
and only if there some q ∈ G<m forcing φL(Ȧ) (α̌, β̌, Ȧ, f˙0 , ..., f˙m−1 , v̌). Note that
the final statement can be defined in L[G<m ], where we have G<m and the forcing
relation P is definable (in L).
That is, we may define a function g 0 in L[G<m ] by
g 0 (α) = β ⇐⇒ ∃(q ∈ G<m )q φL(Ȧ) (α̌, β̌, Ȧ, f˙0 , ..., f˙m−1 , v̌),
and we see that g 0 = g. 

10. Sacks forcing: a minimal extension

Let P be the Cohen poset for adding a single subset
S of ω. Given a generic filter
G ⊆ P over V , let a ⊆ ω be the subset of ω where G is the characteristic function
of a. Recall that V [G] is the minimal transitive model of ZF which extends V and
contains G as a set. G and a can be simply defined from one another, and we will
often denote V [G] as V [a], the minimal transitive extension of V containing a as a
set.
Consider the map f : P × P → P defined as follows.
(
p(k) n = 2k & k ∈ dom p;
f (p, q)(n) =
q(k) n = 2k + 1 & k ∈ dom q.
(In particular, n ∈ dom f (p, q) if and only if either n = 2k and k ∈ dom p or
n = 2k + 1 and k ∈ dom q.
Exercise 10.1. f is an isomorphism between P × P and P.
So if G ⊆ P is generic over V , then f −1 [G] = K × H ⊆ P × P is generic over
V and is in V [G]. Let a, b, c be the subsets of ω corresponding to G, K, H. Then
b, c ∈ V [a] yet c ∈
/ V [b] and b ∈
/ V [c] (recall that H is generic over V [K] and K is
generic over V [H]).
Let us take V = L now. Then the question if whether or not b ∈ L[c] can be seen
as whether b is constructible relative to c. Say that b and c have the same degree of
constructibility if L[b] = L[c]. Inside the extension L[a], where a is a Cohen generic
subset of ω, there are many different degrees of constructibility.
We will now consider a very different poset, such that after forcing with it we will
add a minimal degree a ⊆ ω. That is, if b ∈ L[a] then either b ∈ L or L[a] = L[b].
Let 2<ω be the set of all finite binary sequences, that is, all functions t : n →
{0, 1} for some n ∈ ω. We think of 2<ω as a tree, with root ∅ =<>, which then
splits to < 0 > and < 1 >, and each < i > splits to < i0 > and < i1 > and so on..
each node t ∈ 2<ω splits to t_ 0 and t_ 1. (Here _ is concatenation of sequences.)
For t ∈ 2<ω let l(t) = dom(t) be the length of t. (See Figure 1.)
Say that T ⊆ 2<ω is a tree (a subtree of 2<ω ) if for any t ∈ T for any k < l(t),
t  k is in T as well (T is “downwards closed”). [We will usually assume that T is
not empty, and therefore ∅ ∈ T .] Say that a node t ∈ T is splitting (in T ) if both
t_ 0 and t_ 1 are in T . Say that a tree T is perfect if for any t ∈ T there is some
u ∈ T such that u is splitting in T . (See Figure 2.)
 145B SET THEORY II: AN INTRODUCTION TO FORCING 41

Figure 1. 2<ω

Figure 2. A perfect tree with stem = < 1 >

The stem of a tree T is the unique t ∈ T such that t is splitting in t yet t  k is

not splitting for any k < l(t). Note that if T1 , T2 are trees and T1 is contained in
T2 then the stem of T1 extends the stem of T2 .
42 ASSAF SHANI

Definition 10.2. Sacks forcing S is the poset of all non-empty perfect trees in 2<ω ,
where T1 ≤ T2 if T1 ⊆ T2 . (A smaller tree gives more information which gives a
stronger condition.)
For T ∈ S and t ∈ T let Tt be the subset of T containing all u ∈ T such that u
either extends t or t extends u. Note that the stem of Tt extends t.
Remark 10.3. We have been working a lot with the set 2ω of all functions from
ω to {0, 1}. We identify this with all subsets of ω. This can also be identified with
the “Cantor set” in R. For a tree T ⊆ 2<ω let [T ] be all f ∈ 2ω such that f  n ∈ T
for all n < ω. Then the closed sets in 2ω are precisely those of the form [T ] for
some tree T , and the perfect sets are those of the form [T ] for a perfect tree T .
Proposition 10.4. Suppose G ⊆ S is generic over V . Define f as the union of all
the stems of the trees in G. Then f : ω → {0, 1} is a well defined function, and
f∈/ V.
Proof. First, since G is a filter, f takes at most one value at each n ∈ ω. Next we
show that each n ∈ ω is in the domain of f . Consider the set Dn of all T ∈ S such
that the length of the stem of T is > n. Each Dn is dense and therefore there is
some T in G whose stem is defined on n. Finally, fix h : ω → {0, 1} in V . Let D be
the set of all T in S such that for the stem s of T there is k < l(s) with s(k) 6= h(k).
Then D is dense, and so there is some k for which f (k) 6= s(k). 
Let G ⊆ S be generic over L.
Lemma 10.5. L[G] = L[f ], the minimal transitive extension of V containing f .
Proof. We need to show that G is in V [f ]. In fact, it can be defined as G =

T ∈ SV : f ∈ [T ] . The inclusion ⊆ is immediate. For the other direction, assume
that T ∈ V is such that f ∈ [T ].
Exercise 10.6. Show that for T, U in S, if U is not contained in T then there is a
U 0 ≤ U such that U ∩ T is finite. (This implies that [U ] ∩ [T ] = ∅.)
Working now in V , it follows that the set of U ∈ S such that either U ≤ T or
U ∩ T is finite is dense in S (and is in V ). So there is such a U in G. Since f ∈ [U ]
and f ∈ [T ], it cannot be that U ∩ T is finite, therefore U ≤ T , and so T ∈ G as
well. 
Remark 10.7. Generally speaking, for T ∈ V the sets of branches [T ] as computed
in V or V [G] could be very different. For example, of T = 2<ω is the full binary
tree, then [T ] is 2ω , which is different in V and V [G].
However, if T ∩ U is finite, then [T ] ∩ [U ] is empty in V and in any generic
extension.
Say that t ∈ T is an n’th splitting node of T if there are precisely n splitting
node among {t  k : k ≤ l(t)}.
Lemma 10.8 (Fusion). Suppose T0 , T1 , T2 ,... is a sequence of perfect tress such
that
• Tn+1 ⊆ Tn
• The n + 1’th splitting nodes of Tn are n + 1’th splitting nodes of Tn+1 .
T
Then T = Tn is a perfect tree.
 145B SET THEORY II: AN INTRODUCTION TO FORCING 43

Figure 3. Fusion

Proof. Take t ∈ T . Let m be the number of nodes of the form t  k which are
splitting nodes of T . Now t is a member of Tm . Since Tm is a perfect tree, we may
find t0 above t which is splitting, and is an m-splitting node of Tm . By construction,
t0 is an m-splitting node of each Tm0 , m0 > m. That is, both t0_ 0 and t0_ 1 are in
Tm0 for each m0 , and so they are in T . Therefore t0 is a splitting node of T . 

Theorem 10.9. Suppose X ∈ L[G], X ⊆ η for some ordinal η, then either X ∈ L

or L[X] = L[G].
Proof. Let τ be a name with τ [G] = X. Assume that X ∈ / L and fix some condition
T0 forcing that τ is not in L (that is, τ ∈ ˇ . Note that for any condition T ≤ T0 ,
/ Vη+1
there must be some ζ < η for which T does not force either ζ̌ ∈ τ nor ζ̌ 6∈ τ .
[Otherwise, we could define X in V by ζ ∈ X ⇐⇒ T ζ̌ ∈ τ .] In this case we
may find extensions of T forcing either statement.
We now work in L. We will find a single tree in L such that going “left or right”
will decide different statements about members of X = τ [G]. We will therefore be
able to “decode” the function f from X.
Let ζ0 be the minimal such that T0 does not decide if ζ0 ∈ τ . Let s be the stem
of T0 .
Consider (T0 )s_ 0 and (T0 )s_ 1 . It cannot be the case that they both force ζ0 ∈ τ .
Since the set of conditions S ∈ S such that S is either below (T0 )s_ 0 or (T0 )s_ 1 , is
dense in S, below T0 . So this would imply that all extensions of T0 force the same
44 ASSAF SHANI

value for “ζ0 ∈ τ ”, and therefore T0 would force this. Similarly, it cannot be the
case that they both force ζ0 ∈ / τ.
It follows that there are trees U0 and U1 such that Ui ≤ (T0 )s_ i , and such that
one of U0 , U1 forces ζ0 ∈ τ and the other forces ζ0 ∈ / τ.
Now define T1 by T1 = U0 ∪ U1 . Note that Ts_ i = Ui . Furthermore, T1 and T0
have the same stem s (the same 1-splitting node).
For each Ui , i = 0, 1, we apply the same process: let ζ be the minimal such that
Ui does not decide ζ ∈ τ . Let si be the stem of ui (note that si is a 2-splitting
node of T1 ).
We may find Ui0 ≤ Ui such that Ui0 and Ui have the same stem si and if s, t are
the two 2-splitting nodes of Ui0 , then one of (Ui0 )s , (Ui0 )t forces ζ ∈ τ and the other
forces ζ ∈ / τ.
Now let T2 = U10 ∪ U20 . Then T2 and T1 have the same 2-splitting nodes (the
1-splitting nodes of U00 and U10 ).
For the general construction: assume we arrived at Tm . For each m + 1-splitting
node t of Tm , let U = (Tm )t . Find U00 , U10 two extensions of Ut_ 0 and US t_ 1 which
force conflicting statements of ζ ∈ τ , for some ordinal ζ < η. Let Ut0 = U00 ∪ U10 .
Then Ut0 is an extension of (Tm )t , with the same stem t. Finally, let Tm+1 be the
union of all these Ut0 , where t is ranging over all m + 1-splitting nodes of TmT .
The sequence T0 ⊃ T1 ⊃ T2 ⊃ ... is a fusion sequence, and therefore T = n Tn
is a perfect tree. Also T ≤ T0 .
In conclusion: we showed that the set of all trees T satisfying the following
condition is dense in S: for any splitting node t of T there is some ordinal ζ < η
such that Tt_ 0 and Tt_ 1 decide conflicting statements about “ζ ∈ τ ”.
Since G is generic, there is a tree T ∈ G is above. We can now define f from
the set X = τ [G] as follows. First f extends the stem of T , t0 . There is some ζ
such that Tt_ 0 i
force conflicting information about ζ ∈ τ . Choose the unique i such
that Tt_ 0 i ζ ∈ τ ⇐⇒ ζ ∈ X. LetSt1 be the next splitting node of T above t_ 0 i.
Continue this way, and define f = n tn . Therefore f is in L[X]. By Lemma 10.5
it follows that G is in L[X], and therefore L[G] ⊆ L[X].