Forcing and the Independence of CH (Part 2)

Part 1 here

Part 2: How big is 𝒫(ω)?

Now the pieces are all in place to start applying forcing to prove some big results. Everything that follows assumes the existence of a countable transitive model M of ZFC.

First, a few notes on terminology.

The language of ZFC is very minimalistic. All it has on top of the first-order-logic connectives is a single binary relation symbol ∈. Nonetheless, people will usually talk about theorems of ZFC as if it has a much more elaborate syntax, involving symbols like ∅ and ω and ℵ₁ and terms like “bijection” and “ordinal”. For instance, the Continuum Hypothesis can be written as “There’s a bijection between 𝒫(ω) and ℵ₁“, which is obviously using much more than just ∈. But these terms are all simply shorthand for complicated phrases in the primitive language of ZFC: for instance a sentence “φ(∅)” involving ∅ could be translated as “∃x (∀y ¬(y ∈ x) ∧ φ(x))”, or in other words “there’s some set x that is empty and φ(x) is true”.

Something interesting goes on when considering symbols like ∅ and ω and ℵ₁ that act like proper names. Each name picks out a unique set, but for some of these names, the set that gets picked out differs in different models of ZFC. For example, the interpretation of the name “ℵ₁” is model-relative; it’s meant to be the first uncountable cardinal, but there are countable models of ZFC in which it’s actually only countably large! If this makes your head spin, it did the same for Skolem: you can find more reading here.

On the other hand, the name “∅” always picks out the same set. In every model of ZFC, ∅ is the unique set that contains nothing at all. When a name’s interpretation isn’t model-relative, it’s called absolute. Examples include “∅” and “1,729”. When a name isn’t absolute, then we need to take care to distinguish between the name itself as a syntactic object, and the set which it refers to in a particular model of ZFC. So we’ll write “ℵ₁” when referring to the syntactic description of the first uncountable cardinal, and ℵ₁^M when referring to the actual set that is picked out by this description in the model M.

With that said, let’s talk about a few names that we’ll be using throughout this post:

In M, ω is the conventional name for the set that matches the description “the intersection of all inductive sets”, where inductive sets are those that contain the ordinal 0 and are closed under successor. In any transitive model of ZFC like M, ω is exactly ℕ, the set of natural numbers. Since we’re restricting ourselves to only considering transitive models, we can treat ω as if it’s unambiguous; its interpretation won’t actually vary across the models we’re interested in.

ω₁ corresponds to the description “the smallest uncountable ordinal”. This description happens to perfectly coincide with the description “the first uncountable cardinal” in ZFC, which has the name ℵ₁. But unlike with ω, different transitive models pick out different sets for ω₁ and ℵ₁. So in a model M, we’ll write ω₁^M for the set that M believes to be the smallest uncountable ordinal and ℵ₁^M for the first uncountable cardinal.

ω₂ is the name for the first ordinal for which there’s no injection into ω₁ (i.e. the first ordinal that’s larger than ω₁). Again, this is not absolute: ω₂^M depends on M (although again, ω₂^M is the same as ℵ₂^M no matter what M is). And in a countable model like those we’ll be working with, ω₂^M is countable. This will turn out to be very important!

𝒫(ω) is the name for the the set that matches the description “the set of all subsets of ω”. Perhaps predictably at this point, this is not absolute either. So we’ll have to write 𝒫(ω)^M when referring to M’s version of 𝒫(ω).

Finally, ZFC can prove that there’s a bijection from 𝒫(ω) to ℝ, meaning that this bijection exists in every model. Thus anything we prove about the size of 𝒫(ω) can be carried over to a statement about the size of ℝ. Model-theoretically, we can say that in every model M, |𝒫(ω)^M| = |ℝ^M|. It will turn out to be more natural to prove things about 𝒫(ω) than ℝ.

Okay, we’re ready to make the continuum hypothesis false! We’ll do this by choosing a partially ordered set (P, ≤) whose extension as a Boolean algebra (B, ≤) has the property that no matter what M-generic filter G in B you choose, M[G] will interpret its existence as proof that |𝒫(ω)| ≥ ℵ₂.

Making |𝒫(ω)| ≥ ℵ₂

Let P = { f ∈ M | f is a finite partial function from ω₂^M × ω to {0,1} }. Let’s have some examples of elements of P. The simplest is the empty function ∅. More complicated is the function {((ω+1, 13), 1)}. This function’s domain has just one element, the ordered pair (ω+1, 13), and this element is mapped to 1. The function {((14, 2), 0), ((ω₁^M•2, 2), 1)} is defined on two elements: (14, 2) and (ω₁^M•2, 2). And so on.

We’ll order P by reverse inclusion: f ≤ g iff f ⊇ g. Intuitively, f ≤ g if f is a function extension of g: f is defined everywhere that g is and they agree in those places. For instance, say f = {((ω, 12), 0)}, g = {((ω, 12), 0), ((13, 5), 1)}, h = {((ω, 12), 1)}, and p = {((ω, 11), 1)}. Check your understanding by verifying that (1) g ≤ f, (2) f and h are incomparable and have no common lower bound, and (3) f and p are incomparable but do have a common lower bound (what is it?).

The empty function ∅ is a subset of every function in P, meaning that ∅ is bigger than all functions. Thus ∅ is the top element of this partial order. And every f in P is finite, allowing a nice visualization what the partial order (P, ≤) looks like:

Now, G will be an M-generic ultrafilter in the Boolean extension (B, ≤) of (P, ≤). G is the set that we’re ultimately adding onto M, so we want to know some of its properties. In particular, how will we use G to show that |𝒫(ω)| = ℵ₂?

What we’re going to do is construct a new set out of G as follows: first take the intersection of P with G. (remember that G is an ultrafilter in B, so it doesn’t only contain elements of P). P⋂G will be some set of finite partial functions from ω₂^M × ω to {0,1}. We’ll take the union of all these functions, and call the resulting set F. What we’ll prove of F is the following:

(1) F := ⋃(P⋂G) is a total function from ω₂^M × ω to {0,1}
(2) For every α, β ∈ ω₂^M, F(α, •) is a distinct function from F(β, •).

A word on the second clause: F takes as input two things: an element of ω₂^M and an element of ω. If we only give F its first input, then it becomes a function from ω to {0,1}. For α ∈ ω₂^M, we’ll give the name F_α to the function we get by feeding α to F. Our second clause says that all of these functions are pairwise distinct.

Now, the crucial insight is that each F_α corresponds to some subset of ω, namely {n ∈ ω | F_α(n) = 1}. So F defines |ω₂^M|-many distinct subsets of ω. So in M[G], it comes out as true that |𝒫(ω)^M| ≥ |ω₂^M|. It’s also true in M[G] that |ω₂^M| = ℵ₂^M, and so we get that |𝒫(ω)^M| ≠ ℵ₁^M. This is ¬CH!

Well… almost. There’s one final subtlety: |𝒫(ω)^M| ≠ ℵ₁^M is what ¬CH looks like in the model M. For ¬CH to be true in M[G], it must be that that |𝒫(ω)^M[G]| ≠ ℵ₁^M[G]. So what if |𝒫(ω)^M| ≠ |𝒫(ω)^M[G]|, or ℵ₁^M ≠ ℵ₁^M[G]? This would throw a wrench into our proof: it would mean that M[G] believes that M’s version of 𝒫(ω) is bigger than M’s version of ℵ₁, but M[G] might not believe that its own version of 𝒫(ω) is bigger than its version of ℵ₁. This is the subject of cardinal collapse, which I will not be going into. However, M[G] does in fact believe that 𝒫(ω)^M = 𝒫(ω)^M[G] and that ℵ₁^M = ℵ₁^M[G].

Alright, so now all we need to do to show that M[G] believes ¬CH is to prove (1) that F is a total function from ω₂^M × ω to {0,1}, and (2) that for every α, β ∈ ω₂^M, F_α is distinct from F_β. We do this in three steps:

1. F is a function.
2. F is total.
3. For every α, β ∈ ω₂^M, F_α is distinct from F_β.

Alright so how do we know that F is a function? Remember that F = ⋃(P⋂G). What if some of the partial functions in P⋂G are incompatible with each other? In this case, their union cannot be a function. So to prove step 1 we need to prove that all the functions in P⋂G are compatible. This follows easily from two facts: that G is an ultrafilter in B and P is dense in B. The argument: G is an ultrafilter, so for any f, g ∈ P there’s some element f∧g ∈ B that’s below both f and g. All we know about f∧g is that it’s an element of B, but we have no guarantee that it’s also a member of P, our set of partial functions. In other words, we can’t say for sure that f∧g is actually a partial function from ω₂^M × ω to {0,1}. But now we use the fact that P is dense in B! By the definition of density, since f∧g is an element of B, P must contain some h ≤ f∧g. Now by transitivity, h ≤ f and h ≤ g. So f and g have a common function extension, meaning they must be compatible functions! Pretty magical right?

So F is a function. But how do we know that it’s total? We prove this by looking closely at the dense subsets of P. In particular, for any α ∈ ω₂^M and any n ∈ ω, define D_α,n := {f ∈ P | (α, n) ∈ dom(f)}. This is a dense subset of P. Why? Well, regardless of what α and n are, any function f in P is either already defined on (α, n), in which case we’re done, or it’s not, in which case f has a function extension with (α, n) in its domain. So from any element of P, you can follow the order downwards until you find a function with (α, n) in its domain. Since D_α,n is dense in P and G is M-generic, G must have some element in common with D_α,n. Thus G contains an element f of P that has (α, n) in its domain. This f is one of the functions that we union over to get F, so F must have (α, n) in its domain as well! And since α and n were totally arbitrary, F must be total.

Finally, why are the “F_α”s pairwise distinct? Again we construct dense subsets for our purposes: for any α, β ∈ ω₂^M, define D_α,β := {f ∈ P | f_α ≠ f_β}. This is clearly dense (you can always extend any f in P to make f_α and f_β disagree somewhere). So G contains an element f of P for which f_α ≠ f_β. And thus it must also be true of F that F_α ≠ F_β!

And we’re done! We’ve shown that once we add G to M, we can construct a new set F = ⋃(P⋂G) such that F encodes |ω₂^M|-many distinct subsets of ω, and thus that M[G] ⊨ |𝒫(ω)| ≥ ℵ₂.

Making |𝒫(ω)| ≥ ℵ₄₂₀

What’s great is that this argument barely relied on the “2” in ω₂^M. We could just as easily have started with P = {f ∈ M | f is a finite partial function from ω₄₂₀^M × ω to {0,1}}, constructed an M-generic filter G in the Boolean extension of P, then defined F to be ⋃(P⋂G).

G is still an ultrafilter in B and P is still dense in B, so F is still a function.

D_α,n := {f ∈ P | (α, n) ∈ dom(f)} is still a dense subset of P for any α ∈ ω₄₂₀^M and any n ∈ ω, so F is still total.

And D_α,β := {f ∈ P | f_α ≠ f_β} is still a dense subset of P for any α, β ∈ ω₄₂₀^M, so all the “F_α”s are pairwise distinct.

And now F encodes |ω₄₂₀^M|-many distinct subsets of ω! The final step, which I’m going to skip over again, is showing that M[G] believes that |ω₄₂₀^M| = |ω₄₂₀^M[G]|, i.e. that cardinal collapse doesn’t occur.

And there we have it: this choice of P gives us a new model M[G] of ZFC that believes that |𝒫(ω)| ≥ ℵ₄₂₀! Note how easy and quick this argument is now that we’ve gone through the argument for how to make M[G] believe |𝒫(ω)| ≥ ℵ₂. This is a great thing about forcing: once you really understand one application, other applications become immensely simpler and easier to understand.

Making |𝒫(ω)| = ℵ₁

Okay, we’ve made CH false. Now let’s make it true! This time our choice for (P, ≤) will be the following:

P = {f ∈ M | f is an M-countable partial function from ω₁^M to 𝒫(ω)^M}. Once more we order by reverse inclusion: f ≤ g iff f ⊇ g.

A crucial thing to notice is that I’ve merely required the functions in P to be M-countable, rather than countable. For a set to be M-countable is for there to exist an injection in M from set to ω. Any M-countable set is countable, but some countable sets may not be M-countable (like M itself!). In particular, we know that ω₁^M is actually a countable set, meaning that if we required true countability instead of just M-countability, then P would include some total functions! But M has no injection from ω₁^M to ω, so no function in P can be total. This will be important in a moment!

We get our M-generic ultrafilter G and define F := ⋂(P⋂G). Now we want to show that F is a total and surjective function from ω₁^M to 𝒫(ω). As before, we proceed in three steps:

1. F is a function
2. F is total
3. F is surjective

Step 1: G is an ultrafilter and P is dense in G, so the same argument works to show that all elements of P⋂G are compatible: (1) ultrafilter implies that any f, g in P⋂G have a least upper bound f∧g in B, (2) density of P in G implies that f∧g has a lower bound h in P, so (3) f and g have a common function extension . Thus F is a function.

Step 2: D_α := {f ∈ P | α ∈ dom(f)} is dense in P for any α ∈ ω₁^M, so F is total.

Step 3: D_A := {f ∈ P | A ∈ image(f)} is dense in P for any A ∈ 𝒫(ω)^M. Why? No f in P is total, so any f in P can be extended by adding one more point (α, A) where α ∉ dom(f). Thus A ∈ image(F) for any A ∈ 𝒫(ω), so F is surjective.

So F is a total surjective function from ω₁^M to 𝒫(ω)^M, meaning that in M[G] it’s true that |𝒫(ω)^M| ≤ ℵ₁^M. And since ZFC proves that |𝒫(ω)| > ℵ₀, it follows that M[G] ⊨ |𝒫(ω)| = ℵ₁.

You might have noticed that each of these arguments could just as easily have been made if we had started out with defining P as the finite partial functions in M from ω₁^M to 𝒫(ω)^M. This is true! If we had done this, then we still would have ended up proving that F was a total surjective function from ω₁^M to 𝒫(ω)^M, and therefore that |𝒫(ω)^M| = ℵ₁^M. However, this is where cardinal collapse rears its ugly head: the final step is to prove that |𝒫(ω)^M| = |𝒫(ω)^M[G]| and that ℵ₁^M = ℵ₁^M[G]. This requires that P be the countable partial functions rather than just the finite ones.

And with that final caveat, we see that M[G] believes that |𝒫(ω)| = ℵ₁.

Making |𝒫(ω)| ≤ ℵ₃₁₄

Let P = {f ∈ M | f is an M-countable partial function from ω₃₁₄^M to 𝒫(ω)} and order by reverse inclusion: f ≤ g iff f ⊇ g.

⋂(P⋂G) is again a total and surjective function from ω₃₁₄^M to 𝒫(ω), following the exact same arguments as in the previous section. Cardinal collapse doesn’t occur here either, so M[G] believes that |𝒫(ω)| ≤ ℵ₃₁₄.

✯✯✯

We’ve proven the independence of the Continuum Hypothesis from ZFC! We’ve done more: we’ve also shown how to construct models of ZFC in which we have lots of control over the size of 𝒫(ω). Want a model of ZFC in which |𝒫(ω)| is exactly ℵ₁₇₂₉? Just force with the right P and you’re good to go! There’s something a bit unsatisfactory about all this though, which is that in each application of forcing we’ve had to skim over some details about cardinal collapse that were absolutely essential to the proof going through. I hope to go into these details in a future post to close these last remaining gaps.