MA and its effect on Tree Partitions

(This is the presentation I gave for Stevo Todorcevic’s course Combinatorial Set Theory on Feb 28, 2012. The material comes from Stevo’s 1983 paper “Partition Relations for Partially Ordered Sets”.)

In partition relations for ordinals, it has been established that:

Theorem (Erdos-Rado). \omega_1 \rightarrow (\omega_1, \omega+1)^2

Later it was shown that this is the best you can do, as the strengthenings are consistent:

Theorem(Hajnal). Under CH, \omega_1 \not\rightarrow (\omega_1, \omega+2)^2
Theorem (Todorcevic). Under PFA, for any countable ordinal \alpha , \omega_1 \rightarrow (\omega_1, \alpha)^2

Moving on, we can ask the same questions about non-special trees, which in some way are the tree analogue of “uncountable” or “large”.

Theorem (Todorcevic). Nonspecial Tree \rightarrow (Nonspecial Tree, \omega+1)^2

This is the analogue or the Erdos-Rado theorem.

Recall that a tree T is nonspecial if T \rightarrow (\omega)^1_\omega , which means that any countable partition T contains an infinite set. (This is a generalization of uncountable, because for countable sets you can always put one element per colour.)

We will show the following:

Theorem (Todorcevic). Under MA, for T a tree with no uncountable chains and \vert T \vert = 2^{\aleph_0} we have T \not\rightarrow (T, \omega+2)^2 .

(Of course here, T \not\rightarrow (T, \omega+2)^2 should really be T\not \rightarrow ( Nonspecial, \omega)^2 . Throughout this talk I will assume that you understand that I am not demanding a copy of T in the first colour.)

Through the proof we will actually get the superficially stronger result:

Theorem. Assume MA. Let T be a tree with no uncountable chains and \vert T \vert = 2^{\aleph_0} . There is a partition [T]^2 = K_0 \cup K_1 such that

  1. There is no nonspecial subtree X\subseteq T such that [X]^2 \subseteq K_0 ;
  2. There is no set A \cup \{b,c\} \subseteq T such that A < b<c , otp A=\omega and A \times \{b,c\} \subseteq K_1 .

We will need the following standard results about MA and trees:

Lemma 1. Assume MA. Every Aronszajn tree T of cardinality \kappa<2^{\aleph_0} is special. (Thus nonspecial Aronszajn trees have cardinality \geq 2^{\aleph_0} )
Lemma 2. Every nonspecial tree T of cardinality 2^{\aleph_0} can be pruned to a nonspecial tree X such that for all a \in X , X^a= \{t\in X : a \leq t\} is nonspecial.

To clarify, here an Aronszajn tree is a tree with uncountably many nodes, countable levels and no uncountable chains.

Recall. For X a tree, \hat{a}=\{t \in X : t \leq a\} , the set of predecessors in X .

Lemma 3. Assume MA. Let T be an nonspecial aronszajn tree (of cardinality \kappa =2^{\aleph_0} ) with underlying set \kappa that agrees with the tree ordering. (i.e. \alpha <_T \beta implies \alpha < \beta ). Fix [\kappa]^\omega = \{A_\xi : \xi < \kappa\} .
THEN there is a family \{S_\alpha \subseteq \hat{\alpha}: \alpha < \kappa\} such that

  1. S_\alpha \cap S_\beta is finite for \alpha \neq \beta ;
  2. If \xi < \alpha , (and if A_\xi \cap \hat{\alpha} is not covered by finitely many S_\beta with \beta<\alpha ) then S_\alpha \cap A_\xi \neq \emptyset .

Proofs.

[1]. This is a classical result of Baumgartner from 1970. The poset is what you might expect – finite approximation of a partition- but it is difficult to show this is ccc.

[2]. If there are a small (read: special-many) amount of nodes with special upwards cones, then we can simply remove them (as collection of special many special trees is special. Remember, special means small). The case where there are “nonspecial” many nodes with special upwards cones requires special attention which I will not go into here.

Helpful Diagram, no?

[3] This is proved by induction on \alpha<\kappa , and uses a very similar poset to the one to generate a MAD family with the property that all the elements of the mad family have large intersection with a prescribed family.

Now, on to the theorem!

proof. Let T be an nonspecial aronszajn tree (of cardinality \kappa =2^{\aleph_0} ) with underlying set \kappa that agrees with the tree ordering. Assume by Lemma 2, that we have pruned T properly. Fix [\kappa]^\omega = \{A_\xi : \xi < \kappa\} . Let \{S_\alpha : \alpha < \kappa\} be a family as described in Lemma 3.

Define [T]^2 = K_0 \cup K_1 by \{\beta, \alpha\} \in K_1 iff \beta \in S_\alpha .

Claim 1. There are no 1-homogeneous subsets of order-type \omega+2 .

Let B = \{x_n : n<\omega\}\cup\{x_\omega, x_{\omega+1}\} , with [B]^2 \subseteq K_1 . Then \vert S_{x_{\omega}}\cap S_{x_{\omega+1}} \vert = \vert \{x_n : n<\omega\} \vert = \aleph_0 , which violates the first condition of Lemma 3.

Claim 2. There is no 0-homogeneous nonspecial tree X \subseteq T .

Suppose not. By Lemma 1 and 2, we may assume that X^a is nonspecial and of cardinality \kappa for each a \in X .
For \beta \in X define
\displaystyle C_\beta := \{\alpha \in T :\vert S_\alpha \cap \hat{\beta} \cap X \vert  = \aleph_0\}
Later these will be used to define a decomposition X = \bigcup_{n<\omega} X_n , where each X_n is special, so X will be special.

Fact 1. C_\beta is finite for every \beta \in X .

Tree from Fact 1. Red means nonspecial. Grey means ordinal heights.

 

Suppose not. Let C_\beta be infinite. In particular, \hat{\beta}\cap X is infinite. Remember our enumeration of [\kappa]^\omega ? Well, pick \xi<\kappa such that A_\xi = \hat{\beta}\cap X .

Since we have MA, we get that X^\beta is nonspecial and has cardinality \kappa . So find an \alpha \in X^\beta such that \xi < \alpha .

Claim: A_\xi \cap \alpha is not covered by finitely many S_\gamma where \gamma < \alpha .

Recall that an infinite, almost disjoint family cannot finitely cover an infinite set. So \{S_\gamma : \gamma < \alpha\} cannot finitely cover A_\xi \cap \hat{\alpha} = A_\xi \cap \hat{\beta} = A_\xi .

This yields a contradiction with property (ii) of the S_\alpha ‘s as there will be a \gamma \in A_\xi \cap S_\alpha = \hat{\beta}\cap X\cap S_\alpha which means \gamma \in S_\alpha , ie \{\gamma, \alpha\} \in K_1 , but we had assumed [X]^2 \subseteq K_0 .

[QED, Fact 1]

So now we have a candidate for decomposing X into countably many (hopefully small) pieces.

Let X_n = \{\beta \in X: \vert C_\beta \vert = n\} . The following fact will finish the proof.

Fact 2: Each X_n is special.

Suppose that X_n is nonspecial. By lemma 2, find a \alpha \in X_n such that T^{\alpha} \cap X_n is nonspecial. Let C_\alpha = \{\beta_1, \dots, \beta_n\} , written in increasing (ordinal) order.

The idea here is that if we extend to an element \alpha^\prime \in T^{\alpha}\cap X_n , then C_\alpha = C_{\alpha^\prime} ; it stays fixed! We will extend twice.

Tree from Fact 2. Red means nonspecial. Grey means ordinal heights.

 

Since T^{\alpha}\cap X_n is nonspecial, we may find an \alpha^\prime \in T^{\alpha}\cap X_n such that A := \{\gamma \in X_n : \beta_n < \gamma <_T \alpha^\prime\} is infinite. (There is a subtle point here about which ordering we are using.)

Remember that enumeration of [\kappa]^\omega ? Let \xi<\kappa be such that A_\xi = A .

Since T^{\alpha^\prime} \cap X_n is nonspecial it has cardinality \kappa . Choose an \alpha^{\prime\prime} < \kappa such that \alpha^{\prime\prime} \in T^{\alpha^\prime} \cap X_n .

Note C_{\alpha^{\prime\prime}} = \{\beta_1, \dots, \beta_n\} , so A_\xi \cap S_\beta is finite for every \beta<\alpha^{\prime\prime} .

Thus by property (ii), S_{\alpha^{\prime\prime}} \cap A_\xi \neq \emptyset . i.e. There is a \gamma \in X_n such that \gamma < \alpha^{\prime\prime} and \gamma \in S_{\alpha^{\prime\prime}} , a contradiction.

[QED]

 

3 thoughts on “MA and its effect on Tree Partitions”

  1. Corrections

    Your definition of nonspecial should have a superscript 1, not 2.

    You also need to change the descriptive text at the end of that sentence where you changed the number.

    In the statement of the theorem, it’s confusing to have T on the right side of the arrow, as the T on the left side refers to the specific tree introduced earlier in the sentence, whereas when you put T on the right side you really mean any nonspecial tree.

    Your statement of Lemma 1 is confusing, because the usual definition Aronszajn tree requires that it have cardinality \aleph_1 . Rather than “Aronszajn tree T” you mean “tree T with no uncountable chain”.

    Two comments about your Lemma 2:
    1) The condition “of cardinality 2^{ℵ_0} is not required in the statement of the lemma.
    2) In the proof, the point is that there cannot be nonspecial many nodes with special upwards cones. If there were, you get a contradiction by considering a minimal such node, as it would have a nonspecial cone above it.

    The usual definition of \hat a contains < rather than \leq .

    You are consistent in your use of Aronszajn throughout to mean a tree without uncountable chain, but this seems to be nonstandard.

    In the second sentence of the proof of Fact 2, “special” should be “nonspecial”.

    In the statement of the Claim inside the proof of Fact 1, there is a hat missing from A_\xi \cap \hat\alpha .

    Questions

    I'm reasonably confident that the hypotheses of the theorem can be weakened. Instead of requiring the full MA and \left|T\right| = \mathfrak c , we can simply assume that T is a tree with no uncountable chains such that \left|T\right| = \mathfrak m , where \mathfrak m is the smallest cardinal \kappa for which MA_\kappa is false.
    The required version of Lemma 1 is: If T is a tree with no uncountable chain such that \left|T\right| < \mathfrak m then T must be special. (Thus nonspecial trees with no uncountable chain must have cardinality \geq \mathfrak m .) This is Corollary 41I of Fremlin's textbook "Consequences of Martin's Axiom".
    Lemma 2 doesn't depend on the cardinality as I mentioned earlier.
    I think Lemma 3 simply requires \kappa to be \leq \mathfrak p , which is certainly true if \kappa \leq \mathfrak m .
    Does anyone see anything wrong with this?

    Like

    1. Thanks again for the proofing. I assimilated all of them except your comment about the proof of Lemma 2.

      I also clumped your comments together for ease of reading.

      Like

  2. Pingback: Another Combinatorial Result

Comments are closed.