Forcing and the Continuum Hypothesis

Forcing and the Continuum Hypothesis
Daniel Naylor

1The Continuum Hypothesis
2Transitive Models
2.1Absoluteness for transitive models
2.2Non-absoluteness
2.3The constructible hierarchy
3Forcing
3.1Cohen Forcing
Index

1 The Continuum Hypothesis

1398: Gödel showed $Con (ZFC) ⟹ Con (ZFC + CH)$ .

1962: Cohen showed $Con (ZFC) ⟹ Con (ZFC + \neg CH)$ .

Theorem (Hartogs’s Theorem). For every set $X$ , there is a (least) cardinal $α$ such that there is no injection from $α$ to $X$ .

We denote this by Hartogs’s aleph of $X$ , $ℵ (X)$ .

Theorem. For every set $X$ , there is no injection from $P (X)$ into $X$ . We denote this by $2^{| X |}$ .

Using Axiom of Choice, well-order $P (X)$ and get ordinal $2^{| X |}$ .

We have

ℵ (X) \leq 2^{| X |} .

Notation. Define:

\begin{array}{l} ℵ_{0} & : = ℕ \\ ℵ_{α + 1} & : = ℵ (ℵ_{α}) \\ ℵ_{λ} & : = ⋃_{α < λ} ℵ_{α} \\ ℶ_{0} & = ℕ \\ ℶ_{α + 1} & = 2^{ℶ_{α}} \\ ℶ_{λ} & = ⋃_{α < λ} ℶ_{α} \end{array}

Clearly, $ℵ_{α} \leq ℶ_{α}$ .

Continuum Hypothesis (CH): $ℵ_{1} = ℶ_{1}$ .

Generalised Continuum Hypothesis (GCH): $\forall α ℵ_{α} = ℶ_{α}$ .

Why “continuum”?

Lemma. CH if and only if $\forall X \subseteq ℝ$ , $X$ is uncountable $⟹$ $X \sim ℝ$ ( $\sim$ means “there is a bijection”).

Proof.

$\Rightarrow$ Obvious since $ℶ_{1} = | ℝ |$ .
$\Leftarrow$ Suppose $| ℝ | > ℵ_{1}$ . Well-order the reals in order type $κ > ℵ_{1}$ :
${r_{α} : α < κ} .$

Consider $X : = {r_{α} : α < w_{1}} \subseteq ℝ$ . This is a subset of the reals of cardinality $ℵ_{1}$ , hence is an uncountable subset which is not in bijection with it. □

Reminder:

Gödel showed $Con (ZFC) ⟹ Con (ZFC + CH)$ .

Cohen showed $Con (ZFC) ⟹ Con (ZFC + \neg CH)$ .

Relative consistency proofs.

By Completeness Theorem, this means:

If there is $M ⊨ ZFC$ , then I can construct $N ⊨ ZFC + (\neg) CH$ .

Analogy from algebra:

L_{fields} = {0, 1, +, \cdot, -,^{- 1}} .

Axioms of fields: Fields.

Let $φ_{\sqrt{2}} : = \exists x (x \cdot x = 1 + 1)$ . Note $ℚ ⊨ \neg φ_{\sqrt{2}}$ .

Idea: Start with $ℚ$ and extend $ℚ$ to get $F ⊨ Fields + φ_{\sqrt{2}}$ .

Construct by algebraic closure (not in the usual sense – here we just mean adding in $\sqrt{2}$ and then adding everything else that this requires us to add).

Obtain $ℚ (\sqrt{2}) ⊨ Fields + φ_{\sqrt{2}}$ .

This is easy because everything that matters (Fields and $φ_{\sqrt{2}}$ ) is determined by equations; all formulas we need to check are atomic.

Definition 1.1 (absolute). If $M \subseteq N$ and $M, N$ are $L$ -structures and $φ$ an $L$ -formula, then we say $φ$ is absolute between $M$ and $N$ if for all $x_{1}, \dots, x_{m} \in M$ ,

M ⊨ φ (x_{1}, \dots, x_{n}) ⟺ N ⊨ φ (x_{1}, \dots, x_{n}) .

If the $\Rightarrow$ direction holds, then we say “upwards absolute”, and if the $\Leftarrow$ direction holds, then we say “downwards absolute”.

Theorem (Substructure Lemma). All atomic formulas are absolute between substructures.

WHat if we have models of ZFC? Have

L_{\in} = {\in} .

No function symbols nor constant symbols. So: almost nothing is atomic.

$M \subseteq N$ if and only if $M$ is an $L_{\in}$ -substructure of $N$ .

And: the formulas that we care about are definitely not atomic, but instead very complex.

Try to imagine a proof of:

If $M ⊨ ZFC$ then there is $N \supseteq M$ such that $N ⊨ ZFC + CH$ .

Without loss of generality $M ⊨ \neg CH$ (else we are done). For simplicity, let’s consider the case $ℶ_{1} = ℵ_{2}$ .

What can we do to “get rid of $ℵ_{1}$ ”?

Maybe a surjection $f : ℕ \to ℵ_{1}$ . Maybe we can form $M [f] \supseteq M$ to get a smallest model $M [f] ⊨ ZFC$ .

Clearly, in $M [f]$ , $ℵ_{1}^{M}$ is not a cardinal anymore.

Does that show CH?

All sorts of things can happen

Assuming it is actually possible to form this smallest model $M [f]$ , there are lots of ways that this might not end up being enough to deduce CH. For example:

Maybe $ℝ^{M [f]} \neq ℝ^{M}$
Maybe $ℵ_{2}^{M}$ is not a cardinal either

A fundamental problem of non-absoluteness

Consider $φ_{\emptyset} (x) : = \forall z (z \notin x)$ , which means “ $x$ is empty”.

Consider $M ⊨ ZFC$ . Therefore there are $e, e^{'}$ such that $M ⊨ φ_{\emptyset} (e)$ and $M ⊨ \forall z (z \in e^{'} ⟺ z = e)$ .

Consider $N : = M ∖ {e}$ .

$N$ is an $L_{\in}$ -substructure of $M$ . But $N ⊨ φ_{\emptyset} (e^{'})$ , even though $M ⊨ \neg φ_{\emptyset} (e^{'})$ .

So $φ_{\emptyset}$ is not absolute between substructures.

Instead of substructures, we will restrict out attention to transitive substructures: in particular, to $M$ transitive ( $\forall x, x \in M ⟹ x \subseteq M$ or equivalently $x \in M \land y \in x ⟹ y \in M$ ) such that $M ⊨ ZFC$ .

Next time: theorems about absoluteness for transitive substructures.

Definition (Absolute formula). We say $φ$ is absolute for $M$ if for all $x_{1}, \dots, x_{n} \in M$ , we have

M ⊨ φ (x_{1}, \dots, x_{n}) ⟺ φ (x_{1}, \dots, x_{n}) is true .

Clearly, if $φ$ is absolute for $M$ and absolute for $N$ , then it’s absolute between $M$ and $N$ .

Cohen’s proof becomes:

If $M$ is a countable transitive set such that $M ⊨ ZFC$ , then there is a a countable transitive set $N \supseteq M$ such that $N ⊨ ZFC + \neg CH$ .

2 Transitive Models

Observation: If $M$ is transitive and $M ⊨ “ e is empty”$ , then $e = \emptyset$ . This is because if $w \in e$ , then $w \in e$ and $e \in M$ gives us that $w \in M$ by transitivity, so $M ⊨ w \in e$ , so $M ⊨ “ e is not empty”$ .

Lemma. Assuming that:

$M$ is transitive

Then

M ⊨ Extensionality + Foundation .

Proof. Extensionality: $\forall x \forall y (\forall w (w \in x \leftrightarrow w \in y) \to x = y)$ . Take $x \neq y$ , $x, y \in M$ . Without loss of generality take $z \in x ∖ y$ . Then $z \in x$ and $x \in M$ so $z \in M$ . So $M ⊨ z \in x \land z \notin y$ . So $M ⊨ \neg \forall w (w \in x \leftrightarrow w \in y)$ .

Foundation: $\forall x (x \neq \emptyset \to \exists m (m \in x \land \forall w \neg (w \in m \land w \in x)))$ . Take $x \in M$ . $M ⊨ x \neq \emptyset$ so $x$ is not empty. So find $m \in x$ which is $\in$ -minimal. Then since $x \in M$ as well, we have $m \in M$ . Therefore $x$ has an $\in$ -minimal element in $M$ . □

2.1 Absoluteness for transitive models

Definition (Bounded quantifier). We call a quantifier of the form $\exists x \in y, φ$ or $\forall x \in y, φ$ a bounded quantifier.

(Defined by $\exists x \in y, φ : = \exists x (x \in y \land φ)$ and $\forall x \in y φ : = \forall x (x \in y \to φ)$ ).

Definition (Closed under bounded quantification). A class of formulas $Γ$ is closed under bounded quantification if whenever $φ$ is in $Γ$ , then so are $\exists x \in y, φ$ and $\forall x \in y, φ$ .

Definition (Delta0). $Δ_{0}$ is the smallest class of formulas containing the atomic formulas that is closed under propositional connectives and bounded quantifiers.

Let $T$ be any theory. Then $Δ_{0}^{T}$ is the class of formulas equivalent to a $Δ_{0}$ formula in $T$ .

Theorem. $Δ_{0}$ formulas are absolute for transitive models.

Proof. By induction:

(1) All atomic formulas are absolute by the substructure lemma.
(2) Propositional connectives: exactly the same proof as in the substructure lemma.
(3) Assume that $φ$ is absolute and show that $\exists x \in y, φ$ and $\forall x \in y, φ$ are absolute.
- $\exists x \in y, φ$ : If $\exists x \in y, φ$ is true for some $y \in M$ , then pick a witness $x \in y$ . Since $y \in M$ , we have $x \in M$ . By the induction hypothesis, we have that $M ⊨ φ (x, y)$ . Thus $M ⊨ \exists x (x \in y \land φ (x, y))$ .
  
  If $M ⊨ \exists x (x \in y \land φ (x, y))$ , then $x \in y \land φ (x, y)$ is true.
- $\forall x \in y, φ$ : Similar. □

Corollary. Assuming that:

$T$ is any theory
$M ⊨ T$ is transitive

Then

Δ_{0}^{T}

-formulas are absolute for

M

Definition ( $S i g m a 1$ , $P i 1$ ). A formula is called $Σ_{1}$ if it is of the form $\exists x_{1}, \dots \exists x_{n}, φ$ where $φ$ is $Δ_{0}$ .

It is called $Π_{1}$ if it is of the form $\forall x_{1}, \dots, \forall x_{n}, φ$ where $φ$ is $Δ_{0}$ .

(same for $Σ_{1}^{T}$ , $Π_{1}^{T}$ ).

Proof. Just definition of the semantics of $\exists, \forall$ . □

Example. What is $Δ_{0}$ ?

1. $x \in y$
2. $x = y$
3. $x \subseteq y$ : $⟺ \forall w \in x (w \in y)$
4. $z = {x}$ : $⟺ x \in z \land \forall w \in z (w = x)$
5. $z = {x, y}$
6. $z = (x, y) = {{x}, {x, y}}$
7. $z = \emptyset$ : $⟺ \forall w \in z (w \neq w)$
8. $z = x \cup y$ : $⟺ x \subseteq z \land y \subseteq z \land \forall w \in z (w \in x \lor w \in y)$
9. $z = x \cap y$
10. $z = x ∖ y$
11. $z = x \cup {x}$
12. $z is transitive$
13. $z = ⋃ x$

Definition (Absolute function). Let $M$ a transitive set, and $F : M^{n} \to M$ (note that this means that $M$ is closed under $F$ ). We say $F$ is absolute for $M$ if there is a formula $Φ$ which is absolute for $M$ such that

F (x_{1}, \dots, x_{n}) = z ⟺ Φ (x_{1}, \dots, x_{n}, z) .

Observation: So, if $M$ is closed under pairing ( $\forall x, y \in M, {x, y} \in M$ ), then the pairing operation $x, y \mapsto {x, y}$ is absolute, and therefore $M ⊨ Pairing$ .

Similarly for union.

Lemma. Assuming that:

$φ$ is absolute for $M$
$F, G_{1}, \dots, G_{n}$ are absolute operations on $M$

Then

\begin{array}{l} ψ (x_{1}, \dots, x_{m}) & : = φ (G_{1} (x_{1}, \dots, x_{m}), \dots, G_{n} (x_{1}, \dots, x_{m})) \\ H (x_{1}, \dots, x_{m}) & : = F (G_{1} (x_{1}, \dots, x_{m}), \dots, G_{n} (x_{1}, \dots, x_{m})) \end{array}

are absolute for $M$ .

Proof. Check the definitions! □

Example. More examples:

(14) $z$ is an ordered pair:
$\exists s \in z, \exists d \in z, \exists x \in s, \exists y \in d, (\forall w \in s, (w = x) \land \forall v \in d, (v = x \land v = y) \land \forall w \in z, (w = s \lor w = d)) .$
(15) $z = a \times b$
(16) $z is a relation$
(17) $z = dom x$
(18) $z = range x$
(19) $z is a function$
(20) $z is injective$
(21) $z is surjective$
(22) $z is bijective$

Ordinals

“ $x$ is an ordinal” means $x$ is transitive and $(x, \in)$ is a well-order.

We know: being well-founded is not expressible in first-order logic (see Example Sheet 1).

Because all transitive models satisfy Foundation, we have that if $M$ is transitive, then

M ⊨ x is transitive \land (x, \in) is linearly ordered .

characterises ordinals. But this is clearly in $Δ_{0}$ .

So: being an ordinal is absolute for transitive models.

Thus $M \cap Ord = {x \in M : M ⊨ x is an ordinal}$ . This is transitive, thus there is $α \in Ord$ such that $α = M \cap Ord$ .

Also absolute:

“ $x$ is a successor ordinal” ( $\exists y \in T O D O$ )
“ $x$ is a limit ordinal”
“ $x$ is a non-zero limit ordinal”
$x = ω$ TODO

Cardinals

“ $x$ is a cardinal” if and only if

x is an ordinal \land \forall f, \forall y \in x, f : y \to x ⟹ f is not a surjection

Note that $\forall f$ is not bounded (while $\forall y \in x$ is bounded).

Observe: this is $Π_{1}$ and therefore downwards absolute.

Remark.

(1) We may not want this to be absolute. If it was, we couldn’t change cardinal behaviour.
(2) We can’t obviously bound $\forall f$ , since the natural bound would be
${h : h \to y \to x}$

or
$P (y \times x) .$

These, however, are not (yet??) on our list of absolute concepts.
(3) Not that neither (1) nor (2) is an argument, since there could be an equivalent formula that is $Δ_{0}$ .

2.2 Non-absoluteness

Assume that $M ⊨ ZFC$ is transitive and countable. Then

M \cap Ord = α < ω_{1} .

However, $M ⊨ ZFC$ implies $M ⊨ there are uncountable cardinals$ .

Let $β < α$ be such that $M ⊨ β is the least uncountable cardinal$ .

But $β$ is a countable ordinal, so not a cardinal.

Consequence: All cardinals in $M$ except $ℵ_{0}$ are going to be fake.

So “ $x$ is a cardinal” can’t be absolute.

Note. This also shows that “ $x = P (y)$ ” cannot be absolute:

Take $y$ such that $M ⊨ y = P (ω)$ . Then $y \subseteq P (ω)$ , but is countable since $y \subseteq M$ .

Thus $y \neq P (ω)$ . Therefore “ $x = P (y)$ ” is not absolute.

Recall the general proof strategy mentioned before:

If $M$ is a countable transitive set such that $M ⊨ ZFC$ , then there is a a countable transitive set $N \supseteq M$ such that $N ⊨ ZFC + \neg CH$ .

Question: Is this really solving the original problem? i.e. $Con (ZFC) ⟹ Con (ZFC + \neg CH)$ .

It’s not obvious that $Con (ZFC)$ implies that there is a countable transitive model (ctm) of ZFC.

Answer: That’s not only not obvious, but fake.

Let’s prove that $Con (ZFC)$ $⁄ ⟹$ there is a countable transitive model of ZFC.

Why? Note that $Con (ZFC)$ , or $Con (T)$ for any $T$ is $Δ_{0}$ . So, it’s absolute for transitive models.

So if $M$ is a countable transitive model of ZFC, then $Con (ZFC)$ is true, so by absoluteness, $M ⊨ Con (ZFC)$ . So $M ⊨ ZFC + Con (ZFC)$ . This contradicts Gödel’s Incompleteness Theorem.

We can get a proof of

Con (ZFC) ⟹ Con (ZFC + \neg CH)

via a trick ( Example Sheet 1).

Lemma (Cohen Lemma). Assuming that:

$T \subseteq ZFC$

Then there is finite

T^{*} \subseteq ZFC

such that if

M

is a countable transitive model of

T^{*}

, then there is

N \supseteq M

such that

N

is a countable transitive model of

T + \neg CH

This reduces the problem to:

Find countable transitive models of $T^{*}$ for sufficiently large finite $T^{*} \subseteq ZFC$ .

Definition (Hierarchy). We call an assignment $α \mapsto Z_{α}$ a hierarchy if

(i) $Z_{α}$ is a transitive set
(ii) $Ord \cap Z_{α} = α$
(iii) $α < β ⟹ Z_{α} \subseteq Z_{β}$
(iv) $λ limit ⟹ Z_{λ} = ⋃_{α < λ} Z_{α}$

If ${Z_{α} : α \in Ord}$ is a hierarchy, we can define $Z : = ⋃_{α \in Ord} Z_{α}$ . This is a proper class as $Ord \subseteq Z$ . We also define $ρ_{Z} (x) : = \min {α : x \in Z_{α}}$ , a notion of $Z$ -rank.

Paradigmatic example: von Neumann hierarchy $V_{α}$ , and $V$ is the entire universe.

Theorem 2.1 (Levy Reflection Theorem). Assuming that:

$Z$ is a hierarchy
$φ$ is a formula

Then there are unboundedly many

𝜃

such that

φ

is absolute between

Z_{𝜃}

and

Z

Proposition 2.2 (Tarski-Vaught Test). Assuming that:

$M$ is a substructure of $N$

Then

M

is an elementary substructure if and only if for any formula

ϕ (v, \bar{w})

and

\bar{a} \in M

, if there is

b \in N

such that

N ⊨ ϕ (b, \bar{a})

, then there is

c \in M

such that

N ⊨ ϕ (c, \bar{a})

TVT $_{Φ}$ :

Let $M \subseteq N$ and $Φ$ be a collection of formulas closed under subformulas. Then the following are equivalent:

(i) All formulas in $Φ$ are absolute between $M$ and $N$ .
(ii) For all $φ \in Φ$ , the TV-condition holds: if $φ = \exists x ψ$ , then for all $\bar{y} \in M$ if there is $a \in N$ sucht hat $N ⊨ ψ (a, \bar{y})$ , then there is $b \in M$ such that $N ⊨ ψ (b, \bar{y})$ .

Warm-up: let $(M, \in) ⊨ ZFC$ . Find countable $N \subseteq M$ such that $(N, \in) ≺ (M, \in)$ .

Suppose $\bar{p} = (p_{0}, \dots, p_{n}) \in M$ and $M ⊨ \exists y, ψ (y, \bar{p})$ . Let $w (ψ, \bar{p})$ be a witness for this:

M ⊨ ψ (w (ψ, \bar{p}), \bar{p})

(if necessary, use Axiom of Choice).

(if $M ⊨ \neg \exists y, ψ (y, \bar{p})$ , then let $w (ψ, \bar{p}) = \emptyset$ ).

Set:

\begin{array}{l} N_{0} & : = \emptyset \\ N_{i + 1} & : = {w (ψ, \bar{p}) : ψ formula and \bar{p} \in N_{1}^{< ω}} \\ N & : = ⋃_{i \in ω} N_{i} \end{array}

Note:

(1) $N$ is countable.
(2) $M ≺ N$ by Tarski-Vaught Test.

Remark. In general, even if $M$ is transitive, $N$ is not.

For example, if $ω_{1} \in M$ , then

\exists x, (x is the least countable ordinal)

is true in $M$ .

w (ψ, \emptyset) = ω_{1} .

So $ω_{1} \in N$ . But $ω_{1} \subseteq N$ , since $N$ is countable.

Relevant later!

Also see Example Sheet 1.

Proof of Levy Reflection Theorem. Fix $φ$ and let $Φ$ be its collection of subformulas. This is a finite set!

Need to show: $\forall α, \exists 𝜃 > α$ such that $Z_{𝜃} ⊨ φ ⟺ Z ⊨ φ$ .

For each $ψ \in Φ$ and $\bar{p} = (p_{0}, \dots, p_{n})$ , write

\begin{array}{l} o (ψ, \bar{p}) & : = {\begin{matrix} least α such that \exists y \in Z_{α} with Z ⊨ ψ (y, \bar{p}) & if it exists \\ 0 & otherwise \end{matrix} \\ o (\bar{p}) & : = \max_{ψ \in Φ} o (ψ, \bar{p}) \\ 𝜃_{0} & : = α + 1 \\ 𝜃_{i + 1} & : = \sup {o (\bar{p}) : \bar{p} \in Z_{𝜃_{i}}^{< ω}} \\ 𝜃 & : = \sup_{i \in ω} 𝜃_{i} \end{array}

Then Tarski-Vaught Test implies that $Z_{𝜃}$ and $Z$ agree on $φ$ . □

Corollary. If $T \subseteq ZFC$ is finite, then there is $M$ transitive such that $M ⊨ T$ .

Proof. Let $φ : = \land_{ψ \in T} ψ$ . Since $ZFC ⊢ φ$ , we have that $φ$ is true. By Levy Reflection Theorem, we can find $𝜃$ such that $V_{𝜃} ⊨ φ$ . Note $V_{𝜃}$ is transitive. □

Remark about the proof of Levy Reflection Theorem:

Can you do the same if $Φ$ is infinite?

Of course not: otherwise we colud prove that there exists $𝜃$ such that $V_{𝜃} ⊨ ZFC$ , and hence get $Con (ZFC)$ .

The problem is the case distinction in the definition of $o (ψ, \bar{p})$ : it requires to check whether $\exists y, ψ$ is true.

Next goal: Obtain some $M \subseteq V_{𝜃}$ countable such that $M ⊨ φ$ and $M$ is transitive.

TODO

Theorem (Mostowski’s Collapsing Theorem). Let $r$ be a relation on a set $a$ that is well-founded and extensional. Then there exists a transitive set $b$ , adn a bijection $f : a \to b$ such that $(\forall x, y \in a) (x r y ⟺ f (x) \in f (y))$ . Moreover, $b$ and $f$ are unique.

Proof. See Logic and Set Theory. □

Corollary. For every $T \subseteq ZFC$ finite, there is a countable transitive model of $T$ .

Proof. Without loss of generality that $T$ contains the axiom of extensionality. Form $M ⊨ T$ transitive by Levy Reflection Theorem.

Use warm-up to obtain $N ≺ M$ countable. This is extensional and well-founded, so by Mostowski find $W$ transitive such that

(W, \in) ≅ (N, \in) .

Then $W ⊨ T$ adn $| W | = | |$ , so $W$ is countable. □

The next few lectures will be spent proving $Con (ZFC + CH)$ using Gödel’s constructible universe.

Absoluteness is preserved under transfinite recursion.

Let $F, G, H$ be three operations.

\begin{array}{l} R (0, \bar{x}) & : = F (\bar{x}) \\ R (α + 1, \bar{x}) & : = G (α, R (α, \bar{x}), \bar{x}) \\ R (λ, \bar{x}) & : = H (λ, {R (α, \bar{x}) : α < λ}, \bar{x}) & (*) \end{array}

Proof. Attempts: set functions satisfying the ( $*$ ).

L1 All attempts agree on their common domain.
L2 $\forall α, \exists r$ attempt such that $(α, \bar{x}) \in dom (r)$ .

$R (α, \bar{x}) : = y$ if and only if there exists attempt $r$ with $(α, \bar{x}) \in dom (r)$ and $r (α, \bar{x}) = y$ . □

Note that for $F, G, H$ fixed, there is a finite fragment $T_{F, G, H} \subseteq ZFC$ that proves the recursion theorem instance for $F, G, H$ .

Theorem. If $T \supseteq T_{F, G, H}$ and $F, G, H$ are absolute for transitive models of $T$ , then so is $R$ defined by ( $*$ ).

Want $T_{F, G, H} ⊢ L 1 (F, G, H)$ , $T_{F, G, H} ⊢ L 2 (F, G, H)$ and $T_{F, G, H}$ proves existence of $R$ .

Convention: We say “ $T$ is sufficiently strong” if $T \subseteq ZFC$ is finite and $T$ proves hte existence of all relevant operations such that they are absolute for transitive models of $T$ .

Proof. Observe that by assumption, being an “attempt” is absolute for transitive models of $T$ .

Let $M ⊨ T$ be transitive.

(1) To show: If $M ⊨ R (α, \bar{x}) = z$ , then $R (α, \bar{x}) = z$ .
If $M ⊨ R (α, \bar{x}) = z$ , then $M ⊨ \exists r, r is an attempt and r (α, \bar{x}) = z$ . Without the $\exists r$ , this would be absolute. So when we include the existential quantifier, we get an upwards absolute sentence.

Thus: there is $r$ such that $r$ is an attempt and $r (α, \bar{x}) = z$ . So $R (α, \bar{x}) = z$ .
(2) Other direction. Assume $r$ is an attempt with $r (α, \bar{x}) = z$ .
Since $T_{F, G, H} ⊢ L 2 (F, G, H)$ , we have
$M ⊨ \exists r^{'}, \underset{absolute}{\underset{⏟}{r^{'} is an attempt and (α, \bar{x}) \in dom r^{'}}} .$

Since it is absolute, $r^{'}$ is a real attempt.

By ???, $r^{'} (α, \bar{x}) = r (α, \bar{x})$ . Hence $M ⊨ R (α, \bar{x}) = z$ . □

Note. This uses the fact that “ $Δ_{1}$ ” concepts are absolute.

Definition (Delta1T property). A property is called $Δ_{1}^{T}$ if it’s both ${Σ_{1}}^{T}$ and ${Π_{1}}^{T}$ .

Observe: $Δ_{0}^{T}$ concepts are absolute (upwards from $Σ_{1}$ and downwards from $Π_{1}$ ).

Typical Applications

Bounding a quantifier by operation.

Let $F$ be an operation and $T$ strong enough to prove $F$ is an operation and absolute.

\begin{array}{l} T & ⊢ \forall x, \exists z, F (x) = z \\ T & ⊢ \forall x, \forall z, \forall z^{'}, F (x) = z \land F (x) = z^{'} \to z = z^{'} \end{array}

Then the quantifiers $\exists y \in F (x)$ and $\forall y \in F (x)$ preserve absoluteness.

\begin{array}{l} \exists y \in F (x) ψ & ⟺ \underset{upwards absolute}{\underset{⏟}{\exists z \underset{absolute}{\underset{⏟}{(z = F (x) \land \exists y \in z ψ)}}}} \\ ⟺ \underset{downwards absolute}{\underset{⏟}{\forall z \underset{absolute}{\underset{⏟}{(z = F (x) \to \exists y \in z ψ)}}}} \end{array}

Applications

(1) Encode formulas as elements of

ω^{< ω}


$\in$	$=$	$($	$)$	$\land$	$\lor$	$\neg$	$\exists$	$\forall$	$v_{0}$	$v_{1}$	$v_{2}$	$\dots$

$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$\dots$

$\forall v_{0} \exists v_{1} \neg v_{0} \in v_{1}$ would be $(8, 9, 7, 10, 6, 8, 0, 10)$ .

$F m l \subseteq ω^{< ω}$ . So, $F m l$ is absolute for some (sufficiently strong) finite fragment of $ZFC$ (see Example Sheet 1).

(2) If $X$ is any set then
$“ X ⊨ φ ”$

(which means “ $(X, \in) ⊨ φ$ ”) is defined by the usual (Tarski) recursion and thus also absolute ( Example Sheet 1).

2.3 The constructible hierarchy

Fix a set $X$ . Define for each $φ \in Fml$ and each $p \in X^{< ω}$ (parameter)

D (φ, p, X) : = {w \in X : X ⊨ φ (p, w)}

the subset of $X$ defined by $φ$ with parameter $p$ .

For a sufficiently strong $T \subseteq ZFC$ finite, we have that $T$ proves that $D$ is an absolute operation (see Example Sheet 1).

D (X) : = {D (φ, p, X) : φ \in Fml, p \in X^{< ω}} .

This is absolute for a sufficiently strong theory (use Replacement to get $D (X)$ ).

This $D (X)$ is sometimes (misleadingly) called the “definable power set of $X$ ” (it is misleading because it is more like a “definable (by $X$ ) power set of $X$ ”).

( $α \in D (X) ⟺ \exists φ \in Fml, \exists p \in X^{< ω}, a = D (φ, p, X)$ )

Obvious: $D (X) \subseteq P (X)$ . Also: If $X$ is transitive, then so is $D (X)$ .

\begin{array}{l} L_{0} & : = \emptyset \\ L_{α + 1} & : = D (L_{α}) \\ L_{λ} & = ⋃_{α < λ} L_{α} \end{array}

The constructible hierarchy.

We usually write $L : = ⋂_{α \in Ord} L_{α}$ .

Claim: $L$ is a hierarchy (in the sense of Lecture). See Example Sheet 1.

By closure of absoluteness under transfinite recursion, the $L$ -hierarchy is absolute for transitive models of $T \subseteq ZFC$ where $T$ is strong enough to prove that it exists.

i.e. if $M ⊨ T$ transitive and $α \in Ord \cap M$ and $M ⊨ X = L_{α}$ , then $X = L_{α}$ . So

⋃_{α \in Ord \cap M} L_{α} \subseteq M .

The main theorem of next lecture will be:

If $L ⊨ ZF$ and $M ⊨ ZF$ transitive, then

⋃_{α \in Ord \cap M} L_{α} ⊨ ZF .

(Minimal $ZF$ -model).

Some first idea of what the $L$ -hierarchy is like

Clearly, by induction, $L_{α} \subseteq V_{α}$ , and clearly for $n \in ω$ , $L_{n} = V_{n}$ . So $L_{ω} = V_{ω}$ .

L_{α + 1} : = ⋃_{φ \in Fml} ⋃_{p \in L_{α}^{< ω}} {D (φ, p, L_{α})} .

If $α \geq ω$ , then

| L_{α + 1} | \leq ℵ_{0} \cdot | L_{α}^{< ω} | = ℵ_{0} \cdot | L_{α} | .

Thus $| L_{α} | = | L_{α + 1} |$ .

Therefore $α < ω_{1}$ , $| L_{α} | = ℵ_{0}$ and $| L_{ω_{1}} | = ℵ_{1}$ .

This means: $V_{ω + 1} \neq L_{ω + 1}$ (since the first has size $2^{ℵ_{0}}$ , while the second has size $ℵ_{0}$ ).

Note: This does not mean $V \neq L$ . ( $V = L$ means $\forall x, \exists α, x \in L_{α}$ ).

$V = L$ is called the “axiom of constructibility”.

There is a finite fragment $T_{𝕃}$ of $ZF$ [!] that proves that all of the operations occuring in the definition of $𝕃$ , i.e. $Fml, X^{< ω}, ⊨, D, D$ are well-defined and absolute.

Thus, if $M$ is a transitive model of $T_{𝕃}$ , then

\forall α \in Ord \cap M, 𝕃_{α} \in M

and thus $𝕃_{α} \subseteq M$ .

So $⋃_{α \in Ord \cap M} 𝕃_{α} \subseteq M$ .

Axioms of ZF

Structural axioms:

Extensionality:
$\forall x, \forall y, (\forall w (w \in x \leftrightarrow w \in y) \to x = y) .$

Foundation:

\forall x (\exists v, (v \in x) \to \exists m, (m \in x \land \forall w, \neg (w \in m \land w \in x))) .

Infinity:
$\exists i, \exists e, (\forall v, \neg v \in e \land e \in i) \land \forall x, (x \in i \to \exists s, (s \in i \land \forall w, (w \in s \leftrightarrow w \in x \lor w = x))) .$

Functional axioms:

Pairing:

\forall x, \forall y, \exists p, \forall w, (w \in p \leftrightarrow w = x \lor w = y) .

Union:
$\forall x, \exists v, \forall w, (w \in v \leftrightarrow \exists z, (z \in x \land w \in z)) .$
Powerset:
$\forall x, \exists p, \forall w, (w \in p \leftrightarrow \forall v, (v \in w \to v \in x)) .$

Separation $φ$ :

\forall \bar{p}, \forall x, \exists s, \forall w, (w \in s \leftrightarrow w \in x \land φ (w, \bar{p})) .

Replacement $φ$ :

$\forall \bar{p}, [\forall x, \forall y, \forall z (φ (x, y, \bar{p}) \land φ (x, z, \bar{p}) \to y = z)] \to \forall x, \exists r, \forall w, (w \in r \leftrightarrow \exists y, (y \in x \land φ (y, w, \bar{p}))) .$

Now we check that these hold in $𝕃$ .

In Lecture 2, we proved Extensionality and Foundation in all transitive structures, so also in $𝕃$ .

Note that $ω$ satisfies the condition of the axiom of infinity, so any $M$ transitive with $ω \in M$ will satisfy the axiom of infinity. TODO

Now do pairing and union.

Since the definitions of pairs and unions

\begin{array}{l} z & = {x, y} \\ z & = ⋃ x \end{array}

are absolute for transitive models, it’s enough to show that

\begin{array}{l} \forall x, y \in 𝕃, & {x, y} \in 𝕃 \\ \forall x \in 𝕃 & ⋃ x \in 𝕃 \end{array}

If $x, y \in 𝕃_{α}$ , $φ (w, x, y) : = w = x \lor w = y$ ,

\begin{array}{l} D (φ, (x, y), L_{α}) & = {w \in L_{α} : L_{α} ⊨ φ (w, x, y)} \\ = {w \in L_{α} : L_{α} ⊨ w = x \land w} T O D O \end{array}

Powerset axiom.

\forall x, \exists p, \underset{*}{\underset{⏟}{\forall w, (w \in p \leftrightarrow w \subseteq x)}}

The problem here is that $*$ is not obviously absolute. In particular, $z = P (x)$ is not absolute.

Consider $𝕃_{ω + 1}$ : we have $ω \in 𝕃_{ω + 1}$ and $P \cap 𝕃_{ω + 1}$ is countable.

In $𝕃_{ω + 2}$ , we find

{a \in 𝕃_{ω + 1} : a \subseteq ω}

which is the best possible answer to the question “what is the power set of $ω$ ?” that $𝕃_{ω + 1}$ can give, but unlikely to be the correct answer.

Consider instead $P (ω) \cap 𝕃 = : P$ and define

Ω : = {ρ_{𝕃} (a) : a \in P} .

(reminder: $ρ_{𝕃} (a)$ is the least $α$ such that $a \in 𝕃_{α + 1}$ )

By Replacement, $Ω$ is a set of ordinals, so find $α > Ω$ . Then $P \subseteq 𝕃_{α}$ .

Therefore $P = {a \in 𝕃_{α} : a \subseteq ω} \in 𝕃_{α + 1}$ , so $P \in 𝕃$ .

Separation:

\forall \bar{p}, \forall x, \exists s, \forall w, (w \in s \leftrightarrow \underset{φ^{'} (w, x, \bar{p})}{\underset{⏟}{w \in x \land φ (w, \bar{p})}})

If $x \in 𝕃_{α}$ , then

\begin{array}{l} D (φ^{'}, x, L_{α}) & : = {w \in L_{α} : L_{α} ⊨ φ^{'} (w, x, \bar{p})} \\ = {w \in L_{α} : L_{α} ⊨ w \in x \land φ (w, \bar{p})} \\ \overset{?}{=} {w \in \underset{not a problem}{\underset{⏟}{𝕃}} : \underset{this is a problem}{\underset{⏟}{𝕃}} ⊨ w \in x \land φ (w, \bar{p})} \end{array}

If $φ$ is not absolute between $L_{α}$ and $L$ , this won’t work.

Levy Reflection Theorem to the rescue: $\forall φ, \forall α, \exists 𝜃 > α$ such that $φ$ is absolute between $L_{𝜃}$ and $L$ .

Thus: form

\begin{array}{l} D (φ^{'}, x, L_{𝜃}) & = {w \in L_{𝜃} : L_{𝜃} ⊨ w \in x \land φ (w, \bar{p})} \\ \overset{absolute}{=} {w \in L_{𝜃} : L ⊨ w \in x \land φ (w, \bar{p})} \end{array}

Replacement:

This will be on Example Sheet 2. The proof is a combination of the ideas from power set and separation.

Corollary 2.3 (Minimality). Assuming that:

$T$ is a transitive model of $ZF$

Then for all

α \in T \cap Ord

𝕃_{α} \subseteq T

. Axiom of TODO.

Remark. Remark on the Axiom of Choice.

Gödel (1938): $Con (ZF) \to Con (ZFC)$ .

Note first that everything we did so far only needed $ZF$ in the universe. We will sketch that $𝕃 ⊨ AC$ . In fact a strong version of $AC$ known as GLOBAL CHOICE: there is an absolutely definable bijective operation between $𝕃$ and $Ord$ .

Sketch: Recursive construction of bijections $π_{α} : 𝕃_{α} \to η_{α}$ for some ordinal $η_{α}$ , and such that for $β < α$ we have $π_{α} |_{𝕃_{β}} = π_{β}$ .

If $λ$ is a limit and $π_{α}$ is defined for $α < λ$ , then let

π_{λ} (x) : = π_{α} (x)

if $x \in 𝕃_{α}$ .

Suppose $α = β + 1$ and $π_{β}$ is given by $π_{β} : 𝕃_{β} \to η_{β}$ .

Consider $Fml \times L_{β}^{< ω}$ . Well-order it in order type $η_{β}^{'}$ via the induced $π_{β}$ well-order. Then if $x \in L_{α}$ , say

π_{α} (x) : = {\begin{matrix} π_{β} (x) & if x \in L_{β} \\ η_{β} ξ & if ξ is the ordinal corresponding to the least (φ, \bar{p}) such that x = D (φ, \bar{p}, T O D O) \end{matrix}

TODO

Cohen:

$\forall T \subseteq ZFC$ finite, $\exists T^{*} \subseteq ZFC$ finite such that if $M$ is a countable transitive model of $T^{*}$ , then there is $N \supseteq M$ countable transitive model of $T + \neg CH$ . ( $*$ )

We have seen ( Example Sheet 1) that ( $*$ ) implies $Con (ZFC) ⟹ Con (ZFC + \neg CH)$ .

Simplified: If $M$ is a countable transitive model of $ZFC$ , then there is $N \supseteq M$ countable transitive model of $ZFC h = \neg CH$ .

Idea: If $M$ is a countable transitive model of $ZFC$ : $α : = ω_{1}^{M}$ ; $β : = ω_{2}^{M}$ ; $f : β \to P (ω)$ injection. Force $N$ such that $f \in N$ and $M \subseteq N$ .

Observe that there is a countable transitive model $N$ such that $f \in N$ and $M \subseteq N$ . $M \cup tcl ({f})$ is transitive and countable. Thus LSM gives $N$ transitive countable with $M \cup tcl ({f}) \subseteq N$ . Know $N ⊨ \exists g : β \to P (ω)$ is an injection, but no clue what $ℵ_{1}$ and $ℵ_{2}$ in $N$ are.

How do we control what we add?

3 Forcing

Definition (Forcing). $(ℙ, \leq, 𝟙_{})$ is called a forcing poset or forcing if it is a partial order and $𝟙_{} \in ℙ$ and $𝟙_{}$ is the largest element. Elements of $ℙ$ are called condition.

$p \leq q$ is interpreted as

“ $p$ is stronger than $q$ ”

“ $q$ is weaker than $p$ ”

Note. Unconventional.

Alternative: “Jerusalem convention”. Interpret $p \leq q$ as “ $q$ is stronger than $p$ ”.

We are not following the Jerusalem convention.

Definition (Compatible). $p$ and $q$ are compatible if there is $r \leq p, q$ . Otherwise, we say they are incompatible (which we write as $p ⊥ q$ ).

Definition (Antichain). $A \subseteq P$ is an antichain if any two distinct elements of $A$ are incompatible.

Definition (Dense). $D \subseteq ℙ$ is dense if $\forall p \in T O D O$ .

Definition (Filter). $F \subseteq ℙ$ is called a filter if

(a) $\forall p, q \in F, \exists r \in F, r \leq p, q$
(b) $\forall p \in F, \forall q \in ℙ, q \geq p ⟹ q \in F$

If $F$ only has property (a), we call it a filter base, and then

{p \in ℙ : \exists q \in F, q \leq p}

is the filter generated from $F$ .

Note. Filters cannot contain incompatible elements.

Definition ( $D$ -generic). If $D$ is a family of dense sets, then $F$ is called $D$ -generic if $F$ is a filter and $\forall D \in D, D \cap F \neq \emptyset$ .

Theorem 3.1. Assuming that:

$D$ is countable

Then there is a

D

-generic filter.

Proof. Let $D = {D_{n} : n \in ℕ}$ . Pick $p_{0} \in D_{0}$ arbitrarily and define by recursion $p_{i + 1}$ by picking some $q \leq p_{i}$ with $q \in D_{i + 1}$ .

Then ${p_{i} : i \in ℕ}$ is a filter base, so let $F$ be the filter generated by it. Then it is $D$ -generic by construction. □

Main example

Fix any sets $X$ and $Y$

Fn (X, Y) : = {p : p is a finite fucntion with dom (p) \subseteq X and range (p) \subseteq Y} .

Define $p \leq q ⟺ p \supseteq q$ and $𝟙_{} : = \emptyset$ .

What does $p ⊥ q$ mean?

p ⊥ q ⟺ \exists x \in X, x \in dom (p) \cap dom (q) \land p (x) \neq q (x) .

Lemma 3.2. Assuming that:

$F \subseteq ℙ$ is a filter

Then

⋃ F

is a function.

Lemma 3.3. $D_{x} : = {p \in ℙ : x \in dom (p)}$ is a dense set. If $D : = {D_{x} : x \in X}$ , and $F$ is $D$ -generic, then $dom (⋃ F) = X$ .

Proof. If $x \in X$ , find $p \in F \cap D_{x}$ , then $x \in dom (p)$ , TODO □

3.1 Cohen Forcing

Example 1

$ℂ : = Fn (ω, 2)$ .

If $F$ is $D$ -generic, then $⋃ F : ω \to 2$ (by above).

Lemma 3.4. Assuming that:

Fix $f : ω \to 2$ and define
$N_{f} : = {p \in ℙ : \exists u, p (u) \neq f (u)} .$
$F$ is $D \cup {N_{f}}$

Then

⋃ F \neq f

Corollary 3.5. There is no $F$ that is $D \cup {N_{f} | f : ω \to 2}$ -generic.

However: if $M$ is a countable transitive model and you consider

N_{f} : = {N_{f} : f \in M},

then by Theorem 3.1, there is a $D \cup N_{M}$ -generic. And for this $F$ , TODO

Example 2

$Fn (X, Y) = : ℙ$ as before.

\begin{array}{l} R_{y} & : = {p \in ℙ : y \in range (p)} \\ R & : = {R_{y} : y \in Y} \end{array}

Lemma 3.6. Assuming that:

$F$ is $D \cup R$ -generic

Then

⋃ F : X \to Y

is a surjection.

Corollary 3.7. Assuming that:

$| Y | > | X |$

Then there is no

D \cup R

-generic.

However: if $M$ is a countable transitive model and, e.g. TODO

Example 3

$Fn (X \times Y, 2)$ . Assume $X$ is infinite. Consider

E_{y, y^{'}} : = {p \in ℙ : \exists x \in X, p (x, y) \neq p (x, y^{'})} .

This is dense for $y \neq y^{'}$ .

E : = {E_{y, y^{'}} : y \neq y^{'} \in Y} .

Lemma 3.8. Assuming that:

$F$ is $D \cup E$ -generic

Then there is an injection from

Y

into

P (X)

Proof. Fix $y$ and define

A_{y} : = {x \in X : (⋃ F) (x, y) = 1} .

$E_{y, y^{'}}$ guarantees that $y \mapsto A y$ is an injection. □

Corollary 3.9. Assuming that:

$| Y | > | P (ω) |$

Then there is no

D \cup E

-generic.

However: if $M$ is a countable transitive model of $ZFC + CH$ , $α$ is countable and so a $D \cup E$ -generic exists.

Recap: $M$ a countable transitive model of $ZFC$ (or a sufficiently large finite fragment).

$ℙ \in M$ : dense / filter / $D$ -generic.

Example. $Fn (ω, 2)$ produces a new function $f : ω \to 2$ . Cohen forcing.

Example. $Fn (X, Y)$ produces a surjection $f : X \to Y$ . $Fn (ω, Y)$ COLAPSE of $Y$ .

Example. $Fn (X \times Y, 2)$ produces an injection $f : Y \to P (X)$ .

If $M$ is a countable transitive model of $ZFC$ , then $D_{M} : = {D \subseteq P dense : D \in M}$ is countable, so by Theorem, we have a $D_{M}$ -generic.

Definition 3.10 ( $P$ -generic over $M$ ). We say $F$ is $ℙ$ -generic over $M$ if it is $D_{M}$ -generic. These always exist if $M$ is a countable transitive model.

GOAL: Build an extension $M [G]$ such that $M \subseteq M [G]$ , $M [G]$ a countable transitive model of $ZFC$ , $G \in M [G]$ and $M [G]$ is minimal.

Names

Idea: Think of elements of $ℙ$ as “truth values” for the von Neumann construction.

\begin{array}{l} {Name}_{0}^{ℙ} & : = \emptyset \\ {Name}_{α + 1}^{ℙ} & : = {τ : τ \subseteq {Name}_{α} \times ℙ} \\ {Name}_{λ}^{ℙ} & : = ⋃_{α < λ} {Name}_{α}^{ℙ} \end{array}

Then

{Name}^{ℙ} : = ⋃_{α \in Ord} {Name}_{α}^{ℙ}

is the proper class of all names.

Consider: $ℙ = {0, 1}$ . Then ${Name}^{ℙ} ≅ V$ .

Since this is a recursive definition using absolute concepts, being a name is absolute for transitive models:

{τ : M ⊨ τ is a ℙ -name} = {Name}^{ℙ} \cap M .

TODO

Examples

$\emptyset \in {Name}_{1}^{ℙ}$ ,

τ_{p} : = {(\emptyset, p)} \in {Name}_{2}^{ℙ}

“The name for a set that contains $\emptyset$ with value $p$ .”

τ_{p q} : = {(τ_{p}, q)} .

“The name for whatever $τ_{p}$ describes with value $q$ ”.

Interpretation

If $F \subseteq ℙ$ , we interpret a $ℙ$ -name as follows:

val (τ, F) : = {val (σ, F) : \exists p \in F, (σ, p) \in τ} .

Important: This is a recursive definition.

Thus: the valuation is absolute for transitive models containing $τ$ and $F$ .

Example.

(1) $\emptyset$ : clearly $val (\emptyset, F) = \emptyset$ .
(2) $τ_{p}$ :
$val (τ_{p}, F) : = {\begin{matrix} {\emptyset} & p \in F \\ \emptyset & p \notin F \end{matrix}$
(3) $τ_{p q}$ :
$val (τ_{p q}, F) : = {\begin{matrix} \emptyset & q \notin F \\ {{\emptyset}} & q \in F \land p \in F \\ {\emptyset} & q \in F \land p \notin F \end{matrix}$

The relationship between $p$ and $q$ affects these possibilities.

Example: if $q \leq p$ and $F$ is a filter, then ${\emptyset}$ is impossible.

Example: if $q = 𝟙_{}$ and $F$ is a non-empty filter, then $\emptyset$ is impossible.

Example: if $p ⊥ q$ and $F$ is a filter, then ${{\emptyset}}$ is impossible.

Definition 3.11 (Generic extension). The (generic) extension for any countable transitive model $M$ and any $F \subseteq ℙ$ where $ℙ \in M$ is

M [F] : = {val (τ, F) : τ \in {Name}^{ℙ} \cap M} .

Obviously, $M [F]$ is a countable set with $\emptyset \in M [F]$ (Example (1)).

Also, by definition, $M [F]$ is transitive.

Note:

M [F] ⊨ Extensionality + Foundation .

Need to show

(1) $M \subseteq M [F]$ .
(2) $F \in M [F]$ .
(3) $M [F] ⊨ ZFC$ .
(4) $M [F]$ is minimal.

Canonical Names

Definition 3.12 (Canonical name). Let $x \in M$ . Define by recursion the canonical name for $x$ by

\overset{ˇ}{w} : = {(\overset{ˇ}{y}, 𝟙_{}) : y \in x} .

Lemma 3.13. $val (\overset{ˇ}{x}, F) = x$ if $𝟙_{} \in F$ .

Proof. Induction. □

Corollary 3.14. $M \subseteq M [F]$ if $𝟙_{} \in F$ .

Alternative construction of canonical names without $𝟙_{}$ is on Example Sheet 2.

Γ : = {(\overset{ˇ}{p}, p) : p \in ℙ} .

Lemma 3.15. $val (Γ, F) = F$ .

Proof. Calculate:

\begin{array}{l} val (Γ, F) & = {val (\overset{ˇ}{p}, F) : p \in F} \\ = {p : p \in F} & (by previous lemma) \\ = F \end{array}

□

Corollary 3.16. $F \in M [F]$ .

Remark. If $N$ is a countable transitive model with $M \subseteq N$ and $F \in N$ , then $M [F] \subseteq N$ . (by absoluteness of $val (τ, F)$ ).

Warm-up: Suppose $σ, τ \in {Name}^{ℙ}$ . Define

up (σ, τ) : = {(σ, 𝟙_{}), (τ, 𝟙_{})} .

Pairing: Then

val (up (σ, τ), F)) = {val (σ, F), val (τ, F)} .

(“up” stands for unordered pair).

Corollary 3.17. $M [F] ⊨ Pairing$ (if $𝟙_{} \in F$ ).

Union: If $τ$ is a name, define

u_{τ} : = {(σ^{'}, r) : \exists σ, p, q, s.t. (σ, p) \in τ, (σ^{'}, q) \in σ, r \leq p, q} .

Claim: $val (u_{τ}, F) = ⋃ val (τ, F)$ if $F$ is a filter.

Proof. Suppose $z \in val (u_{τ}, F)$ .

So $z = val (σ^{'}, F)$ for some $(σ^{'}, r) \in u_{τ}$ with $r \in F$ .

So $\exists σ, p, q$ with $(σ, p) \in τ$ , $(σ^{'}, q) \in σ$ , $r \leq p, q$ .

So $p, q \in F$ . Hence $val (σ, F) \in val (τ, F)$ , $z = val (σ^{'}, F) \in val (σ, F)$ .

So $z \in ⋃ val (τ, F)$ .

Conversely, suppose $z \in ⋃ val (τ, F)$ . Then $\exists y, z \in y \in val (τ, F)$ ( $z \to (σ^{'}, q) \in σ$ with $q \in F$ , $y \to (σ, ρ) \in τ$ with $p \in F$ ).

Hence since $F$ a filter, find $r \leq p, q$ with $r \in F$ .

Then $(σ^{'}, r) \in u_{τ}$ , so $z \in val (u_{τ}, F)$ . □

TODO

Further Recap

We proved

M [G] ⊨ Extensionality + Foundation + Pairing + Union .

Homework was: Think about why power set is not easy.

“Union” proof was:

collect all natural candidates of names for elements and assign the natural values.

Problem: If you try to do this for power set, neither the “natural candidates for names” nor the “natural values” are obvious. It’ll turn out that they are obvious in the end, but that requires some assistance.

Note: Separation and Replacement are even worse.

One remaining easy axiom: $AC$ . By well-ordering theorem, $AC$ holds if and only if $\forall x, \exists α, \exists i, i : x \to α$ injection. If $x \in M [F]$ , then there is $σ \in Name$ such that $x = val (σ, F)$ .

Notation. I write $dom (σ) : = {τ : \exists p, (τ, p) \in σ}$ .

Consider $dom (σ)$ . In $M$ , I have $i : dom (σ) \to α$ for some ordinal $α$ . In $M [F]$ , define

y \mapsto \min {i (τ) : val (τ, F) = y, τ \in dom (σ)} .

Call this $i^{*}$ . Then $i^{*} : x \to α$ is an injection. So, $AC$ holds in $M [F]$ .

Forcing

Definition (Forcing language). Fix $M$ a countable transitive model of $ZFC$ , $ℙ \in M$ a forcing poset.

We call the language

L_{forcing} : = L_{\in} \cup {τ : ℙ -names}

the forcing language (over $M$ ).

Definition (Interpretation of forcing language). If $G$ is a $ℙ$ -generic over $M$ and $φ$ is in the forcing language, we say

M [G] ⊨ φ

if and only if

M [G], v ⊨ φ

where $v (τ) : = val (τ, G)$ .

Definition (Semantic forcing predicate). $p ⊩_{M, ℙ} φ$ : Forall $G$ $ℙ$ -generic over $M$ with $p \in G$ , $M [G] ⊨ φ$ .

“ $p$ forces $φ$ ”

We often omit $M, ℙ$ .

Two theorems at the heart of forcing:

(1) Forcing Theorem: If

G

is a

ℙ

-generic over

M

, then

M [G] ⊨ φ ⟺ \exists p \in G, p ⊩ φ .

(2) Definability Theorem: “ $p ⊩ φ$ ” is absolutely definable for transitive models containing $M$ .

We are going to do the following:

(a) Define the syntactic forcing predicate $⊩^{*}$ that is absolutely definable.
(b) Prove the Forcing Theorem for $⊩^{*}$ .
(c) Derive that $⊩ ⟺ ⊩^{*}$ .

Lectures 11 and 12.

Observations (under the assumption of the Forcing Theorem):

(1) If $q \leq p$ and $p ⊩ φ$ , then $q ⊩ φ$ .
(2) If $p ⊩ \exists x, φ$ , then there is a name $τ$ and $q \leq p$ such that $q ⊩ φ (τ)$ .
[if $p ⊩ \exists x, φ (x)$ and $p \in G$ , then by definition $M [G] ⊨ \exists x, φ (x)$ , so there is a name $τ$ such that $M [G] ⊨ φ (τ)$ . By Forcing Theorem, find $r \in G$ such that $r ⊩ φ (τ)$ . Find $q \leq p, r$ , $q \in G$ . By (1), $q ⊩ φ (τ)$ . ]

Proof of Separation in $M [G]$ . Let $φ (x, x_{1}, \dots, x_{n})$ be an $L_{\in}$ -formula (not in the forcing language) and $x \in M [G]$ . Need a name for

A : = {z \in x : M [G] ⊨ φ (z, \bar{p})} .

[For readability, we now drop parameters $\bar{p}$ ].

Fix $σ$ such that $val (σ, G) = x$ . Define

ϱ : = {(π, p) : π \in dom (σ) \land p ⊩ π \in σ \land φ (π)} .

By the Definability Theorem, $ϱ$ is a name in $M$ .

Claim: $val (ϱ, G) = A$ .

“ $\subseteq$ ” If $z \in val (ϱ, G)$ , then there is $(π, p) \in ϱ$ such that $z = val (π, G)$ , $p \in G$ . Since $(π, p) \in ϱ$ , we get $π \in dom (σ)$ , $p ⊩ π \in σ \land φ (π)$ . Together with $p \in G$ , we get
$M [G] ⊨ \underset{z \in x \land φ (z)}{\underset{⏟}{π \in σ \land φ (π)}} .$

Hence $z \in A$ .
“ $\supseteq$ ” If $z \in A$ , then $z \in x$ and $M [G] ⊨ φ (z)$ . So there is $π \in dom (σ)$ , $z = val (π, G)$ .
By the Forcing THeorem, $\exists p \in G$ , $p ⊩ φ (π)$ . Also, there is $q \in G$ and $q ⊩ π \in σ$ . Find $r \in G$ , $r \leq p, q$ such that $r ⊩ π \in r \land φ (π)$ .

Hence $(π, r) \in ϱ$ , so $z = val (π, G) \in val (ϱ, G)$ . □

Proof of power set. Example Sheet 3. □

Proof of Replacement.

Since we already have Separation, it’s enough to show the following:

if $φ$ is a functional formula and $x \in M [G]$ , then there is $R \in M [G]$ such that
$M [G] ⊨ \forall y \in x, \exists z \in R, φ (y, z, \bar{p}) (∗)$

(as before, we suppress parameters for notational ease).

We work in $M$ and identify a name $ρ$ for $R$ . Fix $σ$ such that $x = val (σ, G)$ . Find $α$ large enough such that $dom (σ) \subseteq V_{α}$ . Consider $ψ (p, π) : = \exists μ, p ⊩ φ (π, μ)$ ( $p \in ℙ$ , $π$ a name). By Definability Theorem, this is an $L_{\in}$ formula.

By Levy Reflection Theorem, find $𝜃 > α$ such that $ψ$ is absolute between $V_{𝜃}$ and $V = M$ . Define

ρ : = {(μ, 1) : μ \in V_{𝜃}}

and $R : = val (ρ, G)$ .

Now we verify ( $*$ ) holds: Fix $y \in x$ , $y = val (π, G)$ . Since $φ$ is functional, we know that $φ (π, μ)$ holds in $M [G]$ for some $μ$ . By Forcing Theorem, there is $p \in G$ such that $p ⊩ φ (π, μ)$ . So $M ⊨ ψ (p, π)$ .

By absoluteness, $V_{𝜃} ⊨ ψ (p, π)$ . This means $\exists μ \in V_{𝜃}$ such that $p ⊩ φ (π, μ)$ .

Thus: $val (μ, G) \in val (ρ, G) = R$ .

□

Definition (Dense below $p$ ). $D \subseteq ℙ$ is called dense below $p$ if $\forall q \leq p, \exists r \leq q, r \in D$ .

Lemma 3.18. Assuming that:

$G$ is $ℙ$ -generic over $M$
$E \subseteq ℙ$
$E \in M$

Then

(i) If $E$ is dense below $p$ , $q \leq p$ , then $E$ is dense below $q$ .
(ii) If ${r : E is dense below r}$ is dense below $p$ , then $E$ is dense below $p$
(iii) Either $G \cap E \neq \emptyset$ or $\exists q \in G$ , $\forall r \in E, r ⊥ q$ .
(iv) If $p \in G$ , $E$ is dense below $p$ , then $G \cap E \neq \emptyset$ .

Proof. Example Sheet 3 □

Definition of the syntactic forcing relation

$p ⊩^{*} φ (\bar{τ})$ .

Two recursions:

First “ $⊩^{*} =$ ” by recursion on ${Name}_{α}$ .

Then “ $⊩^{*} \in$ ” without recursion.

Then the rest by recursion on formula complexity.

$p ⊩^{*} τ_{0} = τ_{1}$ : if and only if

\begin{array}{l} \forall (π_{0}, s_{0}) \in τ_{0} \\ {q \leq p : q \leq s_{0} \to \exists (π_{1}, s_{1}) \in τ_{1}, (q \leq s_{1} \land q ⊩^{*} π_{0} = π_{1})} \\ is dense below p \end{array}

and

\begin{array}{l} \forall (π_{1}, s_{1}) \in τ_{1} \\ {q \leq p : q \leq s_{1} \to \exists (π_{0}, s_{0}) \in τ_{0}, (q \leq s_{0} \land q ⊩^{*} π_{0} = π_{1})} \\ is dense below p \end{array}

Remark. This is a recursion on ${Name}_{α}$ .

$p ⊩^{*} τ_{0} \in τ_{1}$ : if and only if

{q \leq p : \exists (π, s) \in τ_{1}, (q \leq s \land q ⊩^{*} π = τ_{0})}

is dense below $p$ .

Remark. No recursion involved, just “ $⊩^{*} =$ ”.

Recursion on complexity of formulas:

$p ⊩^{*} φ \land ψ$ : if and only if $p ⊩^{*} φ$ and $p ⊩^{*} ψ$ .
$p ⊩^{*} \neg φ$ : if and only if $\forall q \leq p$ , $q ⁄ ⊩^{*} φ$ .
$p ⊩^{*} \exists x, φ (x)$ : if and only if ${r : \exists σ, r ⊩^{*} φ (σ)}$ .

Remark. These definitions remind us of Kripke semantics for intuitionistic logic.

Lemma 3.19. The following are equivalent:

(i) $p ⊩^{*} φ$ .
(ii) $\forall r \leq p, r ⊩^{*} φ$ .
(iii) ${r : r ⊩^{*} φ}$ is dense below $ρ$ .

Proof. If this is true for $φ$ of the form $τ_{0} = τ_{1}$ and of the form $τ_{0} \in τ_{1}$ , then it’s true for all formulas.

For $φ$ atomic, we get that (ii) $⟹$ (i) and (ii) $⟹$ (iii) are trivial.

(i) $⟹$ (ii) follows from Lemma 3.18(i).

(iii) $⟹$ (i) follows from Lemma 3.18(ii). □

Strategy:

Theorem 3.20 (Syntactic Forcing Theorem). $M [G] ⊨ φ$ if and only if $\exists p \in G, M ⊨ r ⊩^{*} φ$ .

Corollary 3.21 (Definability Theorem). $p ⊩ φ$ if and only if $p ⊩^{*} φ$ .

( $p ⊩_{M} φ ⟺ M ⊨ p ⊩^{*} φ$ )

Corollary 3.22 (Forcing Theorem). $M [G] ⊨ φ$ if and only if $\exists p \in G, p ⊩ φ$ .

This corollary is immediate from combining the two previously stated results.

Proof of Definability Theorem from Syntactic Forcing Theorem.

$\Leftarrow$ This is just Syntactic Forcing Theorem.
$\Rightarrow$ Suppose $p ⊩ φ$ . By Lemma 3.18, we need to show
${r \leq p : r ⊩^{*} φ}$

is dense below $p$ .

Suppose not. Then I find $q \leq p$ such that $\forall r \leq q$ , $r ⁄ ⊩^{*} φ$ . So $q ⊩^{*} \neg φ$ .

If $q \in G$ , then $p \in G$ . Since $p ⊩ φ$ , $M [G] ⊨ φ$ . Since $q ⊩^{*} \neg φ$ , $M [G] ⊨ \neg φ$ . Contradiction! □

Proof of the Syntactic Forcing Theorem. The Theorem for $=$ can be proved by induction on ${Name}_{α}$ .

The Theorem for $\in$ can be proved once the Theorem has been established for $=$ .

Rest is induction on formula complexity.

Let’s do $\neg$ and leave the rest to Example Sheet 3. Assume we have proved it for $φ$ . We will prove it for $\neg φ$ .

$\Rightarrow$ $M [G] ⊩ \neg φ$ . Consider
$D : = {p : p ⊩^{*} φ or p ⊩^{*} \neg φ} .$

By definition of $⊩^{*} \neg$ , this is dense. Find $p \in G \cap D$ .

By assumption, $p ⁄ ⊩^{*} φ$ , so $p ⊩^{*} \neg φ$ .
$\Leftarrow$ Let $p \in G$ such that $p ⊩^{*} \neg φ$ . By definition, $\forall q \leq p$ , $q ⁄ ⊩^{*} φ$ . If $M [G] ⁄ ⊨ \neg φ$ , thus $M [G] ⊨ φ$ . By induction hypothesis, find $r \in G$ , $r ⊩^{*} φ$ . So $q \leq r, p, q \in G$ .
By Lemma, $q ⊩^{*} φ$ , contradiction to $\forall q \leq p, q ⁄ ⊩^{*} φ$ .

□

Note. The Forcing Theorem is very useful! The inner details of the proof are not very important though. We won’t really discuss these details once we have proved the theorem.

Continuing the proof of Syntactic Forcing Theorem. Assume Syntactic Forcing Theorem for “ $=$ ” and prove if for “ $\in$ ”.

Want to show:

$p ⊩^{*} τ_{0} \in τ_{1}$ if and only if

{q : \exists (π, s) \in τ_{1}, (q \leq s \land q ⊩^{*} π = τ_{0})}

is dense below $p$ .

Proof.

$\Rightarrow$ Assume that $M [G] ⊨ τ_{0} \in τ_{1}$ , i.e. $val (τ_{0}, G) \in val (τ_{1}, G)$ . Thus, there is $(π, s) \in τ_{1}$ such that $val (π, G) = val (τ_{0}, G)$ ( $⟺ M [G] ⊨ π = τ_{0}$ ) and $s \in G$ . So by Syntactic Forcing Theorem for $=$ , find $r \in G$ such that $r ⊩^{*} π = τ_{0}$ .
Find $p \leq r, s$ such that $p \in G$ .

Claim that $D$ is dense below $p$ . Let $q \in D$ and pick the above $(π, s)$ . Then we have $q \leq p \leq s$ and $q ⊩^{*} π = τ_{0}$ (since $q \leq p \leq r$ ).
$\Leftarrow$ Assume $p \in G$ , $p ⊩^{*} τ_{0} \in τ_{1}$ , i.e. $D$ is dense below $p$ . By Lemma 3.18(iv), find $q \in G \cap D$ , thus there is $(π, s) \in τ_{1}$ such that $q \leq s$ , $q ⊩^{*} π = τ_{0}$ . Since $q \in G$ , $s \in G$ , we have $val (π, G) \in val (τ_{1}, G)$ . By Syntactic Forcing Theorem for “ $=$ ”, we have $val (π, G) = val (τ_{0}, G)$ . So $val (τ_{0}, G) \in val (τ_{1}, G)$ . □

Now we prove it for “ $=$ ”.

We prove this by induction on name rank, so assume that Syntactic Forcing Theorem for “ $=$ ” is true for names $π_{0}, π_{1}$ with smaller name rank.

Reminder: we need to show $M [G] ⊨ τ_{0} = τ_{1}$ if and only if $\exists p \in G$ , $p ⊩^{*} τ_{0} = τ_{1}$ .

TODO: double check the below

Proof.

$\Leftarrow$ Assume $p \in G$ such that $p ⊩^{*} τ_{0} = τ_{1}$ . Need to prove $val (τ_{0}, G) = val (τ_{1}, G)$ .
We’ll show that the fact that $D_{0}$ is dense below $p$ implies $val (τ_{0}, G) \subseteq val (τ_{1}, G)$ . The other direction is the same proof but with $0$ and $1$ flipped.

Proof of this: Let $x \in val (τ_{0}, G)$ , so find $(π_{0}, s_{0}) \in τ_{0}$ such that $s_{0} \in G$ and $x = val (π_{0}, G)$ . So, the corresponding $D_{0}$ is dense below $p$ . Find $q \leq s_{0}, p$ such that $q \in G$ . Then $D_{0}$ is dense below $q$ . So find $r \leq q$ such that $r \in G \cap D_{0}$ . (Note that $r \leq q \leq s_{0}$ , so $r \leq s_{0}$ ).

Since $r \in D_{0}$ and $r \leq s_{0}$ , find $(π_{1}, s_{1}) \in τ_{1}$ such that $r \leq s_{1} \land r ⊩^{*} π_{0} = π_{1}$ . By induction hypothesis, $r \in G$ and $r ⊩^{*} π_{0} = π_{1}$ , which implies $x = val (π_{,} v) = val (π_{1}, G)$ (since $(π_{1}, s_{1}) \in τ_{1}$ and $s_{1} \in G$ ).

\Rightarrow

Assume

val (τ_{0}, G) = val (τ_{1}, G)

. Consider the set

\begin{array}{l} D & : = {r : r ⊩^{*} τ_{0} = τ_{1} or \\ Φ_{r}^{0} \exists (π_{0}, s_{0}) \in τ_{0} (r \leq s_{0} \land \forall (π_{1}, s_{1}) \in τ_{1}, \forall q ((q \leq s_{1} \land q ⊩^{*} π_{0} = π_{1}) \to q ⊥ r) \\ Φ_{r}^{1} \exists (π_{1}, s_{1}) \in τ_{1} (r \leq s_{1} \land \forall (π_{0}, s_{0}) \in τ_{0}, \forall q ((q \leq s_{0} \land q ⊩^{*} π_{0} = π_{1}) \to q ⊥ r) \\ } \end{array}

Claim: $D$ is dense. If $p ⊩^{*}$ , then $p \in D$ , so nothing to show. If $p ⁄ ⊩^{*} τ_{0} = τ_{1}$ , then there is some $D_{0} ∕ D_{1}$ that fails to be dense below $p$ .

We’ll show: if $D_{0}$ is not dense below $p$ , then we can find $r \leq p$ such that $Φ_{r}^{0}$ holds.

(Other proof: $D_{1}$ not dense below $p$ $\to Φ_{r}^{1}$ is flipping $0$ and $1$ ).

Suppose $p ⁄ ⊩^{*} τ_{0} = τ_{1}$ and there is $(π_{0}, s_{0}) \in τ_{0}$ such that $D_{0}$ is not dense below $p$ . This means: there is $r \leq p$ such that

\forall q \leq r (q \leq s_{0} \land \forall (π_{1}, s_{1}) \in τ_{1} \neg (q \leq s_{1} \land q ⊩^{*} π_{0} = π_{1}) .

So, we get

r \leq s_{0} \land \forall (π_{1}, s_{1}) \in τ_{1}

for any $q$ that satisfies $q \leq s_{1} \land q ⊩^{*} π_{0} = π_{1}$ . It can’t be compatible with $r$ (finishes the proof of the claim that $D$ is dense).

Summary: We now have that $D$ is dense.

D = {r : r ⊩^{*} τ_{0} = τ_{1} or Φ_{r}^{0} or Φ_{1}^{r}} .

Claim 2: If $r \in G$ , then neither $Φ_{r}^{0}$ nor $Φ_{r}^{1}$ holds (again, just do $Φ_{r}^{0}$ and then flip $0$ and $1$ for $Φ_{r}^{1}$ ).

If $Φ_{r}^{0}$ holds, then find $(π_{0}, s_{0}) \in τ_{0}$ such that $r \leq s_{0}$ and the incompatibility statement holds. $r \in G \to s_{0} \in G$ , so $val (π_{0}, G) \in val (τ_{0}, G)$ . If $(π_{1}, s_{1}) \in τ_{1}$ such that TODO

Put everything together: since $D$ is dense by Claim 1, find $r \in D \cap G$ . Therefore, by Claim 2, $Φ_{r}^{0}$ , $Φ_{r}^{1}$ do not hold.

Thus $r ⊩^{*} τ_{0} = τ_{1}$ . □

Summary: If $G$ is $Fn (ω \times ℵ_{2}^{M}, 2)$ -generic, then $M [G] ⊨ ZFC +$ there is an injection from $ℵ_{2}^{M}$ into $P (ω)$ .

This implies $M [G] ⊨ ZFC + 2^{ℵ_{0}} \geq ℵ_{2}$ if we have $ℵ_{1}^{M} = ℵ^{M [G]}$ , $ℵ_{2}^{M} = ℵ_{2}^{M [G]}$ . This is the goal for today’s lecture.

Note that our proof above is not good enough for the statement ( $*$ ) from Lecture 8:

For all $T \subseteq ZFC$ finite, there exists $T^{*} \subseteq ZFC$ finite such that if $M$ is a countable transitive model of $T^{*}$ , then there is $N \supseteq M$ countable transitive model of $T^{*} + \neg CH$ .

For this, we need to look more carefully at the proof of the GMT:

M ⊨ ZFC ⟹ M [G] ⊨ ZFC .

The proof proceeds AXIOM BY AXIOM and thus for each $φ \in ZFC$ , we find finite $S_{φ}$ such that $M ⊨ S_{φ}$ implies $M [G] ⊨ φ$ .

Let $S \subseteq ZFC$ finite such that $S$ proves that all relevant notions (name, value, …) are well-defined and absolute. Then for $T \subseteq ZFC$ finite, define

T^{*} : = S \cup ⋃_{φ \in T} S_{φ} .

Then, the proof shows ( $*$ ).

Let’s prove $\neg CH$ in $M [G]$ .

Definition (Preserves cardinals). We say $ℙ$ preserves cardinals if $\forall G$ $ℙ$ -generic over $M$ , “ $κ$ is a cardinal” is absolute between $M$ and $M [G]$ .

Definition 3.23 (Countable chain condition). We say $ℙ$ has the countable chain condition (c.c.c.) if every antichain (note the anti!) in $ℙ$ is countable.

Theorem 3.24. Assuming that:

$ℙ$ has countable chain condition

Then

ℙ

preserves cardinals.

Theorem 3.25. $Fn (ω \times ℵ_{2}^{M}, 2)$ has the countable chain condition.

Corollary 3.26. Assuming: - $G$ is $Fn (ω \times ℵ_{2}^{M}, 2)$ -generic over $M$ , then

M [G] ⊨ ZFC + 2^{ℵ_{0}} \geq ℵ_{2} .

Lemma 3.27. Assuming that:

$M ⊨ ℙ$ has countable chain condition
$X, Y \in M$
$G$ is $ℙ$ -generic over $M$
$f : X \to Y$ , $f \in M [G]$

Then there is

F \in M

such that

\forall x \in X, F (x) \subseteq Y

\forall x \in X, f (x) \in F (x)

and

M ⊨ \forall x \in X, F (x) is countable

Proof of Theorem 3.24. Suppose $M ⊨ κ is a cardinal$ , $M [G] ⊨ κ is not a cardinal$ , so there is $λ < κ$ and $f \in M [G]$ , $f : λ \to κ$ , $f$ is a surjection. Apply the lemma to get $F$ .

Define $R : = ⋃_{α < λ} F (α)$ .

Since $\forall x, f (x) \in F (x)$ , $R = κ$ .

But $M ⊨ | R | = ℵ_{0} \cdot λ = λ < κ$ . But then $M$ thinks that $κ$ is not a cardinal, contradiction. □

Now we prove the lemma:

Proof. Let $F (x) : = {y \in Y : \exists p \in ℙ, p ⊩ τ (\overset{ˇ}{x}) = \overset{ˇ}{y}}$ .

Fix $τ$ a name for $f$ .

By Definability Theorem , $F \in M$ .

Then $\forall x \in X, F (x) \subseteq Y$ follows from definition.

$\forall x \in X, f (x) \in F (x)$ follows from Forcing Theorem.

Let’s look at $M ⊨ F (x)$ is countable: If $y \in F (x)$ , let $p_{y}$ be such that $p_{y} ⊩ τ (\overset{ˇ}{x}) = \overset{ˇ}{y}$ .

If $y \neq y^{'}$ , then $p_{y} ⊥ p_{y^{'}}$ . Thus

{p_{y} : y \in F (x)}

is an antichain.

By countable chain condition, it’s countalbe. So $F (x)$ was countable. □

TODO

Proof of Theorem 3.25. Actually, we prove $Fn (X, Y)$ has countable chain condition whenever $Y$ is countable.

$Δ$ -systems form Example Sheet 3 Q33 are also called quasi-disjoint families.

(A family of finite sets $D$ is called a $Δ$ -system if there is a finite set $R$ (called the root of the $Δ$ -system) such that for all $D, D^{'} \in D$ , if $D \neq D^{'}$ then $D \cap D^{'} = R$ ).

$Δ$ -system lemma: Any countable family of finite sets contains an uncountable $Δ$ -system.

Take any $A \subseteq ℙ$ uncountable and prove that it’s not an antichain.

If $p \in A$ , then $dom (p) \subseteq X$ finite. Consider

S : = {dom (p) : p \in A} .

That’s an uncountable family of finite sets, so by $Δ$ -system lemma, find $Δ$ -system $D \subseteq S$ uncountable.

Let $r \subseteq X$ finite be the root of $D$ .

Since $Y$ is countable, there are only countably many functions $q : r \to Y$ . Since $D$ is uncountable, by pigeonhole principle, there are $p, q$ such that $dom (p), dom (q) \in D$ and $p |_{r} = q |_{r}$ . But since $dom (p) \cap dom (q) = r$ , $p$ and $q$ are compatible.

So $A$ is not an antichain. □

We got $M [G] ⊨ 2^{ℵ_{0}} \geq ℵ_{2}$ .

Next time: What is the size of $2^{ℵ_{0}}$ in $M [G]$ ?

Remember: LST Example Sheet 4: $ZFC ⊢ 2^{ℵ_{0}} \neq ℵ_{ω}$ .

What if $ℵ_{2}$ was one of the forbidden values?

Remark. Obtaining $M [G] ⊨ 2^{ℵ_{0}} = ℵ_{2}$ cannot be quite as general as this proof: if $M ⊨ 2^{ℵ_{0}} > ℵ_{2}$ , then this will remain true in $M [G]$ .

Remark. If $G$ is $Fn (ω \times ℵ_{α}^{M}, 2)$ -generic over $M$ , then

M [G] ⊨ 2^{ℵ_{0}} \geq ℵ_{α} .

Previous lecture: Suppose $M$ a countable transitive model of $ZFC$ .

TODO

Question: ( $*$ ) What are the possible values for $2^{ℵ_{0}}$ ?

Mentioned last lecture: not all values are possible. In particular, $2^{ℵ_{0}} \neq ℵ_{ω}$ .

Definition (Cofinal). $C \subseteq κ$ is cofinal ( $=$ unbounded) if $\forall λ < κ, \exists γ \in C, γ \geq λ$ . We can then define:

cf κ : = {| C | : C is cofinal} .

Example 3.28. $cf ℵ_{1} = ℵ_{1}$ , $cf ℵ_{ω} = ℵ_{0}$ .

Lemma 3.29 (Kőnig’s Lemma). $κ^{cf κ} > κ$ .

Then LST Example Sheet 4 Q10 is the special case $κ = ℵ_{ω}$ , $cf κ = ℵ_{0}$ of Kőnig’s Lemma.

Consequence for $2^{cf κ}$ : ${(2^{cf κ})}^{cf κ} = 2^{cf κ}$ , thus $2^{cf κ} \neq κ$ .

Preview of answer to ( $*$ ): Every value not prohibited by Kőnig’s Lemma is possible.

Now: $ℵ_{2}$ !

Definition. If $ℙ$ is any forcing, let

OL : = {A_{n} : n \in ω}

be any $ω$ -sequence of antichains in $ℙ$ .

Let

τ_{OL} : = {(ň, p) : p \in A_{n}} .

We call these nice names.

If $| ℙ | = κ$ and $ℙ$ has countable chain condition, then there are at most $κ^{ℵ_{0}}$ many antichains and thus at most ${(κ^{ℵ_{0}})}^{ℵ_{0}} = κ^{ℵ_{0} \cdot ℵ_{0}} = κ^{ℵ_{0}}$ many $ω$ -sequences of antichains and thus nice names.

Theorem 3.30. Assuming that:

$M [G] ⊨ x \subseteq ω$

Then there is a nice name

τ

such that

val (τ, G) = x

Note. The Theorem does not need any assumptions about $ℙ$ .

Proof. Start with $M$ such that $val (μ, G) = x$ (possibly not nice). Fix $n \in ω$ . Fix either a well-ordering of $ℙ$ (possibly using $AC$ to get one) and build a maximal antichain $A_{n}$ such that $\forall p \in A_{n}$ , $p ⊩ ň \in μ$ .

TODO.

Claim: $val (μ, G) = val (τ_{OL}, G)$ .

$\supseteq$ : If $n \in val (τ_{O L}, G)$ , then there is $p \in G$ such that $(ň, p) \in τ_{OL}$ , and then $p \in A_{n}$ , so $p ⊩ ň \in μ$ . So $n \in val (μ, G)$ .

$\subseteq$ : If $n \in val (μ, G)$ , then by Forcing Theorem, get $q \in G$ such that $q ⊩ ň \in μ$ .

Subclaim: $A_{n} \cap G \neq \emptyset$ . Indeed, by our lemma on compatibility ( Example Sheet 3), get $q^{'} \in G$ such that $q^{'} ⊥ p$ for all $p \in A_{n}$ . Find $r \leq q, q^{'}$ . Then $r ⊩ ň \in μ$ . But that is in contradiction to $A_{n}$ being maximal.

So find $p \in G \cap A_{n}$ . By definition, $(ň, p) \in τ_{OL}$ and $p \in G$ . So $n \in val (τ_{OL}, G)$ . □

Corollary 3.31. Assuming that:

$ℙ$ has countable chain condition
$M ⊨ | ℙ | = κ \land λ = κ^{ℵ_{0}}$

Then

M [G] ⊨ 2^{ℵ_{0}} \leq λ

Proof. Follows directly from:

(a) Theorem.
(b) Calculation of the number of nice names.

□

Main Application

If $ℙ = Fn (ω \times ℵ_{2}^{M}, 2)$ , then $| ℙ | = ℵ_{2}^{M}$ .

Calculate in $M$ , $ℵ_{2}^{ℵ_{0}}$ .

Hausdorff’s Formula:

ℵ_{α + 1}^{ℵ_{β}} = ℵ_{α + 1} \cdot ℵ_{α}^{ℵ_{β}} .

So in particular:

\begin{array}{l} ℵ_{1}^{ℵ_{0}} & = ℵ_{1} \cdot ℵ_{0}^{ℵ_{0}} \\ = 2^{ℵ_{0}} \\ ℵ_{2}^{ℵ_{0}} & = ℵ_{2} \cdot ℵ_{1}^{ℵ_{0}} \\ = ℵ_{2} \cdot 2^{} \end{array}

So $ℵ_{2}^{ℵ_{0}} = \max (ℵ_{2}, 2^{ℵ_{0}})$ .

By this calculation, if $M ⊨ 2^{ℵ_{0}} \leq ℵ_{2}$ , then $M [G] ⊨ 2^{ℵ_{0}} \leq ℵ_{2}$ .

Corollary 3.32. If $M ⊨ CH$ , then $M [G] ⊨ 2^{ℵ_{0}} = ℵ_{2}$ .

Remark. This proof also shows that if

M ⊨ 2^{ℵ_{0}} \leq ℵ_{n}

and $G$ is $ℙ$ -generic over $M$ where $ℙ = Fn (ω \times ℵ_{2}^{M}, 2)$ , then

M [G] ⊨ 2^{ℵ_{0}} \leq ℵ_{n} .

Corollary: If $M ⊨ CH$ , then $M [G] ⊨ 2^{ℵ_{0}} = ℵ_{n}$ .

Remark. What happens at $ℵ_{ω}$ ?

ℙ : = Fn (ω \times ℵ_{ω}^{M}, 2) .

By general theory, $M [G] ⊨ 2^{ℵ_{0}} \geq ℵ_{ω}$ , but Kőnig’s Lemma gives $2^{ℵ_{0}} \geq ℵ_{ω + 1}$ .

What about the lower bound?

Our theorem and counting of nice names yields

M [G] ⊨ 2^{ℵ_{0}} \leq \underset{> ℵ_{ω}}{\underset{⏟}{ℵ_{ω}^{ℵ_{0}}}} .

If $M ⊨ GCH$ , then

ℵ_{ω}^{ℵ_{0}} \leq ℵ_{ω}^{ℵ_{ω}} = ℵ_{ω + 1} .

So by Kőnig’s Lemma, $ℵ_{ω}^{ℵ_{0}} = ℵ_{ω + 1}$ .

Therefore, if $M ⊨ GCH$ , then $M [G] ⊨ 2^{ℵ_{0}} = ℵ_{ω + 1}$ .

TODO

First limit cardinal that is a possible value of $2^{ℵ_{0}}$ is $ℵ_{ω_{1}}$ .

Clearly, $ℙ = Fn (ω \times ℵ_{ω_{1}}^{M}, 2)$ adds injection from $ℵ_{ω_{1}}^{M}$ into $P (ω)$ . So $M [G] ⊨ 2^{ℵ_{0}} \geq ℵ_{ω_{1}}$ .

Count nice names: $| ℙ |^{ℵ_{0}} = ℵ_{ω_{1}}^{ℵ_{0}}$ .

If for all $α < ω_{1}$ , $ℵ_{α}^{ℵ_{0}} \leq ℵ_{ω_{1}}$ ( $*$ ), then $ℵ_{ω_{1}}^{ℵ_{0}} = ℵ_{ω_{1}}$ .

\begin{array}{l} ℵ_{ω_{1}}^{ℵ_{0}} & = ℵ_{ω_{1}} \\ = \underset{= : X}{\underset{⏟}{{f | f : ω \to ℵ_{ω_{1}}}}} \\ = ⋃_{α < ω_{1}} {f | f : ω \to ℵ_{α}} \end{array}

(since $ω_{1}$ has no cofinal $ω$ -sequence).

Thus $| X | \leq ℵ_{1} \cdot ℵ_{ω_{1}} = ℵ_{ω_{1}}$ (by assumption ( $*$ )).

Thus $M [G] ⊨ 2^{ℵ_{0}} = ℵ_{ω_{1}}$ .

TODO

What about $2^{ℵ_{1}}$ ?

Closure

Definition ( $l a m b d a$ -closed). A forcing $ℙ$ is called $λ$ -closed if any family ${p_{α} : α < γ}$ for $γ < λ$ that is a descending chain:

α < β ⟹ p_{β} < p_{α}

there is $q$ such that $q \leq p_{α}$ for all $α < γ$ .

Example. $Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1})$ is $ℵ_{1}$ -cloesd.

[If ${p_{α}}$ is a descending chain, then $⋃_{α < γ} p_{α}$ is a condition in $Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1})$ .]

Theorem 3.33. Assuming that:

$ℙ$ is $λ$ -closed and $κ < λ$

Then

P (κ) \cap M = P (κ) \cap M [G] .

Corollary 3.34. Forcing with $Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1})$

(a)
Does not change $P (ω)$ .
(b)
Therefore preserves $ℵ_{1}$ (see Example Sheet 1 and the relation between codes for countable well-orders and preserving $ℵ_{1}$ ).

Summary: Forcing with $Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1})$ over a model of $GCH$ gives $M [G]$ with:

(1) The same cardinals (cardinals $\geq ℵ_{2}$ preserved by $ℵ_{2}$ -chain condition; $ℵ_{1}$ preserved by $ℵ_{1}$ -closure).
(2) $2^{ℵ_{1}} \geq ℵ_{3}$ (standard).
(3) $2^{ℵ_{0}} = ℵ_{1}$ (by corollary 1 to the closure theorem).
(4) Calculate number of nice names:
$ℵ_{3}^{ℵ_{1} \cdot ℵ_{1}} = ℵ_{3}^{ℵ_{1}} = ℵ_{3} \cdot 2^{ℵ_{1}} = ℵ_{3} \cdot ℵ_{2} = ℵ_{3} .$

Hence $2^{ℵ_{1}} = ℵ_{3}$ .


Forcing	Property	Preservation	Arithmetic

$Fn (ω \times ℵ_{2}, 2)$	countable chain condition	all cardinals	$2^{ℵ_{0}} = ℵ_{2}$ , $2^{ℵ_{1}} = ℵ_{2}$

$Fn (ω \times ℵ_{3}, 2)$	countable chain condition	all cardinals	$2^{ℵ_{0}} = ℵ_{3}$ , $2^{ℵ_{1}} = ℵ_{3}$ , $2^{ℵ_{2}} = ℵ_{3}$

$Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1})$	$ℵ_{1}$ -closed. If $M ⊨ CH$ , then $ℵ_{2}$ -chain condition	$ℵ_{1}$ preserved. (Closure lemma [not yet proved]) $κ \geq ℵ_{2}$ preserved	If $M ⊨ CH$ , then $2^{ℵ_{0}} = ℵ_{1}$ , $2^{ℵ_{1}} = ℵ_{3}$ .

Note $GCH \to PSA$ , but our model of $\neg CH$ fails $PSA$ .

Question: Can we have $ℵ_{1} < 2^{ℵ_{0}} < 2^{ℵ_{1}}$ ?

Closure lemma:

Theorem. If $ℙ$ is $λ$ -closed and $κ < λ$ , then $P (κ) \cap M = P (κ) \cap M [G]$ .

$λ$ -closed: every descending sequence of length $< λ$ has a lower bound.

Proof. Let $f \in M [G]$ , $f : κ \to 2$ and assume towards contradiction that $f \notin M$ . $\to$ $f \notin B$ .

B : = {f \in M | f : M \to 2} .

Let $τ$ be a name for $f$ .

By Forcing Theorem, there is $p \in G$ such that $p ⊩ τ : \overset{ˇ}{κ} \to \overset{ˇ}{2} \land τ \notin \overset{ˇ}{B}$ .

Construct a $κ$ -sequence of conditions $p_{α}$ TODO

TODO

The sequence ${p_{α} : α \leq κ}$ is defined in $M$ (by Definability Theorem), so we can define

g (α) = 1 : ⟺ p_{α + 1} ⊩ τ (\overset{ˇ}{α}) = \overset{ˇ}{1} .

Then $g \in M$ .

But now $p_{κ} ⊩ τ (\overset{ˇ}{α}) = \overset{ˇ}{1}$ or $p_{κ} ⊩ τ (\overset{ˇ}{α}) = \overset{ˇ}{0}$ for all $α$ .

uso $p_{k} ⊩ τ = ǧ$ . Hence $p_{κ} ⊩ τ \in \overset{ˇ}{B}$ .

But $p_{κ} \leq p ⊩ τ \notin \overset{ˇ}{B}$ . Contradiction. □

Note that while $Fn (X, Y, ℵ_{1})$ is always $ℵ_{1}$ -closed, the chain condition depended on the value of $ℵ_{1}^{ℵ_{0}}$ .

The partial order $Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1})$ has in general the ${(2^{ℵ_{0}})}^{+}$ -chain condition.

$CH$ implies ${(2^{ℵ_{0}})}^{+} = ℵ_{2}$ , so all cardinals are preserved.

However, if $2^{ℵ_{0}} > ℵ_{1}$ , then there is a gap and we do not know whether TODO.

If $M ⊨ 2^{ℵ_{0}} = ℵ_{2}$ , does

Fn (ℵ_{1}^{M} \times ℵ_{3}^{M}, 2, ℵ_{1}^{M})

preserve $ℵ_{2}^{M}$ ?

Answer: $Fn (λ^{+} \times κ, 2, λ^{+})$ always adds a surjection from $λ^{+}$ to $2^{λ} \cap M$ . ( $*$ )

Application: If $λ = ℵ_{2}$ and $M = 2^{ℵ_{0}} = ℵ_{2}$ , then $Fn (ℵ_{1} \times κ, 2, ℵ_{1}^{M}$ adds a surjection from $ℵ_{1}^{M}$ onto $P (ℵ_{0}) \cap M$ , i.e. $ℵ_{2}^{M}$ . So $| ℵ_{2}^{M} | = ℵ_{1}^{M [G]}$ .

[Proof of ( $*$ ). ] A generic for $ℙ$ “is” a map $f : λ^{+} \times κ \to 2$ .

Define $h : λ^{+} \to 2^{λ}$ by

h (α) (β) = 1 : ⟺ f (α, β) = 1 .

Claim: $h$ is a surjection onto $2^{λ} \cap M$ .

If $g \in M$ , $g : λ \to 2$ , consider

D_{g} : = {p | \exists α < λ^{+}, \forall β < λ, p (α, β) = 1 ⟺ g (β) = 1} .

This is dense, and thus $g \in range (h)$ . □

Back to our question: Can we get $ℵ_{1} < 2^{ℵ_{0}} < 2^{ℵ_{1}}$ ?

Start with $M ⊨ GCH$ . Consider

ℙ : = Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1}) \cap M

and let $G$ be $ℙ$ -generic over $M$ . Consider

ℚ : = Fn (ω \times ℵ_{2}, 2) \cap M [G],

and let $H$ be $ℚ$ -generic over $M [G]$ .

Claim: $M [G] [H] ⊨ ℵ_{1} < 2^{ℵ_{0}} < 2^{ℵ_{1}}$ .

( $M [G] [H]$ is a forcing iteration).

(1) $ℙ$ is cardinal preserving over $M$ since $M ⊨ GCH$ . So $ℵ_{n}^{M} = ℵ_{n}^{M [G]}$ .
(2) $ℚ$ has countable chain condition, so is cardinal preserving: $⟹$
$ℵ_{n}^{M [G] [H]} = ℵ_{n}^{M [G]} = ℵ_{n}^{M} .$
(3) $M [G] ⊨ 2^{ℵ_{0}} = ℵ_{1} \land 2^{ℵ_{1}} = ℵ_{3}$ (lecture 15; since $M ⊨ CH$ ).
(4) Then $M [G] [H] ⊨ 2^{ℵ_{0}} = ℵ_{2} \land 2^{ℵ_{1}} \geq ℵ_{3}$ (using a nice name analysis, we could calculate $2^{ℵ_{1}} = ℵ_{3}$ ).

This proves the claim.

Important: The order of forcings matters!

Suppose $M ⊨ GCH$ .

ℚ^{'} : = Fn (ω \times ℵ_{2}, 2) \cap M .

$H$ $ℚ^{'}$ -generic over $M$ .

ℙ^{'} : = Fn (ℵ_{1} \times ℵ_{3}, 2, ℵ_{1}) \cap M [H] .

$G$ $ℙ^{'}$ -generic over $M [H]$ .

Consider $M [H] [G]$ . Then

M [H] ⊨ 2^{ℵ_{0}} = ℵ_{2} = 2^{ℵ_{1}} .

But that means that forcing with $ℙ^{'}$ will collapse $ℵ_{2}^{M} = ℵ_{2}^{M [H]}$ .

Since $ℙ^{'}$ is $ℵ_{1}$ -closed,

P (ω) \cap M [H] = P (ω) \cap M [H] [G] .

In particular, $M [H] [G] ⊨ CH$ . So, this order does not achieve what we want.

Final Remark on Forcing CH

Assume $M ⊨ 2^{ℵ_{0}} = ℵ_{2}$ .

Question: Can you obtain $M [G] ⊨ CH$ ?

The natural forcing would be

ℙ : = Fn (ω, ℵ_{1}^{M}) .

This collapses $ℵ_{1}^{M}$ ; it does not have the countable chain condition, but since it has size $ℵ_{1}^{M}$ , it has the $ℵ_{2}^{M}$ -chain condition, so all cardinals $\geq ℵ_{2}^{M}$ are preserved.

Clearly therefore:

M [G] ⊨ | P (ω) \cap M | = ℵ_{2}^{M} = ℵ_{1}^{M [G]} .

But: is $| P (ω) \cap M | = | P (ω) \cap M [G] |$ ?

Nice names: gives upper bound of

{(ℵ_{1}^{M})}^{ℵ_{1}^{M} \cdot ℵ_{0}} = {(2^{ℵ_{1}^{M}})}^{M} .

That’s not surprising, since any $A \subseteq ℵ_{1}$ in $M$ becomes a new subset of $ω$ in $M [G]$ via the new bijection between $ω$ and $ℵ_{1}^{M}$ .