Now we turn to the proof that GCH holds in L. Reflection principles again come to the rescue. First note that the cardinality of Lα equals the cardinality of α for infinite α. (Just observe that the number of formulas with parameters from Lα is #Lα. So #Lα+1=#Lα. The rest is routine transfinite induction.)
Let’s just look at CH; this gives the flavor. Now, ω∈Lω+1, so the question is, how high up do we have to go in the constructible hierarchy to get all the constructible subsets of ω? Answer: no higher than Lω1, where ω1 is the first uncountable cardinal. Given this, CH holds in L: 𝒫L(ω)⊆Lω1 and #Lω1=#ω1=ℵ1, so #𝒫L(ω)≤ℵ1. The reverse inequality holds because #𝒫L(ω)>ℵ0 and ℵ1 is the next larger cardinal after ℵ0. (Remember that we have AC in L, so all cardinals are comparable. Also, these cardinality computations are done in L. For example, 𝒫L(ω) is uncountable in L; we don’t care about its cardinality according to V.)
Cohen is worth quoting (with a couple of tiny changes):
Let us attempt to give some intuitive justification for why all sets of integers are constructible by countable ordinals. If x⊆ω, x∈Lα, then one can ask what are the essential properties of α which imply that x∈Lα. Now x is determined by the truth values of the countably many statements “n∈x’’. For each n we can think of this as imposing one condition on α. Thus it is not unreasonable that these countably many conditions, if they can be satisfied by any α, can also be satisfied by a countable α. The mechanism for making this precise will be furnished by the Löwenheim-Skolem theorem which allows us to construct smaller sets having the same properties as larger sets.
Here’s the argument. Let x be a constructible subset of ω, belonging to Lβ. Recall from post 23 that the relation y=Lβ is definable (in fact Δ1ZF). In other words, there is a formula Λ(u,y) that says that u is an ordinal and y is the set Lu.
We now apply the reflection principle from post 25:
If K is a countable set containing a transitive subset K0, and Φ is a finite set of closed formulas in ℒK(ZF) (so allowing parameters from K), then there is a countable transitive set N⊇K0 reflecting all the formulas in Φ. In reflecting the formulas of Φ, the parameters from K are replaced with images under an ∈-isomorphism F; this ∈-isomorphism is the identity on K0.
Our set K is ω ∪ {ω,x,β,Lβ}. K0=ω. Our formulas Φ are:
| Λ(β,Lβ) |
| x⊆ω |
| x∈Lβ |
Let’s examine N along with the map F sending K into N. F is the identity on ω. So it’s also the identiy on x: F(x)⊆ω because “x⊆ω’’ is reflected, and n∈x ⇔ F(n)∈F(x) ⇔ n∈F(x). We also have
| N⊧x∈F(Lβ) | (reflection) |
| L⊧x∈F(Lβ) | (absoluteness) |
| N⊧Λ(F(β),F(Lβ)) | (reflection) |
| L⊧Λ(F(β),F(Lβ)) | (absoluteness) |
In other words, N reflects x∈Lβ, so x is in F(Lβ) according to N. But by absoluteness of ∈, x really is in F(Lβ). Likewise, β constructs Lβ, so by reflection F(β) constructs F(Lβ) in N. But by absoluteness of Λ(u,y), F(β) really does construct F(Lβ). (When I say “really” I mean according to L, although it’s also true according to V.)
So x∈F(Lβ)=LF(β). Since F(β) is an ordinal contained in the countable transitive set N, it’s countable. We’ve now shown that x is constructed by the countable ordinal F(β), as claimed.
Again I quote Cohen (editing to match our notation):
One should compare the above proof with the intuitive motivation. The “collapsing” of the set K by the isomorphism F means that we have extracted from the ordinal β all the lower ordinals which played a role in the formation of x in Lβ, and then discarded the other lower ordinals. The result is a much smaller ordinal F(β) which also constructs x.
For the full GCH, we need an extension of the reflection principle. Instead of a countable K, we have to allow K to have arbitrary cardinality, with the reflecting M⊇K having the same cardinality. The proof of this is not difficult, and the proof that V=L implies GCH is pretty much the same.
Next up: Forcing!
Diagonal Argument 