(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).
Later it was shown that this is the best you can do, as the strengthenings are consistent:
Theorem(Hajnal). Under CH,
Theorem (Todorcevic). Under PFA, for any countable ordinal,
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
(Nonspecial Tree,
This is the analogue or the Erdos-Rado theorem.
Recall that a tree is nonspecial if
, which means that any countable partition
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
a tree with no uncountable chains and
we have
.
(Of course here, should really be
Nonspecial,
. Throughout this talk I will assume that you understand that I am not demanding a copy of
in the first colour.)
Through the proof we will actually get the superficially stronger result:
Theorem. Assume MA. Let
be a tree with no uncountable chains and
. There is a partition
such that
- There is no nonspecial subtree
such that
;
- There is no set
such that
, otp
and
.
We will need the following standard results about MA and trees:
Lemma 1. Assume MA. Every Aronszajn tree
of cardinality
is special. (Thus nonspecial Aronszajn trees have cardinality
)
Lemma 2. Every nonspecial treeof cardinality
can be pruned to a nonspecial tree
such that for all
,
is nonspecial.
To clarify, here an Aronszajn tree is a tree with uncountably many nodes, countable levels and no uncountable chains.
Recall. For a tree,
, the set of predecessors in
.
Lemma 3. Assume MA. Let
be an nonspecial aronszajn tree (of cardinality
) with underlying set
that agrees with the tree ordering. (i.e.
implies
). Fix
.
THEN there is a familysuch that
is finite for
;
- If
, (and if
is not covered by finitely many
with
) then
.
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 , 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 be an nonspecial aronszajn tree (of cardinality
) with underlying set
that agrees with the tree ordering. Assume by Lemma 2, that we have pruned
properly. Fix
. Let
be a family as described in Lemma 3.
Define by
iff
.
Claim 1. There are no 1-homogeneous subsets of order-type
.
Let , with
. Then
, which violates the first condition of Lemma 3.
Claim 2. There is no 0-homogeneous nonspecial tree
.
Suppose not. By Lemma 1 and 2, we may assume that is nonspecial and of cardinality
for each
.
For define
Later these will be used to define a decomposition , where each
is special, so
will be special.
Fact 1.
is finite for every
.

Suppose not. Let be infinite. In particular,
is infinite. Remember our enumeration of
? Well, pick
such that
.
Since we have MA, we get that is nonspecial and has cardinality
. So find an
such that
.
Claim:
is not covered by finitely many
where
.
Recall that an infinite, almost disjoint family cannot finitely cover an infinite set. So cannot finitely cover
.
This yields a contradiction with property (ii) of the ‘s as there will be a
which means
, ie
, but we had assumed
.
[QED, Fact 1]
So now we have a candidate for decomposing into countably many (hopefully small) pieces.
Let . The following fact will finish the proof.
Fact 2: Each
is special.
Suppose that is nonspecial. By lemma 2, find a
such that
is nonspecial. Let
, written in increasing (ordinal) order.
The idea here is that if we extend to an element , then
; it stays fixed! We will extend twice.

Since is nonspecial, we may find an
such that
is infinite. (There is a subtle point here about which ordering we are using.)
Remember that enumeration of ? Let
be such that
.
Since is nonspecial it has cardinality
. Choose an
such that
.
Note , so
is finite for every
.
Thus by property (ii), . i.e. There is a
such that
and
, a contradiction.
[QED]
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
. Rather than “Aronszajn tree T” you mean “tree T with no uncountable chain”.
Two comments about your Lemma 2:
is not required in the statement of the lemma.
1) The condition “of cardinality
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
contains
rather than
.
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
.
Questions
I'm reasonably confident that the hypotheses of the theorem can be weakened. Instead of requiring the full MA and
, we can simply assume that
is a tree with no uncountable chains such that
, where
is the smallest cardinal
for which
is false.
is a tree with no uncountable chain such that
then
must be special. (Thus nonspecial trees with no uncountable chain must have cardinality
.) This is Corollary 41I of Fremlin's textbook "Consequences of Martin's Axiom".
to be
, which is certainly true if
.
The required version of Lemma 1 is: If
Lemma 2 doesn't depend on the cardinality as I mentioned earlier.
I think Lemma 3 simply requires
Does anyone see anything wrong with this?
LikeLike
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.
LikeLike