A. The Galvin-Hajnal rank and an improvement of Theorem 3.1
Last lecture, I covered the first theorem of the Galvin-Hajnal paper and several corollaries. Recall that the result, Theorem 3.1, states that if and are uncountable regular cardinals, and is -inaccessible, then for any sequence of cardinals such that for all
In particular (see, for example, Corollary 3.7), if and is strong limit, then
The argument relied in the notion of an almost disjoint transversal. Assume that is regular and uncountable, and recall that if is a sequence of sets, then is an a.d.t. for Here, is an a.d.t. for iff and whenever then is bounded.
With as above, Theorem 3.1 was proved by showing that there is an a.d.t. for of size and then proving that, provided that for all then
In fact, the argument showed a bit more. Recall that if then Then, for any ,
The proof of this result was inductive, taking advantage of the well-foundedness of the partial order defined on by iff is bounded in That is well-founded allows us to define a rank for each and we can argue by considering a counterexample of least possible rank to the statement from the previous paragraph.
In fact, more precise results are possible. Galvin and Hajnal observed that replacing the ideal of bounded sets with the nonstationary ideal (or, really, any normal ideal), results in a quantitative improvement of Theorem 3.1.
Definition 1 For let iff is nonstationary. Similarly, define iff is nonstationary, etc.
Since the collection of nonstationary subsets of is a -complete (in fact, normal) ideal, then is well-founded, and is defined for any is usually called the Galvin-Hajnal rank of
Before stating the result, Theorem 8 below, we prove some preliminary lemmas about the behavior of the Galvin-Hajnal rank.
- A -th canonical function exists for all
- For all there is a -th canonical function for such that and
- For all if for all there is some -th canonical function for such that then
Of course, the idea is that an -th canonical function witnesses and is canonical just as ordinals are canonical among well-ordered sets. We prove this in a series of lemmas.
Lemma 3 If is regular and uncountable, and are -th canonical functions for then
Proof: By definition, if and are -th canonical functions for then both and hold, so
By the lemma, we can simply talk about the -th canonical function, if one exists.
Proof: By induction, so if then
To prove the other implication, argue by induction, and assume that for all and all if then where is the -th canonical function.
Suppose that Then there is some such that It follows that for any By induction, By definition, But then as wanted.
Corollary 5 For any regular uncountable cardinal if the -th canonical function for exists, then
Proof: By induction on But is impossible by Lemma 4.
It is easy to exhibit the first few canonical functions.
- The -th canonical function exists for all
- If then iff is stationary.
- iff is stationary.
Proof: For we can set to be the function constantly equal to and we can also set to be the identity. It is straightforward from induction and Fodor’s lemma that Definition 2 is satisfied. Items 2 and 3 follow now from Lemma 4.
In general, given choose a (nonstrictly) increasing sequence of ordinals such that This is possible, since Now set for all
We argue by induction that Definition 2 is satisfied. For this, suppose that Then is stationary. By Fodor’s lemma, there is some fixed such that is stationary. But then
For regular uncountable and it may or may not be the case that the -canonical function exists.
For example, Galvin showed that the -th function does not exist in while in a model of Jech, Magidor, Mitchell, and Prikry, the -th canonical function exists for all This statement is equiconsistent with the existence of a measurable cardinal (the model is obtained by a construction that gives that is precipitous, and it is easy to see that the existence of for all implies this). See Thomas Jech, Menachem Magidor, William Mitchell, and Karel Prikry, Precipitous Ideals, The Journal of Symbolic Logic, 45 (1) (Mar., 1980), 1–8.
If one is only interested in the existence of the -th canonical function for for all for some fixed this does not require any large cardinals, and its consistency was established in Thomas Jech, Saharon Shelah, A note on canonical functions, Israel J. Math. 68 (3) (1989), 376–380.
Given an uncountable regular cardinal forcing allows us to specify in which sense the canonical functions for are, indeed, canonical: These are the functions such that the ordinal in the internal ultrapower is independent of the -generic filter This characterization is often taken in place of Definition 2.
- If is regular uncountable and -inaccessible, and then
Proof: Suppose Let
if and otherwise.
Then so if and if then the restriction of to is in the set product There are at most many such functions and since any ordinal below is represented by one of them, it follows that as wanted.
Item 2 follows immediately, since if then for all and by regularity. But then
Shelah has shown (by a more elaborate argument) that Lemma 7.2 still holds if one weakens the -inaccessibility assumption on to the requirement that for all of cofinality This allows us to weaken the assumption in the same way in the corollaries below.
We are now ready to state the second Galvin-Hajnal theorem.
For notational convenience, let’s write for where with for all
The proof of Theorem 8 is by induction on When the are strictly increasing and this is a result of Erdős, Hajnal, and Milner.
Proof: In the notation of Theorem 8, take for all so and Note that
Notice that Theorem 3.1 follows immediately:
Corollary 10 Suppose that are uncountable regular cardinals and is -inaccessible. If then
Corollary 11 Let be as in Theorem 8.
- Let be a sequence of cardinals such that Then
- Let be an increasing sequence of nonzero cardinals such that Then
- Let be a strictly increasing sequence of infinite cardinals. If is a cardinal, and then
Proof: For 1, let and let be an a.d.t. for of size By assumption, for all so
For 2, recall from Corollary 8 in lecture II.2 that
For 3, let for Then for all and the result follows from item 1.
- If then
- If then
- If for all and for all then
Recall the very general statement of Silver’s theorem, Theorem 21 in lecture II.5:
Corollary 13 (Silver) Let be a -inaccessible cardinal of uncountable cofinality Let be a strictly increasing sequence of cardinals cofinal in Suppose that there is some such that is stationary in Then
I won’t include a full proof of Theorem 8 and instead present only a sketch. To prove Theorem 8 two additional ingredients (whose proofs I skip) are needed. One is the Erdős-Rado theorem, that we will prove in Chapter III.
Definition 14 Let be cardinals and let Given a set recall that The statement means that whenever there is such that the restriction of to is constant. If this is not the case, we write
It is customary in the field to call the functions as above colorings, and to refer to the sets as homogeneous with respect to
This “arrow notation” turns to be very useful. For example, the infinitary version of Ramsey’s theorem is simply A well-known example due to Sierpiński shows that or, more generally, This will be discussed in Chapter 3.
The second ingredient is a result of Hajnal on set-mappings.
Definition 16 Let be a set. A set-mapping on is a function such that . Given such we say that is free with respect to iff
For example, the function given by is a set-mapping on for all and any free is a singleton. Ruziewicz conjectured in 1936 that if one strengthens the cardinality restriction on to for all where is some fixed cardinal, then there is now a free of size This was shown by Hajnal in 1961.
Proof of Theorem 8: Proceed by induction on
Suppose first that
Let be an a.d.t. for By Lemma 6.2, is stationary. Let and is limit so is also stationary. Note that for all and and there is therefore a such that (It is here that the continuity of the sequence is used.)
By Fodor’s lemma, for each there is a stationary set and an ordinal such that for any For fixed sets let and and notice that
Since there are only such pairs and it follows that and we are done.
Suppose now that and that the result holds for all and corresponding such that
Let be an a.d.t. for For and let be least such that and let Notice that since only if but the set of these ordinals is nonstationary since It follows that
This shows that where and therefore and we are done if we show that for each
In fact, for all To see this, fix such a and begin by defining a set-mapping on by
Clearly, is an a.d.t. for Note that for all so Notice now that the hypotheses of the theorem apply to and in place of and Since by the induction hypothesis we have that
Let and If, towards a contradiction, then by Theorem 17 there is a set of size that is free with respect to
Notice that and therefore (since is free) we can inductively find a sequence with each and whenever By definition of it follows that for all such there is an such that
By the Erdős-Rado Theorem 15 there is an infinite set homogeneous for the coloring Let be the constant value that the map takes on If then and therefore there is an infinite decreasing sequence of ordinals, contradiction.
I conclude with an application not mentioned in lecture.
Definition 18 A structure in a countable language with a distinguished unary relation (interpreted in by ) is said to be of type iff and
Chang’s conjecture is the statement that whenever is of type there is an elementary substructure of type
Chang’s conjecture is consistent. It holds under and can be forced from a Ramsey cardinal. A large cardinal of comparable strength is required, since Silver showed that Chang’s conjecture implies the existence of
By arguing about Skolem functions, one can show without too much effort that Chang’s conjecture is equivalent to the statement that whenever there is a subset of of order type such that is countable.
Notice that from Corollary 3.7 from last lecture without assuming Chang’s conjecture we have that if is strong limit then It is open whether Theorem 19 holds without the additional assumption.
Proof: The following argument is due to Galvin.
By say, Corollary 12, it is enough to show that for all
To prove this, let be such that Using Lemma 6, for let be the -th canonical function for so for all Let be a club witnessing this, so for all if then
Define as follows: If is finite, let where we take the minimum of an empty intersection to be zero.
By Chang’s conjecture, there is an of order type such that
We claim that which concludes the proof.
To see the claim, notice first that whenever and Suppose otherwise, and fix counterexamples. Then By definition of this means that there must be some finite such that and therefore, by definition of and it follows that contradiction.
But the claim concludes the proof, since then in and therefore, since we must have
Besides the original Galvin-Hajnal paper, a good reference for this lecture is the book Paul Erdös, András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: Partition relations for cardinals, North-Holland (1984).
[Here is a printable version of this post.]