Category Archives: Set Theory

Prev TOC Next

We start by giving a rough idea of Cohen’s notion of a generic set (in the PA setting); Feferman’s and Addison’s sets are generic. A generic set is patternless or random¹; it has no special properties. For example, the set of primes is not generic, nor is any set containing the set of primes—that’s a discernable pattern, even though it doesn’t determine the whole set. Likewise, if a set contains no primes then it’s not generic. The “least specific” thing we can say about G⊆ℕ, vis-a-vis primes, is that it contains an infinite number and omits an infinite number. So this should be true for any “generic” set. Perhaps you can already see how a generic set will be “slippery”, eluding various kinds of definability.

A generic G⊆ℕ can’t literally have no properties. For example, either 0∈G or 0∉G, and likewise for any other number n. A condition is a consistent conjunction of a finite number of statements, each either n∈G or n∉G for some n∈ℕ. (For example, 0∈G ∧ 17∈G ∧ 221∉G. This is the “formula” definition of condition. “Consistent” just means we don’t have both n∈G and n∉G in the same condition.) Suppose G satisfies a condition p. Cohen’s methods enable us to say exactly which statements about G should hold, given that G is “generic” and satisfies p. Cohen used the (initially vague) notion of “generic” to inspire the notion of “forcing”: if p forces φ, then φ holds for all generic G satisfying p.

The motivation runs from genericity to forcing, but the formal treatment takes the reverse route: first an inductive definition of forcing, then a definition of generic set in terms of forcing, and finally some lemmas justifying the initial intuition.

Now let’s nail down a few details. First, a matter of terminology. Shortly after Cohen’s forcing appeared, Feferman introduced a variation he called weak forcing. The one-way implication mentioned above becomes an equivalence for weak forcing: p weakly forces φ if and only if φ holds for all generic G satisfying p. For this reason, most authors nowadays just say “forcing” for “weak forcing”. Cohen’s version is, naturally, called “strong forcing”. The notation ⊩^* is used for strong forcing, ⊩ for weak forcing. I will follow this convention. We’ll define (weak) forcing in a later post. (The strong/weak distinction is independent of the ZF/PA difference.) As it happens, the most natural treatment first defines strong forcing, proves theorems about it, and then defines weak forcing as a derived concept.

We let ℒ(PA+G) be the language of PA augmented with one new unary predicate G. We write (ℕ,A) for the structure consisting of the standard model (ℕ,0,1,+,·,<) of PA, plus A⊆ℕ interpreting G. We let p,q,r stand for conditions. For our present purposes, conditions as finite bitstrings works better than the “formula” notion. Some notations: p≤q and q≥p mean that q extends (or equals) p. A⊧p means that p is an initial segment of A (regarding A as an infinite bitstring). We let ∅ stand for the empty condition (i.e., the null string).

One difference between the bitstring and formula notions: if A⊧p₁,p₂, then with the bitstring notion, either p₁≤p₂ or p₂≤p₁. With the formula notion, we are assured only that p₁ and p₂ have a common extension q satisfied by A. We will avoid using this special fact about the bitstring notion, to keep certain arguments more general.

We’ll write p⊩^*φ to mean that p strongly forces φ; here φ is a closed formula in ℒ(PA+G). The definition of p⊩^*φ is inductive, as I mentioned. A key aspect of the definition: ∃ is regarded as basic, with ∀ just an abbreviation. Likewise, ∨ is basic with ∧ an abbreviation.

1. p⊩^* s=t ↔ ℕ⊧s=t, where s and t are closed terms in ℒ(PA).
2. p⊩^* G(n) ↔ p(n)=1.
3. p⊩^* α∨β ↔ p⊩^*α or p⊩^*β.
4. p⊩^* ¬φ ↔ there is no q≥p with q⊩^*φ.
5. p⊩^* ∃xφ(x) ↔ for some n∈ℕ, p⊩^*φ(n).

In (2) and (5), we are being a bit sloppy about the distinction between n∈ℕ and the numeral representing it in ℒ(PA).

Let’s talk about clause (4), the definition of p⊩^*¬φ. Cohen originally put everything into prenex normal form. Dana Scott later suggested clause (4), simplifying the development. What is the intuitive justification for (4)? We want to have p⊩^*φ precisely when (ℕ,A)⊧φ for all “generic” A⊧p. Obviously we don’t want to have p⊩^*¬φ and q⊩^*φ for some q≥p. On the other hand, if no extension q≥p strongly forces φ, this indicates we will always find generic sets satisfying an extension q and also satisfying ¬φ, no matter how q extends p.

Imagine going through the elements of ℕ in increasing order, choosing which to put into A. Suppose at some point that A⊧p. After that, we will never be able to assure the truth of φ; only when we’ve gone through “all of ℕ’’ will we find out if φ is true. That suggests that φ is somehow “specific”, that we have to choose “carefully” infinitely often if we want φ to end up true. For example, suppose φ says “G contains only finitely many primes”. This is more specific than its negation, since if n₀ is the largest prime in A, then we have to vigilantly exclude every single prime greater than n₀. So all generic A’s will contain infinitely many primes (and likewise omit infinitely many).

To put it another way: if A⊧p and p extends as far as the last prime in A, then this fact about p tells us an infinite number of facts about A. Namely, exactly which primes belong to it. But if A contains an infinite number of primes, then for any finite initial segment of A, we can say nothing about the primes past it. That seems more “generic” than the alternative.

Clause (4) captures this intuition. Suppose A contains infinitely many primes. If we claim of a condition that “It’s got all the primes of A!”, then our claim will be falsified by some extension. ∅⊩^*¬φ says that there is no condition q with q⊩^*φ. Because of clause (5), it’s a short step from q⊩^* “A has only finitely many primes” to q⊩^* “I’ve got all the primes of A!”. But we’ve just seen that that can’t happen.

The last few paragraphs make the heuristic case for clause (4). Ultimately these clauses justify themselves by the formal development based on them.

The following trivial consequence of clause (4) is important: we cannot have both p⊩^*φ and p⊩^*¬φ.

Now we are ready to define “generic” formally.

A⊆ℕ is generic iff for every closed formula φ in ℒ(PA+G), there is a condition p with A⊧p and either p⊩^*φ or p⊩^*¬φ.

Intuitive justification: either (ℕ,A)⊧φ or (ℕ,A)⊧¬φ. Either way, the truth of φ or its negation should depend on only a finite amount of information about A, namely a condition p (plus the fact that A is “generic”). So we should have either p⊩^*φ or p⊩^*¬φ.

This suggests a slight extension of the ⊩^* notation. Write A⊩^*φ to mean that there exists a p with A⊧p and p⊩^*φ. With this notation, we have

A⊆ℕ is generic iff for every closed formula φ in ℒ(PA+G), either A⊩^*φ or A⊩^*¬φ.

[1] But we will avoid the word “random” from now on, since there is a different notion of algorithmically random.

Prev TOC Next

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 →