## Monday, September 8, 2014

### More on the countable chain condition

We last met the ccc in the context of preserving cofinalities in forcing extensions; but the exercise that I gave the proof for was specifically about forcing. This week, I ran across a nice little exercise which doesn't explicitly mention forcing at all -- it's pure combinatorics -- but, at least for me, thinking about it using the forcing idea was the key to solving the problem.

Exercise 1: Let $$\mathbb{P}$$ be a ccc poset, and let $$X = \{ x_i \colon i < \omega_1 \} \subseteq \mathbb{P}$$ be a subset. Show that there exists an uncountable subset of $$X$$ whose every pair are compatible.

At first glance, this looks completely obvious -- things are either compatible or incompatible, and you can't have more than countably many pairwise incompatible things. The problem, though, is that the compatibility relation need not be transitive -- just because you have an uncountable subset of $$X$$ which is not an antichain does not mean that it satisfies the conclusion of the exercise.

What made this problem interesting to me was that I had to discard some of the heuristics that usually serve me well. In particular, a dependable heuristic when dealing with posets is duality: if something is true for all posets, then you should be able to turn your poset upside-down and it should still be true. However, the compatibility relation is not stable under duality! Most forcing posets have a single weakest condition; if you dualize, you get that every two conditions are compatible, which is clearly useless.

First failed attempt: We define an $$\omega_1$$-coloring of $$X$$ by recursion. Let $$f(x_0) = 0$$. Now, if $$f(x_\alpha)$$ is defined for all $$\alpha < \beta$$, we let $$f(x_\beta)$$ equal the least $$\delta$$ such that $$x_\beta$$ is compatible with all elements of $$f^{-1}(\delta)$$, if any such $$\delta$$ exists. If not, $f(x_\beta) = \sup_{\alpha < \beta} f(x_\alpha) + 1$i.e. $$f(x_\beta)$$ is the first available new color.

Check your understanding: Show that $$f(x_\alpha) \leq \alpha$$ for all $$\alpha$$.

If we could strengthen this to show that $$f(x_\alpha)$$ is strictly less than $$\alpha$$ for all $$\alpha > 0$$, or show that the set of those $$\alpha$$ such that $$f(x_\alpha) = \alpha$$ is bounded, then we would be done: we could use Fodor's Lemma, because the coloring $$f$$ would be a regressive function on a "large" set.

But I don't see an obvious way to do this, and this conclusion appears to be stronger than the problem we're trying to prove. (It still might be true, but I don't have a good intuition one way or another.)

What's the roadblock? Well, even though $$\mathbb{P}$$ has the countable chain condition, there's no obvious reason that we couldn't have a situation like the following: as we're considering colors $$\alpha < \beta$$, $$x_\beta$$ is compatible with most of the conditions in the $$\alpha^{\text{th}}$$ bin, but is incompatible with a few. Now, we're not adding to any large antichains here -- $$x_\beta$$ is compatible with some of the conditions in the $$\alpha$$ bin -- so using the ccc directly here to say this can't go on forever is going to be hard.

Solution: For the purposes of this solution, $$a \uparrow$$ (resp. $$a \downarrow$$) will denote the set of elements of $$X$$ above (below) $$a$$.

First: every set $$a \uparrow$$ consists of pairwise-compatible elements; if any such set is uncountable, we're done. So we assume that all such sets are countable (that is, either finite or countably infinite).

Next: let $$A_0 \subset X$$ be a set of pairwise-incompatible conditions which is maximal under inclusion. (See: I'm even calling the elements of $$\mathbb{P}$$ conditions, even though the problem ostensibly has nothing to do with forcing!) Then because of the ccc, $$A_0$$ is countable.

Now, every element of $$X$$ is either weaker than some element of $$A_0$$, in $$A_0$$, or stronger than some element of $$A_0$$. By our assumption, the set of all conditions weaker than $$A_0$$ is also countable. Conditions weaker than $$A_0$$ may be weaker than many elements of $$A_0$$; however, conditions stronger than $$A_0$$ are stronger than exactly one member of $$A_0$$, and there are uncountably many such conditions.

Hence we can choose an $$a_0 \in A_0$$ which has uncountably many extensions in $$X$$. Now define $$A_1$$ by throwing $$a_0$$ out of $$A_0$$ and adding in a maximal collection of pairwise incompatible elements of $$X$$ below $$a_0$$. Choose $$a_1 < a_0$$ with uncountably many extensions in $$X$$.

Proceeding in this way, we get a sequence of antichains $$A_k$$ and a descending chain of conditions $$a_{k+1} < a_k$$ for all $$k < \omega$$, each with uncountably many extensions. By assumption, $$\bigcup_{k < \omega \: x \in A_k} x \uparrow$$ is countable, so there exists some $$a_\omega \in X$$, $$a_\omega < a_k$$ for all $$k$$.

So we let $$A_\omega$$ contain $$a_\omega$$ and not contain any $$x \in X$$ above $$a_\omega$$. Continuing inductively in this way, we can now define a descending chain $$a_\alpha$$ for $$\alpha < \omega_1$$. This chain satisfies the exercise.