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

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

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.

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. Ari Brodsky says:

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

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. Micheal Pawliuk says:

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