Let me begin with a couple of updates.
In the last Corollary of the Appendix to lecture I.5, I indicate that in we have that
whenever is not for some infinite limit ordinal In fact,
This result is best possible in terms of positive results. In Theorem 11 of the paper by John Hickman listed at the end, it is shown that for any such it is consistent with that there is an with for which
I also want to give an update on the topics discussed in lecture III.3.
and Hajnal asked whether it is possible to have infinite cardinals such that
Galvin and Prikry showed (see Corollaries 16 and 18 of lecture III.3) that any such must be larger than and that
Following a nice suggestion of Grigor Sargsyan, we use arguments as in Theorem 9 from lecture III.5 to show that this partition relation cannot hold.
The key is the following:
Lemma 1 If there are infinite cardinals such that then for every sufficiently large there is an elementary embedding such that and
Here is a brief sketch:
Proof: By Corollary 20 from lecture III.3, the given relation is equivalent to Consider a -Skolem function so that any closed under is both closed under -sequences and an elementary substructure of
Use to define a coloring by setting whenever and otherwise. By assumption, there is with Note that if is the closure of under then But we can assure that and the result follows by taking as the transitive collapse of
One concludes the proof by noting that it is impossible to have such embeddings. For this, it suffices that and that admits a fixed point past its critical point. One then obtains a contradiction just as in Kunen’s proof that there are no embeddings see Corollary 9 in lecture III.3.
Similarly, Matthew Foreman has shown that there are no embeddings with closed under -sequences. The reason is that any such embedding must admit a fixed point past its critical point, as can be argued from the existence of scales. See the paper by Vickers and Welch listed at the end for a proof of this result.
On the other hand, it is still open whether one can have embeddings such that computes cofinality correctly.
1. The Baumgartner-Hajnal theorem
In Theorem 2 of lecture III.5 we showed the -Rado result that
whenever is regular. It is natural to wonder whether stronger results are possible. We restrict ourselves here to the case Due to time constraints, we state quite a few results without proof.
1.1. Hajnal’s counterexample
In general, we cannot even have
For example, Hajnal showed that this fails under and showed that it fails in well-known forcing extensions (e.g., after adding one Cohen real). I present here Hajnal’s argument:
Theorem 2 (Hajnal) Let be regular and assume that Then
This means that there is a coloring that neither admits a -homogeneous bipartite graph with plus vertices, nor a -homogeneous bipartite graph with vertices below and vertices above.
From this, one immediately concludes:
Corollary 3 If is regular and then
Proof: Let enumerate By transfinite recursion we will define a sequence
of subsets of in terms of which we will then define the coloring We require that and define so that
We start by setting for all Suppose now that and has been defined for all To define we use transfinite recursion to define a sequence
of ordinals below and then set
Fix a bijection let and suppose that has been defined. Let
If this set is nonempty, let Otherwise, let This completes the construction of the sequence hence that of the sequence and of the coloring
It remains to show that has the stated property. First, we observe the following almost-disjoint property of the sets
Proof: We may assume that Let be such that We then have that
since any nonzero with is not in by definition of
Next we check that there is no -homogeneous graph of type In effect, fix and two ordinals such that If
then contradicting Lemma 4.
Now we check that there is no -homogeneous graph of type Towards a contradiction, suppose that that and that
Proof: Suppose otherwise. Pick
and let be such that Pick and let be such that
We claim that Hence
and since we obtain a contradiction.
To see that note that:
- For any if then
and, if then
- Therefore has size strictly less than by regularity of
It follows that
Let enumerate the first elements of Now set
so has size and there is some such that
Pick and let be such that Just as above, we reach a contradiction once we show that
To prove that this is the case, let be such that Since is regular, it follows from Lemma 4 that
has size and therefore so does
1.2. Countable ordinals
Hajnal’s result rules out a natural extension of the relation
so we need to look a bit harder for possible extensions. Note that the relation implies immediately that
for any This is because of the following result:
Lemma 6 Any stationary subset of contains closed subsets of order type for any countable
(Of course, we cannot replace with since there are disjoint stationary sets.)
Proof: Let be a given stationary set, and argue by induction on that contains closed copies of with arbitrarily large. (Of course, if the result holds, this must be the case: Given any , notice that is stationary, so it must contain a closed copy of , and .)
This strengthened version holds trivially for finite or successor, by induction. So it suffices to show it for limit, assuming it holds for all smaller ordinals. Define a club with increasing enumeration as follows:
Let be strictly increasing and cofinal in . Since contains closed copies of for all , with their minima arbitrarily large, by choosing such copies with and taking their union, we see that must contain copies of , closed in their supremum, with arbitrarily large minimum element. (I am not claiming that built this way has order type . For example, if and , then would have order type ; but for sure is closed in its supremum and has order type at least . So a suitable initial segment of is as wanted.)
Let be the supremum of such a copy of . At limit ordinals , let . Once is defined, find such a copy of inside with minimum larger than , and let be its supremum.
The set so constructed is club, so it meets . If they meet in or in a , this immediately gives us a closed copy of inside . If they meet in a with limit, let be strictly increasing and cofinal in , and consider an appropriate initial segment of , where is a closed copy of in .
A direct extension of the relation is briefly discussed in Subsection 1.6. This relation certainly implies so one natural attempt at extending this result is seeing whether for a fixed there is a such that This is not the case: From Ramsey’s theorem, we know that however, no countable satisfies In fact, more is true:
Proof: Let be an ordering of in order type and let be the corresponding “” coloring:
Then clearly there can be no -homogeneous set of order type , while a -homogeneous set of order type would give us an infinite -descending sequence.
Since for all and all the best we could hope for is that for any and any finite there is an such that Note that, trivially, However, relations of the form are already significantly harder to achieve. The key to positive results of this kind is to study indecomposable ordinals, those of the form
Theorem 8 Let be countable, and let be finite. Suppose that
Corollary 9 (-Milner) If and then Thus
For certain ordinals, something stronger is true; for example, Specker showed that
for all finite but the same statement fails if we replace with on the other hand, Chang showed that
for all finite The precise characterization of those countable ordinals such that
for all finite stills seems to be open. Special attention has been given to partition ordinals, these are countable ordinals such that
Theorem 10 (Galvin-Larson) Any partition ordinal other than has the form for some countable
The Galvin-Larson result uses the notion of pinning, introduced by Specker:
Definition 11 (Specker) An ordinal pins an ordinal in symbols
iff there is a pinning map that is, a map such that for any we have that
The connection of this notion with the partition calculus comes from Specker’s observation that if for an ordinal and a cardinal, and if then For example, Specker showed that for and that from which it follows that for
Theorem 12 (Schipperus) If is indecomposable or the sum of two indecomposable ordinals, then
On the other hand, one has:
- If is the sum of at least four indecomposable ordinals, then
- If is the sum of at least three indecomposable ordinals, then
- If is the sum of two indecomposable ordinals, then
- If and then
Items 1–3 of Theorem 13 are due to Schipperus, with 6 instead of 5 in item 3; the stated version of item 3 is due to Larson, and item 4 is due to Darby.
1.3. Non-special linear orders
Another possible extension of the relation for all comes from replacing with some other (necessarily uncountable) linear order. A first result of this kind was obtained by and Rado. Recall that is the order type of
Proof: Let be uncountable. Without loss, assume that is of size and let enumerate it. Let be a given coloring.
Mimicking the proof that for each limit let’s build a strictly increasing sequence such that:
- for all
- for all
- is 1-homogeneous for
- Either or else for some and there is no such that items 1–3 hold with in place of
If for some limit we have we are done, as we have found a subset of of order type that is -homogeneous for We can then assume that for all limit ordinals By repeated application of Fodor’s lemma we can then find an uncountable (in fact, stationary) subset of consisting of limit ordinals, and such that there is an with for all and there are ordinals such that for all and all
It then follows that whenever and in implies then is -homogeneous. Otherwise, if are in and we could take contradiction.
We have essentially reduced the partition problem to a problem which is solely about ordered sets: It now suffices to show that whenever is an uncountable subset of then for all We prove something stronger; recall that is the order type of (Actually, we need something a bit stronger, namely, that there is a subset of of type whose indices are also ordered that way. This follows easily by induction from the argument below. We will prove a more general result later, so I will leave this last step as an exercise.)
The coinitiality of and the cofinality of are both countable, since and It follows that and are in fact countable. Also, is a final segment of and is an initial segment. Let so is uncountable and for any both and are uncountable.
A straightforward recursive construction using the above observation easily gives us that
Applying Lemma 15 to the set we are done.
A careful study of the above argument seems to indicate that the notion below is the key to the “right” generalization of for The concept was introduced by Galvin, although the name is probably due to
Definition 16 A linear order is non-special if it is not the union of countably many reverse well-orders, i.e.,
Clearly, any non-special order is uncountable.
Here are some examples of non-special orders:
- Suppose that is an uncountable linear order and that Then It follows that is non-special, since if is partitioned into countably many pieces, one of them must be uncountable (and does not embed ). In particular, the set of reals or, more generally, any uncountable subset of is non-special. Because of this example, uncountable linearly ordered sets that embed neither nor are called of real type. It easily follows from the argument above that for any such we have for all
- Baumgartner has shown that there are non-special orders such that embeds into any uncountable subset. For example, for each limit let be cofinal in of order type Denote by the -th member in the increasing enumeration of and set
for countable limit ordinals iff, letting be least such that then
Galvin noted that Lemma 7 could be improved as follows:
Proof: Consider an arbitrary partition of into many pieces ; we must show that at least one of them admits a subset of order type . Define by setting, for , iff there are such that and . Clearly does not admit a 0-homogeneous set of order type . By assumption, it must therefore admit a -homogeneous set of order type . All but finitely many of its members must then belong to the same , and thus contains a subset of order type , as wanted.
The Baumgartner-Hajnal theorem is the statement that a strong converse to Lemma 17 holds.
In Subsection 1.5, I present a proof of Theorem 18 in the particular case that The argument I will show is very recent and due to Clinton Conley. It also provides us with additional information about colorings of and I address this as well.
1.4. Partial orders
The original proof of the Baumgartner-Hajnal theorem used forcing. More precisely, the result was shown under the additional assumption of and then an absoluteness result is invoked to guarantee that it follows without this axiom. This involves two steps: Assume and let be a finite coloring of Force (plus ) the usual way, so the forcing notion involved is ccc, and is preserved. In the extension, still holds, and therefore
- We may assume that is infinite. Let be a bijection. Use and to define a tree of height any (infinite) branch through which gives a homogeneous subset of for of order type The tree is defined in the ground model, but it is ill-founded in the forcing extension. Well-foundedness is absolute (being equivalent to the existence of a ranking function) and therefore the tree must also be ill-founded in the ground model. It follows that there is, in a homogeneous subset of for of type This is true for all and all colorings and therefore
- More delicately, one needs to verify that, indeed, still holds in the forcing extension. This uses that the forcing involved is ccc.
It is natural to wonder whether Theorem 18 admits a forcing-free proof. Galvin found such an argument, and noticed that in a natural way one is led to consider not just linear orders but partial orders. Somewhat later, extended the result to this setting:
for all and all
As with the original argument of Baumgartner and Hajnal, ‘s proof uses forcing, and I do not know of a way of removing this need. For the case a new (forcing-free) proof has been recently found by Foreman and Hajnal; it is a significant generalization of the elementary substructures argument used to prove the -Rado Theorem 1 from last lecture. Together with the argument below, this provides us with a nice, relatively short, purely combinatorial proof of the Baumgartner-Hajnal theorem for linear orders. The Foreman-Hajnal result can be found in the survey by Hajnal and Larson listed in the references at the end.
This is not yet the end of the story. has shown that implies for all It is not known yet whether the same follows from I believe the best known result in this direction is due to Hirschorn, who showed that under one has
1.5. The Baumgartner-Hajnal theorem
I follow closely the note by Conley listed in the references at the end. Our goal is to show that if is a non-special linear order such that then for all and all
Fix a linearly ordered set For sets say that
iff for all and (The notation is commonly used, but we already use to indicate that embeds into )
Fix a proper ideal of subsets of and use terms like small, positive, and large, in the usual way: A small set is a member of A positive set is one not in A large set is one whose complement is in A set is large in iff The quantifier means “for all positive ” Similarly, means “there exists a positive ”
Say that positive sets split iff any positive set contains positive sets and with below
is large in
Note that if is positive and is a coloring, then for any one of
must be positive. Definition 20 asserts that there is a “coherent” way of (almost) always picking the same color that gives us a positive set. One can strengthen this notion as follows:
is large in
Note that an -focused pair is -compatible, and that the notions are hereditary, in the sense that if is -compatible, and and are both positive, then is also -compatible. Similarly with -focused instead of -compatible.
- is -focused for some or
- is -compatible for both and
Proof: Consider the statement
Case 1: It is true, as witnessed by and Let
and notice that is -focused.
Case 2: It is false. We then have
But this is equivalent to
(Otherwise, fixing counterexamples and the complement of the displayed set would contradict the displayed statement immediately preceding it.) Consequently, is -compatible for both and
Note that the notion of an -compatible pair depends on the order in which we list the sets and
- is -focused for some or
- is -compatible for some
Lemma 26 Suppose that positive sets split, and let be a coloring. Then there is a positive and such that whenever is positive, then we may find positive subsets and of with below such that that the pair is -compatible.
In the setting of Lemma 26, it follows that, by passing to a positive subset of we may assume that the coloring is -splitting, in the following sense:
Definition 27 Assume that positive sets split, and let be a coloring. For say that is -splitting iff for any positive there are positive subsets and with below such that is -compatible.
- is below and is below
- is -compatible,
Proof: Use twice that is -splitting, and find positive sets with below and below such that and are all -compatible.
Since is -compatible, then the set
is large in Similarly,
is large in
It follows that Let be in this intersection. Now set
Then is as wanted.
It will be important in what follows to study colorings of It turns out to be convenient to have a representation of different from the standard one. For this, simply recall that any countable linear order dense in itself and without end points is isomorphic to
Extend the lexicographic order on each to a linear order on by setting for iff where is the first coordinate on which they differ, adopting the convention that undefined The following is obvious from the characterization of just mentioned:
For let denote its length. We now define four colorings of
Definition 30 For let be the map given by
These colorings are rather special. and are constant. and do not admit homogeneous sets of type admits a 1-homogeneous set of type and admits a 1-homogeneous set of type These two colorings are standard counterexamples to a version of Ramsey’s theorem on in which the homogeneous set has order type Before hand, we knew that such counterexamples were to be expected, since by Lemma 7.
Proof: As explained after Lemma 26, we may assume that is -splitting for some We now proceed to embed into For this, we recursively construct for each a function so that the functions are compatible as varies and, letting then is as wanted. To guarantee this, we construct in addition for each a positive set so that
- is -compatible whenever are in
- For all whenever
At stage use the splitting assumption and Lemma 28 to find and positive sets and such that
- is below is below
- and and
- is -compatible,
Suppose that the construction has been carried out through stage Stage is completed by going from left to right in To begin with, by the assumption of compatibility, we may assume that there is a set large in such that for all and all with the set
is positive. Apply Lemma 28 to as in stage to obtain and an -compatible pair Then, replace each with the positive set
Suppose now that we have defined and for all smaller than By the assumption of compatibility, we may assume that for all and all with the set
is positive, and that for all and all with the set
Apply Lemma 28 to as before, and obtain and an -compatible pair Now, for each with replace with
and, for each with replace with
At the end of the construction, we obtain an order-preserving injection and now we proceed to verify that it is as desired. Fix If the construction defined before then belongs to the refined version of constructed right after was defined. But then
and we are done.
The following canonization result is immediate:
Proof: Apply Theorem 31 to and the ideal
The above results (as well as the results in the remainder of this subsection) hold for any finite number of colors. In this setting, the only change we obtain is that the basis of colorings in the canonization result has size larger than four, but they are all either constant functions or of the form for
Corollary 33 (-Rado) The partition relation holds, i.e., any coloring of with two colors black and red either admits a black-homogeneous copy of or else it admits an infinite red-homogeneous set.
Note also that cannot be improved to either or
Corollary 34 (Galvin) For any we have i.e., for any coloring of with finitely many colors, there is a copy of that uses at most two colors.
This is an example of a so-called “rainbow” Ramsey theorem. The ultimate result in this direction is due to D. Devlin:
Definition 35 Let
be the Taylor series expansion of about Define the sequence of odd tangent numbers by so
Theorem 36 (Devlin)
- For every positive integer we have
- However, for any we have
We can now deduce the promised version of the Baumgartner-Hajnal theorem from Theorem 31.
Proof: By Theorem 31, if we can find an -splitting, positive set then in fact admits a homogeneous set for of order type
By Corollary 24 and a density argument, we may then assume that there is an such that every positive set can split into positive sets and with below and an -focused pair.
We now proceed by induction on to show that admits an -homogeneous subset of type
Assume the result for all Suppose first that Split into sets below where is -focused. Let be -homogeneous. For each the set
is large in Since is -additive, we may find an in the intersection of all these sets and, clearly, is -homogeneous and of type
Suppose now that is a limit ordinal, and let be increasing and cofinal in Split several times to find
such that each pair with is -focused. By the inductive hypothesis, find an -homogeneous set As in the previous case, refine each with in such a way that
Now continue inductively, finding an -homogeneous set and refining all with
Finally, let Then is -homogeneous and of type
Again, Corollary 37 holds for colorings into any finite number of colors.
Proof: Let By Corollary 37, it suffices to show that positive sets split.
Bearing in mind the proof of Theorem 14, consider a positive and let
Since then has cofinality and it follows that We are done once we show that because then we can replace with and note that for all both and are positive.
We are not assuming that so the argument is slightly more delicate than in Theorem 14. Let be a strictly decreasing, coinitial sequence in For each let be a partition without homogeneous sets of type For let be the least ordinal such that Now define
by and note that witnesses
It would be interesting to find a unified proof of the full Baumgartner-Hajnal theorem following the methods of this subsection, and to see whether these methods can be extended to provide a combinatorial proof of ‘s Theorem 19.
1.6. The topological Baumgartner-Hajnal theorem
An easy variation of the argument used to show Theorem 14 gives us that
whenever is an uncountable subset of meaning that any coloring either admits an infinite increasing -homogeneous set, or else it admits a closed subset of order type that is -homogeneous. The following extension was recently obtained by Schipperus; it solves questions of Laver and Weiss:
Theorem 39 (Schipperus) and for any uncountable any and any
Once again, Schipperus’s argument uses forcing and absoluteness. It is easy to see that being non-special is not enough to imply the result, and I do not know of a more general setting for which Schipperus’s theorem holds; see his paper (listed below) for details.
I do not know whether under or one can prove that for all and
1.7. Partitions of triples
Finally, I would like to close with a couple of words on an extension of a different kind, namely, what occurs when we color triples rather than pairs.
Theorem 40 (Jones) Let be a non-special partial order. Then
- for each
- For item 1 can be improved to for all
It has been conjectured by Jones and others that if is a non-special partial order, then for all and The assumption on cannot be weakened, in light of the following result; a similar obstacle holds for partial orders:
Theorem 41 If is a linear order, is an infinite cardinal, and then
- James Baumgartner, A new class of order types, Annals of Mathematical Logic, 9 (1976), 187–222.
- James Baumgartner, András Hajnal, A proof (involving Martin’s axiom) of a partition relation, Fund. Math., 78 (3) (1973), 193–203.
- Clinton Conley, Colors and ideals: An artistic extravaganza, preprint.
- Paul András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: Partition relations for cardinals, North-Holland, (1984).
- András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.
- John L. Hickman, -minimal lattices, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 26 (2) (1980), 181–191.
- Albin Jones, Partitioning triples and partially ordered sets, Proceedings of the American Mathematical Society, 136 (5) (May 2008), 1823–1830.
- Rene Schipperus, Countable partition ordinals, PhD thesis, University of Colorado, Boulder; Richard Laver, advisor, (1999).
- Rene Schipperus, The topological Baumgartner-Hajnal theorem, Transactions of the American Mathematical Society, DOI: http://dx.doi.org/10.1090/S0002-9947-2012-04990-7
- John Vickers, Philip Welch, On Elementary Embeddings of an Inner Model to the Universe, The Journal for Symbolic Logic, 66 (3) (2001), 1090–1116.
- Neil Williams, Combinatorial set theory, North-Holland (1977).
Typeset using LaTeX2WP. Here is a printable version of this post.