Title: Daniel's Flashcards / Year 4 / Term 2 / Forcing and the Continuum Hypothesis

html: Definition 1.1 (absolute). If M ⊆ 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 , … , x m ∈ M,
M ⊨ φ ( x 1 , … , x n ) ⟺ N ⊨ φ ( x 1 , … , x n ) .
If the ⇒ direction holds, then we say “upwards absolute”, and if the ⇐ direction holds, then we say “downwards absolute”.
nothing: True

html: Definition (Absolute formula). We say φ is absolute for M if for all x 1 , … , x n ∈ M, we have
M ⊨ φ ( x 1 , … , x n ) ⟺ φ ( x 1 , … , x n ) is true .
nothing: True

html: Lemma. Assuming that:
- M is transitive
Then
M ⊨ Extensionality + Foundation .
proof: Proof. Extensionality: ∀ ⁡ x ∀ ⁡ y ( ∀ ⁡ w ( w ∈ x ↔ w ∈ y ) → x = y ). Take x ≠ y, x , y ∈ M. Without loss of generality take z ∈ x ∖ y. Then z ∈ x and x ∈ M so z ∈ M. So M ⊨ z ∈ x ∧ z ∉ y. So M ⊨ ¬ ⁡ ∀ ⁡ w ( w ∈ x ↔ w ∈ y ).
Foundation: ∀ ⁡ x ( x ≠ ∅ → ∃ ⁡ m ( m ∈ x ∧ ∀ ⁡ w ¬ ⁡ ( w ∈ m ∧ w ∈ x ) ) ). Take x ∈ M. M ⊨ x ≠ ∅ so x is not empty. So find m ∈ x which is ∈-minimal. Then since x ∈ M as well, we have m ∈ M. Therefore x has an ∈-minimal element in M. □
cloze1: True

html: Definition (Bounded quantifier). We call a quantifier of the form ∃ ⁡ x ∈ y , φ or ∀ ⁡ x ∈ y , φ a bounded quantifier.
(Defined by ∃ ⁡ x ∈ y , φ : = ∃ ⁡ x ( x ∈ y ∧ φ ) and ∀ ⁡ x ∈ y φ : = ∀ ⁡ x ( x ∈ y → φ )).
nothing: True

html: Definition (Closed under bounded quantification). A class of formulas Γ is closed under bounded quantification if whenever φ is in Γ, then so are ∃ ⁡ x ∈ y , φ and ∀ ⁡ x ∈ y , φ.
nothing: True

html: 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.
nothing: True

html: Theorem. Δ 0 formulas are absolute for transitive models.
proof: 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 ∃ ⁡ x ∈ y , φ and ∀ ⁡ x ∈ y , φ are absolute.
  - ∃ ⁡ x ∈ y , φ: If ∃ ⁡ x ∈ y , φ is true for some y ∈ M, then pick a witness x ∈ y. Since y ∈ M, we have x ∈ M. By the induction hypothesis, we have that M ⊨ φ ( x , y ). Thus M ⊨ ∃ ⁡ x ( x ∈ y ∧ φ ( x , y ) ).
If M ⊨ ∃ ⁡ x ( x ∈ y ∧ φ ( x , y ) ), then x ∈ y ∧ φ ( x , y ) is true.
  - ∀ ⁡ x ∈ y , φ: Similar. □
cloze1: True

html: Corollary. Assuming that:
- T is any theory
- M ⊨ T is transitive
Then Δ 0 T-formulas are absolute for M.
proof: Proof. Just definition of the semantics of ∃ ⁡ , ∀ ⁡. □
cloze1: True

html: Definition (S i g m a 1, P i 1). A formula is called Σ 1 if it is of the form ∃ ⁡ x 1 , … ∃ ⁡ x n , φ where φ is Δ 0.
It is called Π 1 if it is of the form ∀ ⁡ x 1 , … , ∀ ⁡ x n , φ where φ is Δ 0.
nothing: True

html: Definition (Absolute function). Let M a transitive set, and F : M n → 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 , … , x n ) = z ⟺ Φ ( x 1 , … , x n , z ) .
nothing: True

html: Lemma. Assuming that:
- φ is absolute for M
- F , G 1 , … , G n are absolute operations on M
Then ψ ( x 1 , … , x m ) : = φ ( G 1 ( x 1 , … , x m ) , … , G n ( x 1 , … , x m ) ) H ( x 1 , … , x m ) : = F ( G 1 ( x 1 , … , x m ) , … , G n ( x 1 , … , x m ) )
are absolute for M.
proof: Proof. Check the definitions! □
cloze1: True

html: Lemma (Cohen Lemma). Assuming that:
- T ⊆ ZFC
Then there is finite T ∗ ⊆ ZFC such that if M is a countable transitive model of T ∗, then there is N ⊇ M such that N is a countable transitive model of T + ¬ ⁡ CH.
proof: Proof of Levy Reflection Theorem . Fix φ and let Φ be its collection of subformulas. This is a finite set!
Need to show: ∀ ⁡ α , ∃ ⁡ 𝜃 > α such that Z 𝜃 ⊨ φ ⟺ Z ⊨ φ.
For each ψ ∈ Φ and p ¯ = ( p 0 , … , p n ), write
o ( ψ , p ¯ ) : = { least α such that ∃ ⁡ y ∈ Z α with Z ⊨ ψ ( y , p ¯ ) if it exists 0 otherwise o ( p ¯ ) : = max ⁡ ψ ∈ Φ o ( ψ , p ¯ ) 𝜃 0 : = α + 1 𝜃 i + 1 : = sup ⁡ { o ( p ¯ ) : p ¯ ∈ Z 𝜃 i < ω } 𝜃 : = sup ⁡ i ∈ ω 𝜃 i
Then Tarski-Vaught Test implies that Z 𝜃 and Z agree on φ. □
nothing: True

html: Definition (Hierarchy). We call an assignment α ↦ Z α a hierarchy if
- (i) Z α is a transitive set
- (ii) Ord ⁡ ∩ Z α = α
- (iii) α < β ⟹ Z α ⊆ Z β
- (iv) λ limit ⟹ Z λ = ⋃ ⁡ α < λ Z α
If { Z α : α ∈ Ord ⁡ } is a hierarchy, we can define Z : = ⋃ ⁡ α ∈ Ord ⁡ Z α. This is a proper class as Ord ⁡ ⊆ Z. We also define ρ Z ( x ) : = min ⁡ { α : x ∈ Z α }, a notion of Z-rank.
nothing: True

html: 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.
proof: Proof of Levy Reflection Theorem . Fix φ and let Φ be its collection of subformulas. This is a finite set!
Need to show: ∀ ⁡ α , ∃ ⁡ 𝜃 > α such that Z 𝜃 ⊨ φ ⟺ Z ⊨ φ.
For each ψ ∈ Φ and p ¯ = ( p 0 , … , p n ), write
o ( ψ , p ¯ ) : = { least α such that ∃ ⁡ y ∈ Z α with Z ⊨ ψ ( y , p ¯ ) if it exists 0 otherwise o ( p ¯ ) : = max ⁡ ψ ∈ Φ o ( ψ , p ¯ ) 𝜃 0 : = α + 1 𝜃 i + 1 : = sup ⁡ { o ( p ¯ ) : p ¯ ∈ Z 𝜃 i < ω } 𝜃 : = sup ⁡ i ∈ ω 𝜃 i
Then Tarski-Vaught Test implies that Z 𝜃 and Z agree on φ. □
nothing: True

html: 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 , w ¯ ) and a ¯ ∈ M, if there is b ∈ N such that N ⊨ ϕ ( b , a ¯ ), then there is c ∈ M such that N ⊨ ϕ ( c , a ¯ ).
proof: Proof of Levy Reflection Theorem . Fix φ and let Φ be its collection of subformulas. This is a finite set!
Need to show: ∀ ⁡ α , ∃ ⁡ 𝜃 > α such that Z 𝜃 ⊨ φ ⟺ Z ⊨ φ.
For each ψ ∈ Φ and p ¯ = ( p 0 , … , p n ), write
o ( ψ , p ¯ ) : = { least α such that ∃ ⁡ y ∈ Z α with Z ⊨ ψ ( y , p ¯ ) if it exists 0 otherwise o ( p ¯ ) : = max ⁡ ψ ∈ Φ o ( ψ , p ¯ ) 𝜃 0 : = α + 1 𝜃 i + 1 : = sup ⁡ { o ( p ¯ ) : p ¯ ∈ Z 𝜃 i < ω } 𝜃 : = sup ⁡ i ∈ ω 𝜃 i
Then Tarski-Vaught Test implies that Z 𝜃 and Z agree on φ. □
nothing: True

html: Corollary. If T ⊆ ZFC is finite, then there is M transitive such that M ⊨ T.
proof: Proof. Let φ : = ∧ ⁡ ψ ∈ T ψ. Since ZFC ⊢ φ, we have that φ is true. By Levy Reflection Theorem, we can find 𝜃 such that V 𝜃 ⊨ φ. Note V 𝜃 is transitive. □
cloze1: True

html: 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 → b such that ( ∀ ⁡ x , y ∈ a ) ( x r y ⟺ f ( x ) ∈ f ( y ) ). Moreover, b and f are unique.
proof: Proof. See Logic and Set Theory. □
nothing: True

html: Corollary. For every T ⊆ ZFC finite, there is a countable transitive model of T.
proof: 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 , ∈ ) ≅ ( N , ∈ ) .
Then W ⊨ T adn | W | = | |, so W is countable. □

html: Theorem. If T ⊇ T F , G , H and F , G , H are absolute for transitive models of T, then so is R defined by (∗).
proof: 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 ( α , x ¯ ) = z, then R ( α , x ¯ ) = z.
If M ⊨ R ( α , x ¯ ) = z, then M ⊨ ∃ ⁡ r , r is an attempt and r ( α , x ¯ ) = z. Without the ∃ ⁡ 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 ( α , x ¯ ) = z. So R ( α , x ¯ ) = z.
- (2) Other direction. Assume r is an attempt with r ( α , x ¯ ) = z.
Since T F , G , H ⊢ L 2 ( F , G , H ), we have
M ⊨ ∃ ⁡ r ′ , r ′ is an attempt and ( α , x ¯ ) ∈ dom ⁡ r ′ ⏟ absolute .
Since it is absolute, r ′ is a real attempt.
By ???, r ′ ( α , x ¯ ) = r ( α , x ¯ ). Hence M ⊨ R ( α , x ¯ ) = z. □

html: Definition (Delta1T property). A property is called Δ 1 T if it’s both Σ 1 T and Π 1 T.
nothing: True

html: Corollary 2.3 (Minimality). Assuming that:
- T is a transitive model of ZF
Then for all α ∈ T ∩ Ord ⁡, 𝕃 α ⊆ T. Axiom of TODO.
proof: Proof. Let D = { D n : n ∈ ℕ }. Pick p 0 ∈ D 0 arbitrarily and define by recursion p i + 1 by picking some q ≤ p i with q ∈ D i + 1.
Then { p i : i ∈ ℕ } is a filter base, so let F be the filter generated by it. Then it is D-generic by construction. □
nothing: True

html: Definition (Forcing). 𝟙 ( ℙ , ≤ , 𝟙 ) is called a forcing poset or forcing if it is a partial order and 𝟙 𝟙 ∈ ℙ and 𝟙 𝟙 is the largest element. Elements of ℙ are called condition.
nothing: True

html: Definition (Compatible). p and q are compatible if there is r ≤ p , q. Otherwise, we say they are incompatible (which we write as p ⊥ q).
nothing: True

html: Definition (Antichain). A ⊆ P is an antichain if any two distinct elements of A are incompatible.
nothing: True

html: Definition (Dense). D ⊆ ℙ is dense if ∀ ⁡ p ∈ T O D O.
nothing: True

html: Definition (Filter). F ⊆ ℙ is called a filter if
- (a) ∀ ⁡ p , q ∈ F , ∃ ⁡ r ∈ F , r ≤ p , q
- (b) ∀ ⁡ p ∈ F , ∀ ⁡ q ∈ ℙ , q ≥ p ⟹ q ∈ F
If F only has property (a), we call it a filter base, and then
{ p ∈ ℙ : ∃ ⁡ q ∈ F , q ≤ p }
is the filter generated from F.
nothing: True

html: Definition (D-generic). If D is a family of dense sets, then F is called D-generic if F is a filter and ∀ ⁡ D ∈ D , D ∩ F ≠ ∅.
nothing: True

html: Theorem 3.1. Assuming that:
- D is countable
Then there is a D-generic filter.
proof: Proof. Let D = { D n : n ∈ ℕ }. Pick p 0 ∈ D 0 arbitrarily and define by recursion p i + 1 by picking some q ≤ p i with q ∈ D i + 1.
Then { p i : i ∈ ℕ } is a filter base, so let F be the filter generated by it. Then it is D-generic by construction. □
cloze1: True

html: Lemma 3.2. Assuming that:
- F ⊆ ℙ is a filter
Then ⋃ ⁡ F is a function.
proof: Proof. If x ∈ X, find p ∈ F ∩ D x, then x ∈ dom ⁡ ( p ), TODO □
cloze1: True

html: Lemma 3.3. D x : = { p ∈ ℙ : x ∈ dom ⁡ ( p ) } is a dense set. If D : = { D x : x ∈ X }, and F is D-generic, then dom ⁡ ( ⋃ ⁡ F ) = X.
proof: Proof. If x ∈ X, find p ∈ F ∩ D x, then x ∈ dom ⁡ ( p ), TODO □
cloze1: True

html: Lemma 3.4. Assuming that:
- Fix f : ω → 2 and define
N f : = { p ∈ ℙ : ∃ ⁡ u , p ( u ) ≠ f ( u ) } .
- F is D ∪ { N f }
Then ⋃ ⁡ F ≠ f.
proof: Proof. Fix y and define
A y : = { x ∈ X : ( ⋃ F ) ( x , y ) = 1 } .
E y , y ′ guarantees that y ↦ A y is an injection. □
cloze1: True

html: Corollary 3.5. There is no F that is D ∪ { N f | f : ω → 2 }-generic.
proof: Proof. Fix y and define
A y : = { x ∈ X : ( ⋃ F ) ( x , y ) = 1 } .
E y , y ′ guarantees that y ↦ A y is an injection. □
cloze1: True

html: Lemma 3.6. Assuming that:
- F is D ∪ R-generic
Then ⋃ ⁡ F : X → Y is a surjection.
proof: Proof. Fix y and define
A y : = { x ∈ X : ( ⋃ F ) ( x , y ) = 1 } .
E y , y ′ guarantees that y ↦ A y is an injection. □
cloze1: True

html: Corollary 3.7. Assuming that:
- | Y | > | X |
Then there is no D ∪ R-generic.
proof: Proof. Fix y and define
A y : = { x ∈ X : ( ⋃ F ) ( x , y ) = 1 } .
E y , y ′ guarantees that y ↦ A y is an injection. □
cloze1: True

html: Lemma 3.8. Assuming that:
- F is D ∪ E-generic
Then there is an injection from Y into P ( X ).
proof: Proof. Fix y and define
A y : = { x ∈ X : ( ⋃ F ) ( x , y ) = 1 } .
E y , y ′ guarantees that y ↦ A y is an injection. □
cloze1: True

html: Corollary 3.9. Assuming that:
- | Y | > | P ( ω ) |
Then there is no D ∪ E-generic.
proof: Proof. Induction. □
cloze1: True

html: 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.
nothing: True

html: Definition 3.11 (Generic extension). The (generic) extension for any countable transitive model M and any F ⊆ ℙ where ℙ ∈ M is
M [ F ] : = { val ⁡ ( τ , F ) : τ ∈ Name ⁡ ℙ ∩ M } .
nothing: True

html: Definition 3.12 (Canonical name). Let x ∈ M. Define by recursion the canonical name for x by
𝟙 w ˇ : = { ( y ˇ , 𝟙 ) : y ∈ x } .
nothing: True

html: Lemma 3.13. val ⁡ ( x ˇ , F ) = x if 𝟙 𝟙 ∈ F.
proof: Proof. Induction. □
cloze1: True

html: Corollary 3.14. M ⊆ M [ F ] if 𝟙 𝟙 ∈ F.
proof: Proof. Calculate:
val ⁡ ( Γ , F ) = { val ⁡ ( p ˇ , F ) : p ∈ F } = { p : p ∈ F } (by previous lemma) = F □
cloze1: True

html: Lemma 3.15. val ⁡ ( Γ , F ) = F.
proof: Proof. Calculate:
val ⁡ ( Γ , F ) = { val ⁡ ( p ˇ , F ) : p ∈ F } = { p : p ∈ F } (by previous lemma) = F □

html: Corollary 3.17. M [ F ] ⊨ Pairing (if 𝟙 𝟙 ∈ F).
proof: Proof. Suppose z ∈ val ⁡ ( u τ , F ).
So z = val ⁡ ( σ ′ , F ) for some ( σ ′ , r ) ∈ u τ with r ∈ F.
So ∃ ⁡ σ , p , q with ( σ , p ) ∈ τ, ( σ ′ , q ) ∈ σ, r ≤ p , q.
So p , q ∈ F. Hence val ⁡ ( σ , F ) ∈ val ⁡ ( τ , F ), z = val ⁡ ( σ ′ , F ) ∈ val ⁡ ( σ , F ).
So z ∈ ⋃ ⁡ val ⁡ ( τ , F ).
Conversely, suppose z ∈ ⋃ ⁡ val ⁡ ( τ , F ). Then ∃ ⁡ y , z ∈ y ∈ val ⁡ ( τ , F ) (z → ( σ ′ , q ) ∈ σ with q ∈ F, y → ( σ , ρ ) ∈ τ with p ∈ F).
Hence since F a filter, find r ≤ p , q with r ∈ F.
Then ( σ ′ , r ) ∈ u τ, so z ∈ val ⁡ ( u τ , F ). □
cloze1: True

html: Definition (Forcing language). Fix M a countable transitive model of ZFC, ℙ ∈ M a forcing poset.
We call the language
L forcing : = L ∈ ∪ { τ : ℙ -names }
the forcing language (over M).
nothing: True

html: 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 ).
nothing: True

html: Definition (Semantic forcing predicate). p ⊩ M , ℙ φ: Forall G ℙ-generic over M with p ∈ G, M [ G ] ⊨ φ.
“p forces φ”
We often omit M , ℙ.
nothing: True

html: Proof of Replacement.
Since we already have Separation, it’s enough to show the following:
if φ is a functional formula and x ∈ M [ G ], then there is R ∈ M [ G ] such that
M [ G ] ⊨ ∀ ⁡ y ∈ x , ∃ ⁡ z ∈ R , φ ( y , z , 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 ⁡ ( σ ) ⊆ V α. Consider ψ ( p , π ) : = ∃ ⁡ μ , p ⊩ φ ( π , μ ) (p ∈ ℙ, π a name). By Definability Theorem, this is an L ∈ formula.
By Levy Reflection Theorem, find 𝜃 > α such that ψ is absolute between V 𝜃 and V = M. Define
ρ : = { ( μ , 1 ) : μ ∈ V 𝜃 }
and R : = val ⁡ ( ρ , G ).
Now we verify (∗) holds: Fix y ∈ x, y = val ⁡ ( π , G ). Since φ is functional, we know that φ ( π , μ ) holds in M [ G ] for some μ. By Forcing Theorem, there is p ∈ G such that p ⊩ φ ( π , μ ). So M ⊨ ψ ( p , π ).
By absoluteness, V 𝜃 ⊨ ψ ( p , π ). This means ∃ ⁡ μ ∈ V 𝜃 such that p ⊩ φ ( π , μ ).
Thus: val ⁡ ( μ , G ) ∈ val ⁡ ( ρ , G ) = R.
□
cloze1: True

html: Definition (Dense below p). D ⊆ ℙ is called dense below p if ∀ ⁡ q ≤ p , ∃ ⁡ r ≤ q , r ∈ D.
nothing: True

html: Lemma 3.18. Assuming that:
- G is ℙ-generic over M
- E ⊆ ℙ
- E ∈ M
Then
- (i) If E is dense below p, q ≤ 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 ∩ E ≠ ∅ or ∃ ⁡ q ∈ G, ∀ ⁡ r ∈ E , r ⊥ q.
- (iv) If p ∈ G, E is dense below p, then G ∩ E ≠ ∅.
proof: Proof. Example Sheet 3 □
cloze1: True

html: Lemma 3.19. The following are equivalent:
- (i) p ⊩ ∗ φ.
- (ii) ∀ ⁡ r ≤ p , r ⊩ ∗ φ.
- (iii) { r : r ⊩ ∗ φ } is dense below ρ.
proof: Proof. If this is true for φ of the form τ 0 = τ 1 and of the form τ 0 ∈ τ 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). □

html: Theorem 3.20 (Syntactic Forcing Theorem). M [ G ] ⊨ φ if and only if ∃ ⁡ p ∈ G , M ⊨ r ⊩ ∗ φ.
proof: Proof of Definability Theorem from Syntactic Forcing Theorem.
- ⇐ This is just Syntactic Forcing Theorem.
- ⇒ Suppose p ⊩ φ. By Lemma 3.18, we need to show
{ r ≤ p : r ⊩ ∗ φ }
is dense below p.
Suppose not. Then I find q ≤ p such that ∀ ⁡ r ≤ q, r ⁄ ⊩ ∗ φ. So q ⊩ ∗ ¬ ⁡ φ.
If q ∈ G, then p ∈ G. Since p ⊩ φ, M [ G ] ⊨ φ. Since q ⊩ ∗ ¬ ⁡ φ, M [ G ] ⊨ ¬ ⁡ φ. Contradiction! □
nothing: True

html: Corollary 3.21 (Definability Theorem). p ⊩ φ if and only if p ⊩ ∗ φ.
proof: Proof of Definability Theorem from Syntactic Forcing Theorem.
- ⇐ This is just Syntactic Forcing Theorem.
- ⇒ Suppose p ⊩ φ. By Lemma 3.18, we need to show
{ r ≤ p : r ⊩ ∗ φ }
is dense below p.
Suppose not. Then I find q ≤ p such that ∀ ⁡ r ≤ q, r ⁄ ⊩ ∗ φ. So q ⊩ ∗ ¬ ⁡ φ.
If q ∈ G, then p ∈ G. Since p ⊩ φ, M [ G ] ⊨ φ. Since q ⊩ ∗ ¬ ⁡ φ, M [ G ] ⊨ ¬ ⁡ φ. Contradiction! □
nothing: True

html: Corollary 3.22 (Forcing Theorem). M [ G ] ⊨ φ if and only if ∃ ⁡ p ∈ G , p ⊩ φ.
proof: Proof of Definability Theorem from Syntactic Forcing Theorem.
- ⇐ This is just Syntactic Forcing Theorem.
- ⇒ Suppose p ⊩ φ. By Lemma 3.18, we need to show
{ r ≤ p : r ⊩ ∗ φ }
is dense below p.
Suppose not. Then I find q ≤ p such that ∀ ⁡ r ≤ q, r ⁄ ⊩ ∗ φ. So q ⊩ ∗ ¬ ⁡ φ.
If q ∈ G, then p ∈ G. Since p ⊩ φ, M [ G ] ⊨ φ. Since q ⊩ ∗ ¬ ⁡ φ, M [ G ] ⊨ ¬ ⁡ φ. Contradiction! □
nothing: True

html: Definition (Preserves cardinals). We say ℙ preserves cardinals if ∀ ⁡ G ℙ-generic over M, “κ is a cardinal” is absolute between M and M [ G ].
nothing: True

html: 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.
nothing: True

html: Theorem 3.24. Assuming that:
- ℙ has countable chain condition
Then ℙ preserves cardinals.
proof: Proof of Theorem 3.24 . Suppose M ⊨ κ is a cardinal, M [ G ] ⊨ κ is not a cardinal, so there is λ < κ and f ∈ M [ G ], f : λ → κ, f is a surjection. Apply the lemma to get F.
Define R : = ⋃ ⁡ α < λ F ( α ).
Since ∀ ⁡ x , f ( x ) ∈ F ( x ), R = κ.
But M ⊨ | R | = ℵ 0 ⋅ λ = λ < κ. But then M thinks that κ is not a cardinal, contradiction. □
cloze1: True

html: Theorem 3.25. Fn ⁡ ( ω × ℵ 2 M , 2 ) has the countable chain condition.
proof: Proof of Theorem 3.24 . Suppose M ⊨ κ is a cardinal, M [ G ] ⊨ κ is not a cardinal, so there is λ < κ and f ∈ M [ G ], f : λ → κ, f is a surjection. Apply the lemma to get F.
Define R : = ⋃ ⁡ α < λ F ( α ).
Since ∀ ⁡ x , f ( x ) ∈ F ( x ), R = κ.
But M ⊨ | R | = ℵ 0 ⋅ λ = λ < κ. But then M thinks that κ is not a cardinal, contradiction. □
cloze1: True

html: Corollary 3.26. Assuming: - G is Fn ⁡ ( ω × ℵ 2 M , 2 )-generic over M, then
M [ G ] ⊨ ZFC + 2 ℵ 0 ≥ ℵ 2 .
proof: Proof of Theorem 3.24 . Suppose M ⊨ κ is a cardinal, M [ G ] ⊨ κ is not a cardinal, so there is λ < κ and f ∈ M [ G ], f : λ → κ, f is a surjection. Apply the lemma to get F.
Define R : = ⋃ ⁡ α < λ F ( α ).
Since ∀ ⁡ x , f ( x ) ∈ F ( x ), R = κ.
But M ⊨ | R | = ℵ 0 ⋅ λ = λ < κ. But then M thinks that κ is not a cardinal, contradiction. □

html: Lemma 3.27. Assuming that:
- M ⊨ ℙ has countable chain condition
- X , Y ∈ M
- G is ℙ-generic over M
- f : X → Y, f ∈ M [ G ]
Then there is F ∈ M such that ∀ ⁡ x ∈ X , F ( x ) ⊆ Y, ∀ ⁡ x ∈ X , f ( x ) ∈ F ( x ) and M ⊨ ∀ ⁡ x ∈ X , F ( x ) is countable.
proof: Proof of Theorem 3.24 . Suppose M ⊨ κ is a cardinal, M [ G ] ⊨ κ is not a cardinal, so there is λ < κ and f ∈ M [ G ], f : λ → κ, f is a surjection. Apply the lemma to get F.
Define R : = ⋃ ⁡ α < λ F ( α ).
Since ∀ ⁡ x , f ( x ) ∈ F ( x ), R = κ.
But M ⊨ | R | = ℵ 0 ⋅ λ = λ < κ. But then M thinks that κ is not a cardinal, contradiction. □
cloze1: True

html: Definition (Cofinal). C ⊆ κ is cofinal (= unbounded) if ∀ ⁡ λ < κ , ∃ ⁡ γ ∈ C , γ ≥ λ. We can then define:
cf ⁡ κ : = { | C | : C is cofinal } .
nothing: True

html: Lemma 3.29 (Kőnig’s Lemma). κ cf ⁡ κ > κ.
proof: Proof. Start with M such that val ⁡ ( μ , G ) = x (possibly not nice). Fix n ∈ ω. Fix either a well-ordering of ℙ (possibly using AC to get one) and build a maximal antichain A n such that ∀ ⁡ p ∈ A n, ň p ⊩ ň ∈ μ.
TODO.
Claim: val ⁡ ( μ , G ) = val ⁡ ( τ OL ⁡ , G ).
⊇: If n ∈ val ⁡ ( τ O L , G ), then there is p ∈ G such that ň ( ň , p ) ∈ τ OL ⁡, and then p ∈ A n, so ň p ⊩ ň ∈ μ. So n ∈ val ⁡ ( μ , G ).
⊆: If n ∈ val ⁡ ( μ , G ), then by Forcing Theorem, get q ∈ G such that ň q ⊩ ň ∈ μ.
Subclaim: A n ∩ G ≠ ∅. Indeed, by our lemma on compatibility ( Example Sheet 3), get q ′ ∈ G such that q ′ ⊥ p for all p ∈ A n. Find r ≤ q , q ′. Then ň r ⊩ ň ∈ μ. But that is in contradiction to A n being maximal.
So find p ∈ G ∩ A n. By definition, ň ( ň , p ) ∈ τ OL ⁡ and p ∈ G. So n ∈ val ⁡ ( τ OL ⁡ , G ). □
nothing: True

html: Theorem 3.30. Assuming that:
- M [ G ] ⊨ x ⊆ ω
Then there is a nice name τ such that val ⁡ ( τ , G ) = x.
proof: Proof. Start with M such that val ⁡ ( μ , G ) = x (possibly not nice). Fix n ∈ ω. Fix either a well-ordering of ℙ (possibly using AC to get one) and build a maximal antichain A n such that ∀ ⁡ p ∈ A n, ň p ⊩ ň ∈ μ.
TODO.
Claim: val ⁡ ( μ , G ) = val ⁡ ( τ OL ⁡ , G ).
⊇: If n ∈ val ⁡ ( τ O L , G ), then there is p ∈ G such that ň ( ň , p ) ∈ τ OL ⁡, and then p ∈ A n, so ň p ⊩ ň ∈ μ. So n ∈ val ⁡ ( μ , G ).
⊆: If n ∈ val ⁡ ( μ , G ), then by Forcing Theorem, get q ∈ G such that ň q ⊩ ň ∈ μ.
Subclaim: A n ∩ G ≠ ∅. Indeed, by our lemma on compatibility ( Example Sheet 3), get q ′ ∈ G such that q ′ ⊥ p for all p ∈ A n. Find r ≤ q , q ′. Then ň r ⊩ ň ∈ μ. But that is in contradiction to A n being maximal.
So find p ∈ G ∩ A n. By definition, ň ( ň , p ) ∈ τ OL ⁡ and p ∈ G. So n ∈ val ⁡ ( τ OL ⁡ , G ). □
cloze1: True

html: Corollary 3.31. Assuming that:
- ℙ has countable chain condition
- M ⊨ | ℙ | = κ ∧ λ = κ ℵ 0
Then M [ G ] ⊨ 2 ℵ 0 ≤ λ.
proof: Proof. Follows directly from:
- (a) Theorem.
- (b) Calculation of the number of nice names.
□
cloze1: True

html: Definition (l a m b d a-nice names). Generalise “nice names” to λ-nice names:
Let
OL ⁡ = { A α : α < λ }
be a family of λ many maximal ℙ-antichains:
τ OL ⁡ : = { ( α ˇ , p ) : p ∈ A α }
for α ∈ λ.
These are names for subsets of λ.
nothing: True

html: 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 ≤ p α for all α < γ.
nothing: True

html: Theorem 3.33. Assuming that:
- ℙ is λ-closed and κ < λ
Then
P ( κ ) ∩ M = P ( κ ) ∩ M [ G ] .
proof: Proof. Let f ∈ M [ G ], f : κ → 2 and assume towards contradiction that f ∉ M. → f ∉ B.
B : = { f ∈ M | f : M → 2 } .
Let τ be a name for f.
By Forcing Theorem, there is p ∈ G such that p ⊩ τ : κ ˇ → 2 ˇ ∧ τ ∉ B ˇ.
Construct a κ-sequence of conditions p α TODO
TODO
The sequence { p α : α ≤ κ } is defined in M (by Definability Theorem), so we can define
g ( α ) = 1 : ⟺ p α + 1 ⊩ τ ( α ˇ ) = 1 ˇ .
Then g ∈ M.
But now p κ ⊩ τ ( α ˇ ) = 1 ˇ or p κ ⊩ τ ( α ˇ ) = 0 ˇ for all α.
uso ǧ p k ⊩ τ = ǧ. Hence p κ ⊩ τ ∈ B ˇ.
But p κ ≤ p ⊩ τ ∉ B ˇ. Contradiction. □
cloze1: True

html: Corollary 3.34. Forcing with Fn ⁡ ( ℵ 1 × ℵ 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).
proof: Proof. Let f ∈ M [ G ], f : κ → 2 and assume towards contradiction that f ∉ M. → f ∉ B.
B : = { f ∈ M | f : M → 2 } .
Let τ be a name for f.
By Forcing Theorem, there is p ∈ G such that p ⊩ τ : κ ˇ → 2 ˇ ∧ τ ∉ B ˇ.
Construct a κ-sequence of conditions p α TODO
TODO
The sequence { p α : α ≤ κ } is defined in M (by Definability Theorem), so we can define
g ( α ) = 1 : ⟺ p α + 1 ⊩ τ ( α ˇ ) = 1 ˇ .
Then g ∈ M.
But now p κ ⊩ τ ( α ˇ ) = 1 ˇ or p κ ⊩ τ ( α ˇ ) = 0 ˇ for all α.
uso ǧ p k ⊩ τ = ǧ. Hence p κ ⊩ τ ∈ B ˇ.
But p κ ≤ p ⊩ τ ∉ B ˇ. Contradiction. □
cloze1: True