In this post, we shall provide a proof of Todorcevic’s theorem, that implies . This will show that the Erdos-Rado theorem that we discussed in an earlier post, is consistently optimal. Our exposition of Todorcevic’s theorem would be slightly more general, with the benefit of yielding another famous theorem of Todorcevic: .
We commence by fixing two sequences (whose existence are basic ZFC facts):
- Let be a sequence of injections such that is countable for every ;
- Let be a sequence of strictly increasing functions, such that implies that is finite.
Denote .
This post will center around the analysis of the following object: let be the function satisfying for all :
Define and by letting for all :
Proposition 1. For every subset of order-type , we have .
Proof. Towards a contradiction, suppose that is of order-type and . Let , , and .
Fix such that whenever . Let . Put , and likewise . Since and are injective, each of the sets is finite, so we may find some which is not in .
By , we get that . As is strictly increasing, this means that . Likewise, , and It follows that and , contradicting the fact that .
For a set and , denote .
Proposition 2. Every uncountable , admits an uncountable subset such that
Proof. Let . Then is uncountable and for every , either is empty, or is uncountable. Fix in . Let
Then
Proposition 3. For every uncountable , the set contains a club.
Proof. Suppose that is a given uncountable set. By restricting our attention to an uncountable subset, we may assume that satisfies . Denote . Then is the intersection of countably many clubs. Thus, it suffices to show that for every , there exists some in for which .
Fix .
Pick above . Put , and . Since , the set is non-empty, and hence uncountable, so let us pick above . Put , , , and . Note:
- is finite, since is injective;
- , since witnesses that ;
- , since .
Fix above . Then:
- , since ;
- , and hence . That is, ;
- , since ;
- , and hence ;
- , and hence ;
- , since is strictly increasing;
- , since ;
- if , then and ;
- if and , then .
If follows that . In particular, .
Proposition 4. Suppose that is unbounded in .
Then for every uncountable subset .
Proof. Suppose that is a given uncountable set. As in the proof of Propositon 3, we may assume that , and consider the club .
Fix . Since is countable, let us find an injection and an uncountable subset for which . Define , by letting for all . Note that . [For suppose that is an element of . As is unbounded in , there exists some such that is infinite, but then also is infinite for , contradicting the fact that as the definition of dictates.]
Let be the least integer such that . Fix a sequence of ordinals in such that for all . By minimality of , there exists some such that . Thus, let us fix some for which is infinite.
As witnesses that , we infer that , and hence we may pick some . Put , and let be least integer greater than for which . Then:
- , and .
- , since ;
- , since is order-preserving;
- , since .
It follows that , and hence . .
Corollary 1 (Todorcevic, 1989). entails .
Proof. Recall that iff there exists a sequence which is increasing and unbounded in .
Corollary 2 (Hajnal, 1960). CH entails .
Proof. CH implies .
Corollary 3 (Todorcevic, 1987). .
Proof. Let be a partition of into mutually disjoint stationary sets. Define , by letting Then, for every uncountable , contains a club, and hence .

Pingback: Rectangles vs. squares at the level of the first uncountable cardinal | Assaf Rinot
Hey,
Great post, I really enjoyed reading this today! Do you know if the graph is uncountably chromatic regardless of the value of the bounding number? Or is it countably chromatic if your sequence is <*-bounded?
Thanks!
Thanks, Dani! , for which the corresponding graph is countably chromatic.
Under Martin’s Axiom, this graph is countably chromatic. Can’t tell at the moment whether the boundedness of F suffices, but I suspect that, at least, for every bounded F, there is a choice of
p.s.
Let me draw your attention to slide #65 (onwards) from here.
Thanks! The poset of finite good colourings should work with MA, right?
Nice conference program, I will definitely look at your talk!
Exactly right. The CCC follows from Proposition 1.