**1. Infinite exponents **

Last lecture we showed that for any Later, we will see that for any and any there is such that On the other hand (recall we are assuming choice), there are no nontrivial positive partition relations with infinite.

(To avoid vacuously true statements, we are always assuming implicitly that requires for at least one )

*Proof:* It is enough to show that In effect, if holds and we may assume that is regular, so any countable subset of is bounded, and the ordinal is still strictly below

For let denote the subset of consisting of its first many members.

Now, given let be the function If is homogeneous for and of size then is homogeneous for In effect, let so If then by homogeneity of

This shows that for infinite implies that there is some such that so it is enough to show that the latter never holds. In fact, we cannot even have (Recall our convention that denotes the order type and the size.)

For this, let be an arbitrary infinite cardinal, and let be a well-ordering of Define by iff is the -least member of and otherwise.

If is homogeneous for and is the -least member of then so is -homogeneous. Now consider any infinite sequence of infinite subsets of Since for all we must have that contradicting that is a well-order.

In the presence of the axiom of choice, Theorem 1 completely settles the question of what infinite exponent partition relations hold. Without choice, the situation is different.

For example, Mathias showed that is consistent and, in fact, holds in Solovay’s model. It follows that in the presence of large cardinals, or under determinacy, holds in Amusingly, it is still open whether suffices to obtain (not just in ) This seems related to the question of whether implies Woodin’s

Kleinberg and Seiferas studied the question of whether *well-ordered choice* suffices to prove Theorem 1. I believe the question is still open, but they showed that there is essentially only one instance that requires investigation, namely, whether Mathias’s partition relation is compatible with well-ordered choice. For the remainder of this lecture, we work without choice, and use the arrow notation in the sense of order types; unless otherwise stated, all variables denote ordinals. By a *cardinal* I mean an initial ordinal.

For an ordinal, let be the largest limit ordinal (or zero) not larger than and let be the unique natural number such that

Definition 2Let be an infinite cardinal.-well-ordered choice, is the statement that every -sequence of nonempty sets admits a choice function.

well-ordered choice, is

For a binary relation and an ordinal, an-chain of lengthis a function with domain such that whenever-dependent choice,is the statement that for every binary relation if every -chain of length less than can be extended to a longer -chain, then there is an -chain of length

It is easy to see that, for any implies which implies However, does not imply is strictly weaker than but implies Also, implies but no suffices.

**Homework 13 (Jensen)** *Show that implies *

Recall the following monotonicity properties of the arrow notation; the only one that may need arguing is the last one, that can be proved as in the opening paragraphs of the proof of Theorem 1.

Lemma 3Let and be cardinals, and and let and be ordinals such that Assume that

- If then
- If then
- If then
- If and then

Theorem 4 (Kleinberg-Seiferas)Assume and suppose that

- If or or then for all
- If and then iff there is some such that

By the proof of Theorem 1, it follows that plus the existence of a well-ordering of implies that no infinite exponent partition relations hold.

The main use of in the proof below is as follows: Assuming we can assign to each a set with We also define this way if In what follows, we will always assume such an assignment has taken place.

Given any and write for the -th element of in increasing order. Suppose Define as the least such that The following obvious remark will prove useful:

Lemma 5Assume Given any and any there is some with

We need another preliminary result; its proof will be given in another lecture; the notation is defined in the obvious way for an arbitrary set:

Theorem 6 (-Rado)For any set any ordinal and any nonzero there is some such that

The -Rado theorem was originally proved using choice. Proofs of the choiceless version above, that we need, have been rediscovered a few times. Apparently the first such proof is due to Keisler and Morley, from 1967. Kleinberg and Seiferas also provide a proof. Another proof (for finite) is due to Thomas Forster, from 2007.

We are now ready to begin the proof of Theorem 4.

*Proof:* The proof divides naturally in several cases.

*Suppose first that * By monotonicity, if then which implies that and therefore

Given denote by the two sets of order type with such that Define by iff

It is enough to show that for any there is some such that This shows that does not admit homogeneous sets of order type and therefore to begin with.

To see the claim, suppose so Let be such that and take Then The argument is similar if

*Suppose now that * By the previous case, we may assume that so By monotonicity, if then so and therefore

Define by iff for all where It is enough to show that does not admit homogeneous sets of order type For this, it suffices to show that given any there are with

Let Define so that is the least member of larger than for all and also larger than By construction,

As before, let be the subsets of of order type such that and Let be such that and define by Then as witnessed by

*Suppose that * As before, if then so and therefore

Define by Since for any there is some with it follows that does not admit infinite homogeneous sets, and we are done.

*Suppose that and * Now we prove that iff

*Suppose first that * By monotonicity, so and therefore

Towards a contradiction, suppose that and let be a witnessing coloring. Given let and set

Note that is infinite, so is defined. Now define a coloring by

It is enough to check that admits no infinite homogeneous sets. But this is clear, since given any any infinite subset of induces an infinite subset of with Since admits no infinite homogeneous sets, there is such that But then is not constant on

*Conversely, suppose that * Let be such that and We need to check that if then

First, notice that by an obvious induction. Second, note that Ramsey’s theorem for any holds; for example, the amount of choice used in the first proof given last lecture is which follows from by Homework 13.

We will show that which clearly suffices. For this, consider a coloring and let enumerate Use to produce a sequence where

- are infinite sets, and
- for all

To do this, assume is given, and set for Since we can find an infinite and an such that is -homogeneous for

Now define by By Ramsey’s theorem, there is an infinite set and an such that is -homogeneous for Let consist of the first elements of

Let be largest such that We claim that is -homogeneous. To see this, note that any -sized subset of is for some If then because since the are decreasing. But since This shows that is constantly equal to on

*Finally, suppose that and * We need to show that iff there is some such that

*First, suppose that * By monotonicity, so and therefore As shown above, this implies that

*Conversely, suppose that * Let and We need to show that there is some such that For this, we use the choiceless -Rado Theorem 6.

We claim that we can take such that To see this, consider a coloring For define by

There is a canonical bijection between and By it follows that we can associate to each a pair such that and is -homogeneous for By choice of we can find an and an such that is -homogeneous for the map

Let Then is homogeneous for since any has the form for some and so

**2. Partition cardinals **

By further restricting the amount of choice in the universe, it becomes possible that several of the infinite exponent relations shown inconsistent in the arguments above now hold. In fact, the study of infinite exponent relations under the axiom of determinacy has proved to be very fruitful, and a detailed theory has emerged. I illustrate this with a result of Kleinberg that shows that infinite exponents give rise to measurable cardinals. In what follows, whenever the elements of a linearly ordered set are displayed, as in it is understood that

Lemma 7Suppose that Then is a regular cardinal.

*Proof:* It is easy to check that must be a limit ordinal. Let be such that there is some with

Define by iff Let be a homogeneous subset of of order type Then since is unbounded.

Now define by Then is strictly increasing. Hence

*Proof:* It is easy to see that so is regular.

Let be given. Given let and denote the subsets of consisting, respectively, of its first elements and of its remaining Now define by iff

Let be homogeneous for of type Then in fact is -homogeneous. To see this, slice off into successive sets of order type Clearly, cannot be injective on since it only takes many values.

It follows that is also homogeneous for Because if we can find with and since we must have

Lemma 9If and then for any

*Proof:* We argue as above: Let be given, where is the set of functions from into and define by iff where are as before. Let be homogeneous for of order type and define as before. If is 0-homogeneous for then it is homogeneous for as before, and we are done.

Suppose towards a contradiction that is 1-homogeneous for so the map given by is 1-1.

By lemma 8 and an easy argument, Let be given by least such that Then we can find and that is -homogeneous for Then is a -sized subset of contradiction.

Theorem 10 (Kleinberg)Suppose that for some limit ordinal Then is measurable, and there is a normal ultrafilter over concentrating on ordinals of the same cofinality as

*Proof:* * is measurable.*

As before, is regular. First, we generalize the notion of -club and identify the ultrafilter that witnesses the measurability of

For a limit ordinal and let denote the set of all suprema of increasing -sequences of elements of Say that is **-closed** iff If is -closed and unbounded in say that is a **-club**. Clearly, for any the set is -club.

Let denote the collection of subsets of that contain a -club. Clearly, is nonempty, is closed under supersets, and does not contain the empty set.

We want to show that if then in fact is a -complete filter over To see this claim, suppose that and that is a sequence of members of Since we are not assuming we cannot automatically pick -clubs to conclude that which is again a -club. Instead, we use that

For and a limit ordinal, let denote the initial segment of of order type Let and be unbounded subsets of By an obvious back-and-forth construction, we can find and unbounded subsets of and respectively, such that for all limit ordinals

Define as follows: Given and let iff Let be homogeneous for of size Then in fact for all and

To see this, suppose that is such that for all Let be -club, and consider and as above. Then so contradicting that

Now let so is -club. It is enough to show that To see this, let so there is with Then for all so for all and the claim follows.

A similar argument shows that is in fact an ultrafilter. To see this, let be given. We use that and consider the partition given by iff If is homogeneous for of size then is -club, and either or depending on whether is -homogeneous or -homogeneous.

* is normal.*

First we show that Clearly, To see the other containment, it is enough to see that if is -club, then is -closed. Let and let be its increasing enumeration.

Let so Fix strictly increasing, continuous, and cofinal, and let such that

For let be the initial segment of such that Also, let have order type Then has order type and the same supremum as Thus,

Note that implies This is all we require below, so it follows that we may assume that is a regular cardinal.

To show that is normal, consider a function regressive on a -measure 1 set, and we need to argue that is constant on a -measure 1 set.

For this, fix a -club where is regressive, and let be given by iff Let be homogeneous for of size Given let Then and so Hence is -homogeneous.

Given any and any with let It follows that By -additivity of it follows that there is some such that

Definition 11Astrong partition cardinalis a cardinal such that

Aweak partition cardinalis a cardinal such that for all

In the presence of the existence of uncountable strong partition cardinals implies the existence of large cardinals Also, uncountable strong partition cardinals satisfy stronger partition relations than the one required by the definition. For example, one has:

Definition 12means that for any partition there is a set such that is constant on for all

Note that fails; for example, consider given by Also, as noted by and Rado, fails; for example, consider given by iff

Definition 13ARamsey cardinalis a cardinal such that

Theorem 14 (Henle)

- If is an uncountable cardinal, is a cardinal, and then In particular, an uncountable strong partition cardinal is both Ramsey and a weak partition cardinal.
- If then for all
- If then implies that the least such that admits a -complete nonprincipal ultrafilter. If holds, then (and therefore is measurable.) If holds, then the ultrafilter can be taken to be normal.
- If is uncountable and then

On the other hand, it is not the case that if then for arbitrary sets For example, holds under and therefore also However, and it follows that

To state the main result about partition cardinals, we need two additional large cardinal notions:

Definition 15Analgebraon is a structure of the form where for each there is an such that

A cardinal isJónssoniff every algebra on admits a proper subalgebra of size

For example, that is not Jónsson can be witnessed by letting if and setting and arbitrary for We will return to Jónsson cardinals next lecture.

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.

Definition 16Given ordinals say that iff for any there is an such that Similarly, by replacing with

Say that iff for any there is an such that Similarly by replacing with

If say that is-Rowbottomiff for any and say that isRowbottomiff it is -Rowbottom.

Theorem 17 (Kleinberg)Assume Let be an uncountable strong partition cardinal. Then there are cardinals such that:

- for all In particular, and are measurable.
- All the are singular Jónsson cardinals of cofinality and is a Rowbottom cardinal.

Theorem 18 (Kleinberg)In the situation of Theorem 17, assume moreover that there is a normal ultrafilter over such that has order type Then:

- for
- is a weak partition cardinal.
- Every normal ultrafilter over or is an as defined in the proof of Theorem 10.

It is in the context of that Kleinberg results have proved useful. In part, this may be accidental, in that we do not know any ways of obtaining partition cardinals other than via determinacy. On the other hand, Kechris and Woodin have shown that, in determinacy is equivalent to the existence of unboundedly many strong partition cardinals below so determinacy seems to be the natural setting for studying these cardinals.

As mentioned above,

holds under This is a theorem of Martin.

In one can make sense of ultrapowers of ordinals by -complete ultrafilters; this is not necessarily the case in general without any amount of choice, since one cannot prove ‘s theorem for the full ultrapower of so some care is required.

Theorem 19 (Martin)Assume If and is uncountable, then for any -complete ultrafilter over the image of under the induced ultrapower map, is a cardinal.

From Martin’s theorem 19 it follows that where is the -club ultrafilter over Hence from Theorems 17 and 18 it follows that

and that each is a Jónsson cardinal of cofinality and is Rowbottom.

Under a very detailed analysis of measures has been carried out by Steve Jackson and others, and so many cardinals with strong partition properties have been identified. Steel proved, for example, that in under every regular cardinal below is in fact measurable. Also, it follows from Jackson’s analysis that

are all strong partition cardinals and their successors are weak partition cardinals; here, exponentiation is ordinal exponentiation.

The precise result shown by Kleinberg is that if is a strong partition cardinal and is a normal ultrafilter over then we can define as in Theorem 17 by setting A careful analysis of measures under then allows us to study many cardinals above a given For example, the only regular cardinals under between and are for and the -club ultrafilter over These cardinals are precisely and

Theorem 20 (Jackson-Khafizov)Assume Suppose that

Let

where be the Cantor normal form of Then the following hold:

- If then
- If is a successor ordinal, then
- If is a limit ordinal, then

Löwe exploited Kleinberg’s result and the Jackson-Khafizov analysis thanks to the following “shifting lemma:”

Theorem 21 (Löwe)Assume Let and let be a -complete ultrafilter over Let Suppose that for all cardinals either is a successor of cofinality strictly larger than or else is a limit of cofinality strictly smaller than Then

For example, under if then there are only three normal ultrafilters over namely for It follows that the Kleinberg sequence associated to is:

- If then for
- If then for
- If then for

** Bibliography **

Here are some references consulted while preparing this note:

- James Henle,
*Some consequences of an infinite-exponent partition relation*, The Journal of Symbolic Logic,**42 (4)**, (Dec., 1977), 523–526. - Steve Jackson,
*Structural consequences of*, in**Handbook of set theory**, Matthew Foreman, Akihiro Kanamori, eds., to appear. - Akihiro Kanamori,
**The higher infinite**, Springer (1994). - Eugene Kleinberg,
*Strong partition properties for infinite cardinals*, The Journal of Symbolic Logic,**35 (3)**, (Sep., 1970), 410–428. - Eugene Kleinberg,
**Infinitary combinatorics and the axiom of determinateness**, Springer (1977). - Eugene Kleinberg and J. Seiferas,
*Infinite exponent partition relations and well-ordered choice*, The Journal of Symbolic Logic,**38 (2)**, (Jun., 1973), 299–308. - Benedikt Löwe,
*Kleinberg sequences and partition cardinals below*, Fundamenta Mathematicae,**171 (1)**, (2002), 69–76.

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

~~The homework problem should be numbered 13.~~Fixed.[…] again, assume choice throughout. Last lecture, we showed that for any The results below strengthen this fact in several ways. Definition 1 […]

~~And, implies in although it is not known whether implies I’ll fix this in the note soon.~~Done; thanks to Richard Ketchersid for clarifying the issue for me.[…] proof of Theorems 1 and 3 above require the axiom of choice. However, the proof of Theorem 4 in lecture III.2 requires a choiceless version. I now proceed to establish this version. Theorem 5 () For any set […]

Woodin has extended significantly the results about Jónsson cardinals mentioned in the context of namely, he has shown using the directed systems analysis of that (assuming determinacy) in every uncountable cardinal below is Jónsson. It is not clear whether the argument can be extended to strengthen the conclusion to say that every such cardinal is Rowbottom.

Steve Jackson has shown (from determinacy) that this is the case for all uncountable cardinals below

[…] from Definition 15 on lecture III.2 that a cardinal is Jónsson iff every algebra on admits a proper subalgebra of size Here, an […]

[…] of partition properties and the computation of ultrapowers of associated measures. See also here for extensions of this result, references, and some additional […]