Forcing (mathematics) - The Countable Chain Condition

The Countable Chain Condition

An antichain A of P is a subset such that if p and q are in A, then p and q are incompatible (written p ⊥ q), meaning there is no r in P such that r ≤ p and r ≤ q. In the Borel sets example, incompatibility means p∩q has measure zero. In the finite partial functions example, incompatibility means that p∪q is not a function, in other words, p and q assign different values to some domain input.

P satisfies the countable chain condition (c.c.c.) if every antichain in P is countable. (The name, which is obviously inappropriate, is a holdover from older terminology. Some mathematicians write "c.a.c." for "countable antichain condition".)

It is easy to see that Bor(I) satisfies the c.c.c., because the measures add up to at most 1. Fin(E,2) is also c.c.c., but the proof is more difficult.

Given an uncountable subfamily W ⊆ Fin(E,2), shrink W to an uncountable subfamily W₀ of sets of size n, for some n<ω. If p(e₁)=b₁ for uncountably many p ∈ W₀, shrink to this uncountable subfamily W₁, and repeat, getting a finite set { (e₁,b₁), …, (e_k,b_k) }, and an uncountable family W_k of incompatible conditions of size n−k such that every e is in at most countably many dom(p) for p ∈ W_k. Now pick an arbitrary p ∈ W_k, and pick from W_k any q that is not one of the countably many members that have a domain member in common with p. Then p ∪ { (e₁,b₁), …, (e_k,b_k) } and q ∪ { (e₁,b₁), …, (e_k,b_k) } are compatible, so W is not an antichain. In other words, Fin(E,2) antichains are countable.

The importance of antichains in forcing is that for most purposes, dense sets and maximal antichains are equivalent. A maximal antichain A is one that cannot be extended and still be an antichain. This means every element of p ∈ P is compatible with some member of A. Their existence follows from Zorn's lemma. Given a maximal antichain A, let D = { p : p≤q, some q∈A }. D is dense, and G∩D≠0 if and only if G∩A≠0. Conversely, given a dense set D, Zorn's lemma shows there exists a maximal antichain A⊆D, and then G∩D≠0 if and only if G∩A≠0.

Assume P is c.c.c. Given x,y ∈ V, with f:x→y in V, one can approximate f inside V as follows. Let u be a name for f (by the definition of V) and let p be a condition which forces u to be a function from x to y. Define a function F whose domain is x by F(a) = { b : ∃ q ≤ p, q forces u(aˇ) = bˇ }. By definability of forcing, this definition makes sense within V. By coherence of forcing, different b’s come from incompatible p’s. By c.c.c., F(a) is countable.

In summary, f is unknown in V, since it depends on G, but it is not wildly unknown for a c.c.c. forcing. One can identify a countable set of guesses for what the value of f is at any input, independent of G.

This has the following very important consequence. If in V, f:α→β is a surjection from one infinite ordinal to another, then there is a surjection g:ω×α→β in V and consequently a surjection h:α→β in V. In particular, cardinals cannot collapse. The conclusion is that 2ℵ₀ ≥ ℵ₂ in V.