Category Archives: Math

Prev TOC Next

Cohen introduced forcing in 1963 to prove the independence of the continuum hypothesis from ZFC. The next few years witnessed simplifications, other applications, and other perspectives. Despite the simplifications, forcing in set theory comes encrusted with technicalities.

In set theory, the basic forcing concepts occur entangled with the cumulative hierarchy, the level-by-level build-up of the universe of sets from the empty set. This makes for a messy situation. The most “barnacle-free” setting for forcing is Peano arithmetic. Only three levels demand attention:

1. Numbers.
2. Sets of numbers.
3. Classes of sets of numbers. (I use the word ‘class’ just for smoothness; these are bona fide sets in ZF, not proper classes.)

Both in ZF and in the cases treated here, forcing deals with definability. Gödel had shown that if all sets are constructible (V=L), then AC and GCH hold. So Cohen started off by trying to show the relative consistency of V≠L. As we’ve seen, constructibility is all about definability.

We’ll look at four kinds of definability for Peano arithmetic (or really three):

• Arithmetic sets of numbers. A set is arithmetic if it can be defined by a formula of ℒ(PA).
• Implicitly definable sets of numbers. A set is implicitly definable if it can be defined by a formula in the language of PA augmented by a predicate symbol (say S) standing for the set. I’ll write ℒ(PA+S) for the augmented language.
• Arithmetic classes of sets of numbers. A class is arithmetic if it can be defined by a formula of ℒ(PA+S). Implicit definability is the special case where a singleton {A} is an arithmetic class.
• Hyperarithmetic sets of numbers (aka Δ¹₁ subsets). A set is hyperarithmetic if it can be defined by a certain kind of formula in the second-order language of PA, denoted by ℒ²(PA).

Using forcing, Feferman showed the existence of a hyperarithmetic set that is not implicitly definable, and Addison showed that the class of arithmetic sets is not an arithmetic class.

Our roadmap:

1. We define the four kinds of definability.
2. In the context of PA, we offer intuition for the notions generic set and forcing.
3. We proceed with the formal development, and prove the Feferman and Addison theorems.
4. We generalize the notions of forcing and generic sets.
5. We turn to ZF set theory.

Prev TOC Next

Prev TOC Next

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 ω₁ is the first uncountable cardinal. Given this, CH holds in L: 𝒫^L(ω)⊆L_ω1 and #L_ω1=#ω₁=ℵ₁, so #𝒫^L(ω)≤ℵ₁. The reverse inequality holds because #𝒫^L(ω)>ℵ₀ and ℵ₁ is the next larger cardinal after ℵ₀. (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 Δ₁^ZF). In other words, there is a formula Λ(u,y) that says that u is an ordinal and y is the set L_u.

We now apply the reflection principle from post 25:

If K is a countable set containing a transitive subset K₀, and Φ is a finite set of closed formulas in ℒ_K(ZF) (so allowing parameters from K), then there is a countable transitive set N⊇K₀ 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 K₀.

Our set K is ω ∪ {ω,x,β,L_β}. K₀=ω. Our formulas Φ are:

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

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_β)=L_F(β). 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!

Prev TOC Next

Prev TOC Next

Let’s put it all together. Recall that Gödel proved three main results about L: Continue reading →

Prev TOC Next

The Collapse of the Tacoma Bridge

Continue reading →

Prev TOC Next

Mount Hood Reflected in Mirror Lake (Public Domain)

Continue reading →

Prev TOC Next

Now we turn to the absolutness of the notion of constructibility. There is a formula Λ(x) which says that x is constructible, and which holds in L iff it holds in V. Λ(x) is not Δ₀, nor is it absolute over all transitive classes, so some subtleties come into play. (It is absolute between models of ZF.) Continue reading →

Prev TOC Next

Let’s look again at the notion of definability, rewritten slightly: for any set A, x⊆A is definable over A if there is a first-order formula φ(y,ū) and elements ā∈A such that Continue reading →

Prev TOC Next

The constructible universe is traditionally denoted L. L is a subclass of V and is a proper class. Gödel proved three things about L: Continue reading →

Prev TOC Next

Sierpiński’s Theorem: GCH implies AC Continue reading →

Prev TOC Next

Just denying the axiom of choice doesn’t buy you much. If you’re going to throw away AC, you should add some powerful incompatible axiom in its place. The Axiom of Determinacy (AD) has been studied in this light. Continue reading →