**1. Infinitary Jónsson algebras **

Once again, assume choice throughout. Last lecture, we showed that for any The results below strengthen this fact in several ways.

Definition 1Let be a set. A function is-Jónssonfor iff for all if then

Actually, for a cardinal, the examples to follow usually satisfy the stronger requirement that In the notation from Definition 16 from last lecture,

The following result was originally proved in 1966 with a significantly more elaborate argument. The proof below, from 1976, is due to Galvin and Prikry.

Theorem 2 (Erdös-Hajnal)For any infinite there is an -Jónsson function for

*Proof:* It is enough to show that for all infinite cardinals

Define a version of the equivalence relation on by setting iff there is some such that Choose a representative from each -equivalence class For let and let be least such that

(Note that needs not be in and that it needs not be the least such that )

Consider the function Although may fail to be -Jónsson, we claim that it has the following property: There is an such that for any It is obvious one can now use and a bijection between and to define an -Jónsson function for

To see the claim, assume otherwise and use this to define recursively a sequence as follows:

- Pick such that there is some
- Given (of size ) and let be such that there is some

It follows that is strictly increasing, is strictly decreasing, and for all

Now let and Let be least such that

for some and fix such Note that and so It follows that contradiction.

In a few particular cases, direct proofs are also possible, and I discuss a few below, before exploring generalizations.

I begin with a result of Solovay. We need a preliminary lemma, generalizing Ulam’s Theorem 13 from lecture II.5 that stationary subsets of can be split into many stationary subsets:

Theorem 3 (Solovay)Any stationary subset of a regular cardinal can be split into many disjoint stationary sets.

*Proof:* Let be regular and be stationary, and set

or

We claim that is stationary. To see this, let be an arbitrary club subset of Then the set of limit points of is also club (and a subset of ), so it meets since is stationary. Let Then either has cofinality so it is in or else it has uncountable cofinality. In that case, notice that since it is a limit of points in so is club in and therefore is also club in Were stationary in it would meet and this would contradict the minimality of It follows that and therefore is stationary, as wanted.

Let now be an arbitrary point of If has cofinality it is the limit of an -sequence of successor ordinals. Let be the increasing enumeration of this sequence, and notice that since all ordinals in are limit ordinals. Suppose now that has uncountable cofinality, so is not stationary in Since it follows that is not stationary either, so there is a club subset of disjoint from and let be the increasing enumeration of this club set so, again,

With the sequences defined as above for all we now claim that there is some such that for all the set

is stationary. The proof is by contradiction, assuming that no is as wanted.

It follows then that for all there is some such that the set as above is non-stationary. Fix a club disjoint from it, and let be the club Let where Notice that is club, and so is We claim that This contradicts that is stationary, and therefore there must be a as claimed.

Suppose then that are points in Since then so (hence, ) for all We claim that To see this, let Then (by definition of ), Since then and, since then It follows that Since is cofinal in we must necessarily have

Since is continuous and is a limit ordinal (since it is in ), it follows that But, since is increasing, then also Hence, We have finally reached a contradiction, because but the sequence was chosen so its range is disjoint from This proves that which of course is a contradiction since is stationary. It follows that indeed there is some such that all the sets are stationary for all

Now let be the map

Clearly, is regressive. Also, from the definition of it follows that

for all so is unbounded in since each is in fact stationary, as we showed above. Given any since is regressive, there is some (necessarily, ) such that is stationary, by Fodor’s lemma. A simple induction allows us to define a strictly increasing sequence such that is stationary for all Notice that these many subsets of (hence, of ) so defined are all disjoint. By adding to one of them whatever (if anything) remains of after removing all these sets, we obtain a partition of into many disjoint stationary subsets, as wanted.

Theorem 4 (Solovay)Let be a regular uncountable cardinal. Then In fact, for any infinite regular even if we consider as an order type.

*Proof:* Let be a partition of into stationary sets, and let be given by the unique such that Then is as required, i.e., for any

To see this, let and set Then is a -club subset of so, for all Hence

For we can in fact show something stronger:

Theorem 5 (-Hajnal)For any infinite cardinal i.e., there is a map such that for any

*Proof:* Let enumerate in such a way that each set is listed many times. Inductively define so that and for all

Let and set if for all

We claim that is as wanted. Because given any and if we let be the -st occurrence of in the sequence then and

This can be generalized thanks to the following strengthening of its core idea.

Lemma 6 (Galvin-Prikry)For every infinite cardinal and every there is an injective function such that for all and (Here, is treated as a cardinal rather than an order type.)

*Proof:* If as in Theorem 5, a straightforward transfinite induction suffices to find

For general let enumerate For let be injective and such that for all and

Now, given and let be the least such that and define

Then and It follows that if say, then there is an ordinal such that Therefore and Since is 1-1, we conclude that and But then as well, and is 1-1.

Corollary 7 (Galvin-Prikry)If and are cardinals and is infinite, then

*Proof:* Let be as in Lemma 6 with Since is 1-1, we can define so that for all and But then

The same idea gives us -Jónsson functions for some singular cardinals, as shown by Kunen in this argument from 1971.

*Proof:* Let enumerate By transfinite recursion define such that for all This is possible, because there are elements of and Now let be such that for and if is not an

To see that is -Jónsson, let Let so

The result follows.

This gives us another proof of Kunen’s inconsistency Theorem 13 from lectures II.10 and II.12.

*Proof:* Argue by contradiction. As usual, let be the first fixed point of past its critical point If then elementarity implies that is a strong limit cardinal for all so is a singular strong limit cardinal of cofinality and, by Theorem 8, there is an -Jónsson function If then by elementarity there is some such that But then for some and is in the range of Of course, cannot then be the critical point of and we are done.

For one can further strengthen Corollary 7 as follows.

Theorem 10 (Galvin-Prikry)For any set there is a function such that whenever and then and for any -sequence of pairwise disjoint sets in and any there is a sequence with for all and

*Proof:* In fact, we build so that

- only depends on for any and
- Whenever is a sequence of pairwise disjoint finite subsets of such that is infinite, and then there is a sequence with for all is infinite, and

To do this, use Zorn’s lemma to find a maximal sequence of pairwise almost disjoint elements of For each being countable, it is easy to find a function satisfying the two conditions above with in place of

Now, given set where is least such that is infinite. It is now easy to check that is as wanted.

A variant of Lemma 6 gives us the following:

Lemma 11 (Galvin-Prikry)Given an infinite cardinal and a set there is an injective function such that and is a singleton for all and

*Proof:* It suffices to argue when and the general case is then handled as in the proof of Lemma 6.

Let be an injective enumeration of Note that for all One can easily find such that is injective, and is a singleton for all

We can then take

Corollary 12For all infinite cardinals and all sets there is a function such that for al

*Proof:* With as above, let satisfy for all and

We now proceed to show that one can `lift’ exponents and relax the requirements a bit, while still obtaining infinitary Jónsson algebras. We will repeatedly use the following lemma.

Lemma 13Let be an infinite cardinal and let and be sets, with Given there is a function such that for all

*Proof:* Use Lemma 6 to find an injective such that for all and

Choose injections for all

Now define so that for all and

*Proof:* Let witness

Define as follows: Given let By Lemma 13, we can then find such that for all But so in fact for all with

Now consider It follows that so witnesses

Recall that means that whenever there is some and

*Proof:* Clearly, implies

Suppose now that and let be a witness. We need to show that We may assume that and that by Corollary 7.

By Theorem 2 and Corollary 14, Let be a witness, and define by for all

Use Lemma 13 to find a function such that for all Hence the same holds for all and since for all such then It follows that witnesses

Corollary 16If then

*Proof:* For any any injective witnesses Take and apply Theorem 15.

*Proof:* Let witness and witness

Let be given by for all and find with for all such As before, we also have for all

But, for any such and therefore and it follows that witnesses

Galvin and Prikry point out that one could define a relation by iff and then Theorem 17 could be read as saying that is transitive.

Corollary 18If and then, in fact,

*Proof:* As mentioned in the proof of Corollary 14, one always has In particular, By transitivity,

*Proof:* We may of course assume and By Corollary 7, we may also assume that Clearly, By transitivity,

*Proof:* By Theorem 15 and Corollary 19, iff which implies or, equivalently,

The reverse implication is clear.

Definition 21 (Kunen)For an infinite cardinal, let be the statement that for all functions there is an infinite set such that

Kunen showed that implies that and that the assertion that holds for some is of large cardinal character, in the sense that it implies that for all there is an inner model with at least (order type) many measurable cardinals.

Corollary 22If and then holds.

*Proof:* By Corollaries 14 and 20, is equivalent to which implies which implies .

It is a question of and Hajnal whether can ever hold. As far as I know, this is still open (I would be glad to hear of any updates). On the other hand, the existence of some such that is consistent.

Theorem 23 (Kunen)If is a -supercompact cardinal, then

*Proof:* Fix an elementary with critical point such that and let

Let As in the proof of Corollary 9, Also, By elementarity, there is some such that

Theorem 24 (Galvin-Prikry)Let and be infinite cardinals, with singular. Suppose that for all Then also

*Proof:* Let and fix a strictly increasing sequence of cardinals cofinal in Let witness and for all let witness

Let be given by

for all Let be such that for all such We claim that witnesses

Let and Then there is some with There must then be some such that and some such that and it follows that This shows that and we are done.

** Bibliography **

Here are some references consulted while preparing this note:

- Fred Galvin, Karel Prikry,
*Borel sets and Ramsey’s theorem*, The Journal of Symbolic Logic,**38 (2)**(Jun., 1973), 193–198. - Fred Galvin, Karel Prikry,
*Infinitary Jonsson algebras and partition relations*, Algebra Universalis,**6**(1976), 367–376. - Akihiro Kanamori,
**The higher infinite**, Springer (1994). - Kenneth Kunen,
*Elementary embeddings and infinitary combinatorics*, The Journal of Symbolic Logic,**36 (3)**, (Sep., 1971), 407–413.

*Typeset using LaTeX2WP. Here is a printable version of this post.*

[…] I want to present some significant strengthenings of the results above. The results from last lecture exploit the fact that a great deal of coding can be carried out with infinitely many coordinates. […]

[…] are no embeddings All the known proofs of this result (see for example lectures II.10, II.12, and III.3) use the axiom of choice in an essential way. Theorem 27 (Sargsyan) In assume there is an […]

[…] I also want to give an update on the topics discussed in lecture III.3. […]