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.

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

What made this problem interesting to me was that I had to

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

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

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} \)

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

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.

**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.

## No comments:

## Post a Comment