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 2 Let 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 length is 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 3 Let and be cardinals, and and let and be ordinals such that Assume that
- If then
- If then
- If then
- If and then
- 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 5 Assume 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:
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 7 Suppose 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 9 If 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.
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.
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 11 A strong partition cardinal is a cardinal such that
A weak partition cardinal is 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 12 means 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 13 A Ramsey cardinal is 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 15 An algebra on is a structure of the form where for each there is an such that
A cardinal is Jónsson iff 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 16 Given 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 -Rowbottom iff for any and say that is Rowbottom iff it is -Rowbottom.
- 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:
- 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.
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
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
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.