#forcing

A theory T is a set of axioms in first order logic. A proof in T is a sequence φ₁ .. φₙ of formulas such that each formula is an axiom of T or follows logically from previous formulae in the sequence, this proof is said to prove the formula φₙ. For a formula φ, we write T ⊦ φ to mean that there is a proof φ₁ .. φₙ (φ = φₙ) of φ in T. T is inconsistent if it proves the always false statement ⊥, T is consistent if it does not prove this statement. We write Con(T) for “T is consistent”. T ⊬ φ is equivalent to Con(T + ¬φ), so to show that ZFC cannot prove or disprove CH, we want to show Con(ZFC + ¬CH) and Con(ZFC + CH), assuming that ZFC is consistent.

To show that Con(ZFC) implies Con(ZFC + ¬CH), we start with a model V of ZFC and add ω₂ many reals (subsets of ω) to it. However, we don't have anywhere to get those ω₂ reals from ¯\(˙˘˙)/¯ We can't get them simply out of V as that'd mean V already has at least ω₂ many reals. What we do is assume the existence of a larger universe V⁺ that V lives in. Usually, when forcing, the existence of the larger universe V⁺ is implicit, but I state its existence explicitly to avoid confusion.

We can try to define a theory ZFC⁺ extending ZFC by adding a constant symbol V (the universe of ZFC⁺ is called V⁺ rather than V) and the axiom “V is a model of ZFC”, however, even without assuming nice properties of V like it being a well-founded model, the consistency of ZFC⁺ is stronger than that of ZFC, but ideally, we want to show that Con(ZFC + ¬CH) follows from Con(ZFC), not Con(ZFC⁺).

Luckily, ZFC already sort-of proves the existence of models of ZFC. To be more precise, for every finite fragment t of ZFC, ZFC proves that there is a model of t. However, ZFC does not prove the statement ‘for all finite fragments t of ZFC, there is a model of t’! ∀n T ⊦ φ(n) and T ⊦ ∀n φ(n) are two different statements, it's important to know the distinction!

Let t be a finite fragment of ZFC, aiming to show that ZFC ⊦ ∃M M ⊧ t (⊧ is the symbol for ‘satisfies’ or ‘is a model of’). We'll build the model M by starting with the empty set M_0 = ∅ and adding more and more elements to it until it satisfies ZFC. Since t is a finite fragment of ZFC, we have that V ⊧ t. If t were to be infinite, V ⊧ t would be an infinite conjunction of the formulas in t, and infinite formulas don't exist in first order logic, hence we assume t to be finite. To build the next model M_1, for every formula of the form ∃x φ(x) that t proves, we have that V ⊧ ∃x φ(x), and thus there is some x such that φ(x). We add some x that satisfies φ(x) to M_1 for every such formula ∃x φ(x). We do the same for M_2, but instead of adding x for each ∃x φ(x), we add some x for every y in M_1 and every formula of the form ∃x φ(x,y) that t proves. We do the same with M_3: we add some x satisfying φ(x,y) for every y ∈ M_2 and every formula of the form ∃x φ(x,y) that t proves. We continue this infinitely, and we then define M = ⋃{M_n | n ∈ ℕ} as the union of all M_n. By induction on the complexity of formulas, we can show that M ⊧ φ for every φ such that t ⊦ φ, proving this is left as an exercise to the reader.

Since there are only countably many formulas, every M_n must be countable, and so their union, M, is countable as well. We also have that M is a standard model: it has sets x and uses the real membership relation as its own membership relation. Besides showing that for every finite fragment t of ZFC, ZFC proves that there exists a model of t, we have shown that we can assume this model to be standard and countable.

The construction of the model M we have performed is called a Skolem hull. Usually, when taking Skolem hulls, we take all formulas φ that the original model (in this case, V) satisfies instead of only those that are proven by some theory t, but we couldn't do that as there are an infinite amount of models that V satisfies and a proof in ZFC may only use a finite number of axioms. Skolem hulls are my second favourite thing from model theory and it could be useful to have it in your toolbox.

Although M is a standard model of the theory t, it isn't transitive. A transitive set is a set X such that, for every x ∈ X, we have x ⊂ X. It's usually easier to work with transitive models. We can turn M into a transitive model by the use of a Mostowski collapse. You can read the Wikipedia article on it if you want to know what that is, this is a post about forcing, not Mostowski collapses and Skolem hulls.

Instead of adding the axiom ‘V is a model of ZFC’ to ZFC⁺, we can add, for each individual axiom φ of ZFC, the axiom ‘V ⊧ φ’. And, as we have shown above, we can also add the axiom ‘V is countable and transitive’. Since proofs in ZFC⁺ may only use a finite amount of axioms, they may only use a finite amount of axioms of the form ‘V ⊧ φ’, so ZFC⁺ thinks that V satisfies finite fragments of ZFC without realizing it satisfies the whole of ZFC: it might think there is a very long formula φ that V doesn't satisfy while, in reality, such a formula would be infinitely long and doesn't actually exist.

One theorem from logic that we'll use is the compactness theorem. This theorem states that, for a theory T of first order logic, if T is inconsistent then a finite fragment of T is inconsistent. Contrapositively, if every finite fragment of T is consistent, then T must be consistent as well. A proof of this theorem is quite easy.

Another important lemma we'll use is that if a theory T proves a finite theory S is consistent, then S must be consistent. If S were to be inconsitent, then there must be some proof φ₁ .. φₙ of ⊥ in S, and T would prove that φ₁ .. φₙ is a proof of ⊥ as checking if a proof is correct is as simple as just running an algorithm. Thus, for a finite fragment S of ZFC+¬CH, if ZFC⁺ proves S is consistent, then S must be consistent. And if ZFC⁺ proves S is consistent for every finite fragment S of ZFC+¬CH, then ZFC+¬CH must be consistent by compactness.

Since V is countable in V⁺, the ω₂ of V, written ω₂^V, is a countable ordinal in V⁺ while the ω₂ of V⁺, written ω₂^V⁺, doesn't exist in V. I'll work in the universe V unless otherwise specified, so ω₂ refers to ω₂^V rather than ω₂^V⁺, and countable means countable in V rather than countable in V⁺. For some object x and a model M, x^M refers to the interpretation of x in M.

So now that we have the little universe V and the big universe V⁺, we want to add ω₂ reals to V. Since V is countable in V⁺, there are a lot of things outside of V in V⁺. For example, P(ω) ∩ V is countable in V⁺, while the P(ω) of V⁺ is uncountable in V⁺, meaning that P(ω) \ V must be uncountable, so V is missing a lot of reals that can be added into V. However, if we simply take a set X ⊂ P(ω)^V⁺ such that V thinks X has cardinality ω₂, and then add it to V by just adjoining it like so: V ∪ {X}, this new model is no longer a model of ZFC. It has a universe V, but also just another object X adjoint to it, and things like X ∪ ℕ, X × X, etc, don't exist, while they should for V ∪ {X} to be a model of ZFC.

Thus, instead of adding a single new element X, forcing aims to add an object G in such a way that the axioms of ZFC are still satisfied. It does this through the use of names. A name is an object in V that describes an object in the extended universe V[G], but without a way to interpret the name in V, those objects that exist in V[G] don't yet exist in V. The object G gives a way to interpret the names in V, and interpreting every name in V through G gives the new model V[G]. Explaining what that means exactly requires the definition of a forcing poset, which I'll now explain.

A partial ordered set (poset) is a structure (P,≤) with a set P and a binary relation ≤ on P, such that:

≤ is reflexive: x ≤ x for all x ∈ P.

≤ is transitive: if x ≤ y and y ≤ z then x ≤ z for all x,y,z ∈ P.

≤ is antisymmetric: if x ≤ y and y ≤ x then x = y for all x,y ∈ P.

Two elements x,y ∈ P are compatible if there is some z such that z ≤ x and z ≤ y. x and y are incompatible if no such z exists. A forcing poset is a poset P with the additional axioms:

There is a greatest element 1 ∈ P.

For every x ∈ P, there are y,z ∈ P such that y ≤ x, z ≤ x and y and z are incompatible.

The last axiom is called the splitting condition. Members of a forcing poset P are called forcing conditions. x ≤ y is read as ‘x is stronger than y’ or ‘x extends y’. Forcing conditions can be thought of as statements that can be true or false, these statements say something about the object being added, where the greatest element 1 is a statement that is always true. The forcing poset that we'll focus on in this blog post is called Cohen forcing. Forcing conditions are finite partial functions from ω₂ × ω to {0,1}. That is, functions from a finite subset of ω₂ × ω to the set {0,1}. For forcing conditions p and q, p ≤ q iff p is a function extension of q, i.e. dom(p) ⊃ dom(q) and p(α,n) = q(α,n) for all (α,n) ∈ dom(q). A forcing condition p: ω₂ × ω ⇀ {0,1} says something about the object g: ω₂ × ω → {0,1} that is being added, namely, that g(x) = p(x) for all x ∈ dom(p). For every α < ω₂, {n | g(α,n) = 1} will be a new real in the new model V[G], meaning that there will be ω₂ many new reals and CH will break.

For a forcing poset P, a P-name is a set of tuples (σ,p) where σ ∈ V^P is a P-name and p ∈ P is a forcing condition, this set may be empty. Alternatively, the class of P-names, V^P, can be defined by induction:

V^P_0 = ∅.

V^P_α+1 = P(V^P_α × P) for an ordinal α.

V^P_α = ⋃{β<α} V^P_β for limit ordinal α.

Then, V^P = ⋃{α ∈ Ord} V^P_α is the class of P-names. A P-name {(σ,p)} means ‘this set contains σ iff p is true’. Thus, for a set x, we can define a P-name &x for x as follows &x = {(&y,1) | y ∈ x} as 1 is always true. We can also define the set of all true forcing conditions as &G = {(&p,p) | p ∈ P}, which contains p iff p is true.

A way to decide which forcing conditions are true and which are false is done using a filter. A filter F on P is a subset F ⊂ P such that:

1 ∈ F.

If x ∈ F and x ≤ y, then y ∈ F.

For all x,y ∈ F, there is some z ∈ F such that z ≤ x and z ≤ y.

A filter decides what forcing conditions are true and which are false: members of the filter are true forcing conditions, while things that aren't in the filter are false. The first axiom of a filter, 1 ∈ F, states that the statement 1 is true, the second axiom states that x is true and x implies y, then y is true, and the third statement states that no members of the filter contradict each other (i.e. none are incompatible).

However, not any filter will do. If the filter F is already in the model V, then we don't add anything new to V. It might also be possible to break axioms of ZFC such as comprehension with certain filters. Because of this, we use a special filter called a generic filter.

A forcing poset P has a topology. An open set in P is a set O ⊂ P that is downwards closed, i.e. for every x ∈ O and every y ∈ P such that y ≤ x, we have y ∈ O. A set D is dense if it meets all non-empty open sets. In P, that means that D is dense iff ∀x ∈ P ∃y ∈ D y ≤ x. For a family D of dense subsets of P, a filter G ⊂ P is D-generic iff G meets all dense D ∈ D. One important theorem used to construct generic sets is the Rasiowa-Sikorski lemma. This lemma states that, if P is a forcing poset, p ∈ P is a forcing condition, and D is a countable family of dense subsets of P, then there is a D-generic filter G on P that contains p. A proof of this lemma is left as an exercise to the reader. Since V is countable in V⁺, we can apply the Rasiowa-Sikorski lemma to it: we can define a V-generic filter as a filter that is D-generic filter for D = {D ∈ V | D is a dense subset of P}, and since D is countable in V⁺, such a generic filter G exists in V⁺. I'll often call a V-generic filter simply a generic filter.

Given a forcing poset P ∈ V, a generic filter G ⊂ P on P and a P-name σ ∈ V^P, the interpretation of σ by G is defined as σ^G := {τ^G | ∃p ∈ G (τ,p) ∈ σ}. One can verify that, for x ∈ V, we have &x^G = x and &G^G = G for &G = {(&p,p) | p ∈ P}. V[G] is defined as V[G] = {σ^G | σ ∈ V^P}. Now, all we have to do is verify that V[G] is indeed a model of ZFC and, when P is Cohen forcing, that V[G] satisfies ¬CH.

Im eepy. I'll do that another day -.- Good night.

Hi. I hope you slept well. I'll now continue with explaining forcing.

For a forcing condition p ∈ P, P-names τ₁ .. τₙ and a formula φ, p forces φ(τ₁ .. τₙ), denoted p ⊩ φ(τ₁ .. τₙ), if for all generic G ⊂ P with p ∈ G, we have V[G] ⊧ φ(τ₁^G .. τₙ^G). The following three lemmas are important in forcing:

Definability For every formula φ, there is a formula ψ such that for all forcing conditions p and all P-names τ₁ .. τₙ, p ⊩ φ(τ₁ .. τₙ) iff V ⊧ ψ(p,τ₁ .. τₙ). I.e. ‘p forces φ(τ₁ .. τₙ)’ is definable in V.

Coherence If p ⊩ φ(τ₁ .. τₙ) and q ≤ p, then q ⊩ φ(τ₁ .. τₙ).

Truth If V[G] ⊧ φ(τ₁^G .. τₙ^G) then there is some forcing condition p such that p ⊩ φ(τ₁ .. τₙ). That is, a statement is true iff it is forced.

I encourage you to try proving these lemmas yourself. Coherence is quite easy, but the other two might be more difficult to prove. I'll give a proof for definability and truth.

First, we'll define ⊩* by induction on the complexity of formulas. We'll start with atomic formulas. When does p force σ ∈ τ? One naive guess might be if ∃q ≥ p (σ,q) ∈ τ, however, this doesn't quite work. There might be a P-name ρ such that σ ≠ ρ, yet p ⊩ σ = ρ and ∃q ≥ p (ρ,q) ∈ τ but ∄q ≥ p (σ,q) ∈ τ. Thus, we define p ⊩* σ ∈ τ as ∃(ρ,q) ∈ τ p ⊩* σ = ρ.

So now we need to define p ⊩* σ = τ. By the axiom of extensionality, two sets are equal if they contain the same elements. Thus, we can define p ⊩* σ = τ as ∀ρ ∈ V^P p ⊩* "ρ ∈ σ" ⇔ p ⊩* "ρ ∈ τ". This might seem self-referential, as we define equality in terms of membership, which is itself defined in terms of equality, but we can define it inductively as the rank of the names always decrease. The rank of σ is the smallest ordinal α such that σ is in V^P_{α+1}. The quantor '∀ρ ∈ V^P' currently ranges of all P-names (thus, also those with higher rank than σ or τ), but we can fix that by defining ⊩* ≠ instead of ⊩* =, and then we can define p ⊩* σ = τ as p ⊩* ¬σ ≠ τ.

p ⊩* σ ≠ τ iff (∃(ρ,q) ∈ τ q ≥ p ∧ p ⊩* ¬ρ ∈ σ) ∨ (∃(ρ,q) ∈ σ q ≥ p ∧ p ⊩* ¬ρ ∈ τ).

So now we can define ⊩* ¬, ⊩* ∨ and ⊩* ∃ as follows:

p ⊩* ¬φ(τ₁ .. τₙ) iff ∀q ≤ p ¬q ⊩* φ(τ₁ .. τₙ).

p ⊩* "φ(τ₁ .. τₙ) ∨ ψ(τ₁ .. τₙ)" iff p ⊩* "φ(τ₁ .. τₙ)" ∨ p ⊩* "ψ(τ₁ .. τₙ)".

p ⊩* ∃x φ(x, τ₁ .. τₙ) iff ∃σ ∈ V^P p ⊩* φ(σ, τ₁ .. τₙ).

This internal definition of forcing is almost complete. However, what if a formula φ is forced by p, not because φ is immediately apparent, but because the only forcing conditions that extend p immediately force φ? To give a more concrete example, suppose σ = ∅, τ = {(σ,p), (σ,q)} are P-names, and p = {((0,0),0)} and q = {((0,0),1)} are (incompatible) forcing conditions in Cohen forcing. Then, we don't have 1 ⊩* σ ∈ τ, however, σ ∈ τ is still forced by 1 as any generic filter that contains 1 also contains p or q. Thus, the final step of the definition of forcing is p ⊩ φ(τ₁ .. τₙ) iff {q | q ⊩* φ(τ₁ .. τₙ)} is dense below p, equivalently, p ⊩ φ(τ₁ .. τₙ) iff p ⊩* ¬¬φ(τ₁ .. τₙ).

The last part of the proof of definability is checking that our internal definition of forcing is correct. This is left as an exercise to the reader.

Now I'll give a proof of truth. Although in no point in the proof of definability genericity is relevant, it is very important for truth. Truth states that for a formula φ and P-names τ₁ .. τₙ, if V[G] ⊧ φ(τ₁ .. τₙ), then there is some p ∈ G so that p ⊩ φ(τ₁ .. τₙ). That is, a formula is true if and only if it is forced.

For a statement φ and P-names τ₁ .. τₙ, we can define the set D_φ = {p | p ⊩ φ(τ₁ .. τₙ) ∨ p ⊩ ¬φ(τ₁ .. τₙ)}. Thus, D_φ is the set of forcing conditions that decide φ. We can verify that D_φ is a dense set: we have 1 ⊩ φ ∨ ¬φ as φ ∨ ¬φ is always true, this is equivalent to 1 ⊩* ¬¬(φ ∨ ¬φ) when using the internal definition, i.e. {p | p ⊩* φ ∨ ¬φ} = {p | p ⊩* φ ∨ p ⊩* ¬φ} is dense, and since D_φ is a superset of this set, it must be dense as well. Since D_φ is dense and G is generic, G ∩ D_φ must be non-empty, so some p ∈ G must force φ or force ¬φ. Thus, every formula that is true in V[G] is forced by some forcing condition in G.

We can use definability, coherence and truth to prove that V[G] ⊧ ZFC. I'll leave this as an exercise to reader, cuz... why not ¯\(˙˘˙)/¯ Extensionality and foundation hold in V[G] as V[G] is a transitive model of ZFC, union and infinity aren't too difficult to prove, separation and powerset might be a bit more tricky, the argument for why V[G] satisfies replacement is similar to that of separation, and choice might be a little bit more difficult than the others. I'll give a proof for why V[G] satisfies the axiom lemma of pairing so you have some inspiration for your proof.

Given sets x and y in V[G], we want to show that {x,y} is a set. x and y have P-names, let's call them σ and τ. We can now define a P-name ρ := {(σ,1), (τ,1)}. We can see that ρ^G = {σ^G, τ^G} = {x,y} ∈ V[G], and thus V[G] satisfies the lemma of pairing.

So now that we know V[G] is a model of ZFC (at least, for every finite fragment t of ZFC, ZFC⁺ proves that V[G] is a model of t), we now need to show that V[G] ⊧ ¬CH when using Cohen forcing. We want to add more than ω₁ reals, e.g. ω₂ reals, to the model V. We thus want G to encode information for a set of ω₂ distinct reals. Since a real is an infinite sequence of 0s and 1s, we thus want a ω₂ × ω table of 0s and 1s so that none of the rows are equal. In Cohen forcing, the forcing conditions encode partial information about this ω₂ × ω table. The forcing conditions are finite partial functions from ω₂ × ω to {0,1}, i.e. functions with finitely many pairs (α,n) for ordinals α < ω₂ and natural numbers n as domain, that maps each (α,n) in its domain to either 0 or 1. For forcing conditions p and q, we have p ≤ q iff p is a function extension of q, i.e. dom(q) ⊂ dom(p) and p(α,n) = q(α,n) for all (α,n) ∈ dom(q). A generic filter G on P would thus consist of finite partial functions p: ω₂ × ω ⇀ {0,1} that together form a function g: ω₂ × ω → {0,1} defined as g = ⋃G. For each ordinal α, r_α = {n | g(α,n) = 1} ⊂ ω is a real in the model V[G]. We can use the genericity of G to show that all reals r_α are distinct: suppose we have r_α = r_β for some α ≠ β. Then, there must be some p ∈ G such that p ⊩ r_α = r_β. However, no such p can exist: p may only contain finite information about r_α and r_β, but r_α = r_β means that g(α,n) and g(β,n) are equal on all, and thus infinitely many, n. We can define a dense set D_{α,β} = {p ∈ P | ∃n p(α,n) ≠ q(β,n)}, it's easy to check that this set is dense for α ≠ β, and thus G ∩ D_{α,β} is non-empty. This means that all reals r_α are indeed distinct reals. We thus have added ω₂ distinct reals to V.

But we're still missing something. Can you spot it? No..? Oh, okay. Don't worry. I'll tell you. We have added ω₂^V reals, but we need ω₂^V[G] reals, and nothing so far tells us that ω₂^V and ω₂^V[G] should be equal!

Luckily, they are equal. Here is proof:

Cohen forcing satisfies the countable chain condition. A (strong) antichain A ⊂ P is a set of forcing conditions that are pairwise incompatible, i.e. ∀p,q ∈ A p ≠ q → p ⊥ q. Usually, the word antichain is used to refer to sets of pairwise incomparable elements, but incomparability is kinda useless when forcing as opposed to incompatibility (two objects x and y in a poset are incomparable iff x ≰ y and y ≰ x). The κ-chain condition (κ-c.c) states that, given any antichain A ⊂ P, the cardinality of A is <κ. The countable chain condition (c.c.c) is the ω₁-chain condition, i.e. all antichains are countable.

If P satisfies the c.c.c, then for every function f ∈ V[G] from some D ∈ V to V, there is a function F ∈ V[G] from D to V such that, for every x ∈ D, F(x) is countable and f(x) ∈ F(x). I.e. functions in V[G] can be approximated by "countable covering functions" in V (‘countable covering function’ is not a term, I just made that up :p).

The above lemma can be used to show that, when P has the countable chain condition, if κ is an uncountable regular cardinal in V, then κ must also be uncountable regular in V[G]. In otherwords, for any uncountable regular cardinal κ, P does not collapse κ (P collapses κ if κ is no longer a regular cardinal in the forcing extension V[G]). Proving these three things ((i) Cohen forcing has the c.c.c, (ii) if P has the c.c.c then for every function f: D → V in V[G] for D ∈ V has a "countable covering function" and (iii) if P has the c.c.c then it collapses no regular cardinals) are left as an exercise to the reader.

And that completes the proof of Con(ZFC) → Con(ZFC + ¬CH). Good night everyone! mi wile lape -.- If you have trouble understanding something in this blog post, or you have some other questions, you can tell me! Holidays are starting for me now so I currently have a lot of free time.

I was planning to make an introduction to set theory, but that post isn't going that well. I don't know what my next maths post will be about.