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