Editing Forcing (mathematics) (section)

== The countable chain condition ==
{{main article|Countable chain condition}}
An [[strong antichain|(strong) antichain]] <math> A </math> of <math> \mathbb{P} </math> is a subset such that if <math> p,q \in A </math> and <math> p \ne q </math>, then <math> p </math> and <math> q </math> are '''incompatible''' (written <math> p \perp q </math>), meaning there is no <math> r </math> in <math> \mathbb{P} </math> such that <math> r \leq p </math> and <math> r \leq q </math>.  In the example on Borel sets, incompatibility means that <math> p \cap q </math> has zero measure. In the example on finite partial functions, incompatibility means that <math> p \cup q </math> is not a function, in other words, <math> p </math> and <math> q </math> assign different values to some domain input.

<math> \mathbb{P} </math> satisfies the [[countable chain condition]] (c.c.c.) if and only if every antichain in <math> \mathbb{P} </math> 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 <math> \operatorname{Bor}(I) </math> satisfies the c.c.c. because the measures add up to at most <math> 1 </math>. Also, <math> \operatorname{Fin}(E,2) </math> satisfies the c.c.c., but the proof is more difficult.

Given an uncountable subfamily <math> W \subseteq \operatorname{Fin}(E,2) </math>, shrink <math> W </math> to an uncountable subfamily <math> W_{0} </math> of sets of size <math> n </math>, for some <math>n < \omega </math>. If <math> p(e_{1}) = b_{1} </math> for uncountably many <math> p \in W_{0} </math>, shrink this to an uncountable subfamily <math> W_{1} </math> and repeat, getting a finite set <math> \{ (e_{1},b_{1}),\ldots,(e_{k},b_{k}) \} </math> and an uncountable family <math> W_{k} </math> of incompatible conditions of size <math> n - k </math> such that every <math> e </math> is in <math> \operatorname{Dom}(p) </math> for at most countable many <math> p \in W_{k} </math>. Now, pick an arbitrary <math> p \in W_{k} </math>, and pick from <math> W_{k} </math> any <math> q </math> that is not one of the countably many members that have a domain member in common with <math> p </math>. Then <math> p \cup \{ (e_{1},b_{1}),\ldots,(e_{k},b_{k}) \} </math> and <math>q \cup \{ (e_{1},b_{1}),\ldots,(e_{k},b_{k}) \} </math> are compatible, so <math> W </math> is not an antichain. In other words, <math> \operatorname{Fin}(E,2) </math>-antichains are countable.{{sfn|Cohen|2008|loc=Section IV.8, Lemma 2}}

The importance of antichains in forcing is that for most purposes, dense sets and maximal antichains are equivalent. A ''maximal'' antichain <math> A </math> is one that cannot be extended to a larger antichain. This means that every element <math> p \in \mathbb{P} </math> is compatible with some member of <math> A </math>. The existence of a maximal antichain follows from [[Zorn's lemma|Zorn's Lemma]]. Given a maximal antichain <math> A </math>, let

:<math> D = \left \{ p \in \mathbb{P} \mid (\exists q \in A)(p \leq q) \right \}.</math>

Then <math> D </math> is dense, and <math> G \cap D \neq \varnothing </math> if and only if <math> G \cap A \neq \varnothing </math>. Conversely, given a dense set <math> D </math>, Zorn's Lemma shows that there exists a maximal antichain <math> A \subseteq D </math>, and then <math> G \cap D \neq \varnothing </math> if and only if <math> G \cap A \neq \varnothing </math>.

Assume that <math> \mathbb{P} </math> satisfies the c.c.c. Given <math> x,y \in V </math>, with <math> f: x \to y </math> a function in <math> V[G] </math>, one can approximate <math> f </math> inside <math> V </math> as follows. Let <math> u </math> be a name for <math> f </math> (by the definition of <math> V[G] </math>) and let <math> p </math> be a condition that forces <math> u </math> to be a function from <math> x </math> to <math> y </math>. Define a function <math> F: x \to \mathcal{P}(y) </math>, by

:<math> F(a) \stackrel{\text{df}}{=} \left \{ b \left | (\exists q \in \mathbb{P}) \left [(q \leq p) \land \left (q \Vdash ~ u \left (\check{a} \right ) = \check{b} \right ) \right ] \right \}. \right.</math>

By the definability of forcing, this definition makes sense within <math> V </math>. By the coherence of forcing, a different <math> b </math> come from an incompatible <math> p </math>. By c.c.c., <math> F(a) </math> is countable.

In summary, <math> f </math> is unknown in <math> V </math> as it depends on <math> G </math>, 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 <math> f </math> is at any input, independent of <math> G </math>.

This has the following very important consequence. If in <math> V[G] </math>, <math> f: \alpha \to \beta </math> is a surjection from one infinite ordinal onto another, then there is a surjection <math> g: \omega \times \alpha \to \beta </math> in <math> V </math>, and consequently, a surjection <math> h: \alpha \to \beta </math> in <math> V </math>. In particular, cardinals cannot collapse. The conclusion is that <math>2^{\aleph_{0}} \geq \aleph_{2} </math> in <math> V[G] </math>.