(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:
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 tree of 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 family such that
- is finite for ;
- If , (and if is not covered by finitely many with ) then .
. 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.
. 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.
 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 .
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.