[This document was typeset using Luca Trevisan‘s LaTeX2WP. I will refer to result (or definition ) from last lecture as ]

** 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 1For 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.

Definition 2Let be a regular uncountable cardinal. Thecanonical functions forare defined inductively: A function is an -th canonical function iff

A -th canonical function exists for allFor all there is a -th canonical function for such that andFor 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 3If 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.

Lemma 4Let be an uncountable regular cardinal, let and let be such that the -th canonical function exists. Then iff

*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 5For 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.

Lemma 6Let be a regular uncountable cardinal.

The -th canonical function exists for allIf 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.

Lemma 7Let be an uncountable regular cardinal and let

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

Theorem 8 (Galvin-Hajnal)Let be an uncountable regular cardinal, let be a (not necessarily strictly) increasing continuous sequence of cardinals, let and set for If then

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 10Suppose that are uncountable regular cardinals and is -inaccessible. If then

*Proof:* By Corollary 9, and by Lemma 7,

Corollary 11Let be as in Theorem 8.

Let be a sequence of cardinals such that ThenLet be an increasing sequence of nonzero cardinals such that ThenLet 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.

Corollary 12Let be a cardinal of uncountable cofinality and suppose that is -inaccessible. Let be a strictly increasing and continuous sequence of infinite cardinals cofinal in Let

IfthenIf thenIf for all and for all then

*Proof:* In Corollary 11, take and To prove 1, notice that and Item 2 follows from Corollary 11.3, and item 3 follows from the fact that

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

*Proof:* This follows from Corollary 12.1 and Lemma 6.2.

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 14Let 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 16Let be a set. Aset-mappingon is a function such that . Given such we say that isfree with respect toiff

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.

Theorem 17 (Hajnal)Let and be cardinals with and infinite. Let be a set-mapping on such that for all Then there is an of size that is free with respect to

*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 18A structure in a countable language with a distinguished unary relation (interpreted in by ) is said to beof typeiff and

Chang’s conjectureis 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.

Theorem 19 (Magidor)Chang’s conjecture implies that if is strong limit, then

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.]

[…] the Galvin-Hajnal results on powers of singulars of uncountable cofinality (see lectures II.6 and II.7). His first success was an extension to cardinals of countable cofinality. For example: Theorem […]

[…] for ordinals. We briefly encountered this weakening when discussing Chang’s conjecture in lecture II.7. Definition 16 Given ordinals say that iff for any there is an such that Similarly, by […]

Hi again,

little typo in the proof of Th 8: In two places it should be instead of

Thanks for the notes by the way

Ha! Well spotted, thanks. There was another + missing, (Corrected now, but not in the pdf.)

I am *slowly* turning the notes into a book, and would like to mention you in the acknowledgements section. What name should I use? (If you rather tell me by email, try a_b94@hotmail.com, which is the account I keep for these matters.)

[…] We also need the notion of Rowbottom cardinal, that requires a significant weakening of the ordinary partition relation for ordinals. We briefly encountered this weakening when discussing Chang’s conjecture in lecture II.7. […]

[…] the Galvin-Hajnal results on powers of singulars of uncountable cofinality (see lectures II.6 and II.7). His first success was an extension to cardinals of countable cofinality. For […]