Now that I’m on winter break, I decided to work through the proofs of the Galvin-Hajnal formulas again. Many of the methods that are foundational to modern cardinal arithmetic can be found in these proofs, and working through will hopefully shed light on the motivation for some of the more basic the machinery used in pcf theory.
My plan is to work through, and follow fairly closely Galvin and Hajnal’s paper “Inequalities for Cardinal Powers”. This will certainly take multiple entries, though I’m not sure as to how many. The plan is to work through the proof of the first Galvin-Hajnal formula in this post, and maybe do short follow up on the corollaries mentioned in the first section of the paper. The corollaries are instructive in how one moves from results about cardinalities of products to cardinalities of powers of singulars. So, there is reason to work through that material as well.
Theorem (The First Galvin-Hajnal Formula): Let and be uncountable regular cardinals such that, for all , . Assume further that is a sequence of cardinals such that for all , . It then follows that .
We begin with a definition of the primary tool used in the proof of the above theorem.
Definition: Let be a regular cardinal. An almost disjoint transversal system (a.d.t.) for a sequence of sets is a set such that for each , .
The idea here is that almost disjoint transversal systems care about disjointness up to small subsets of . So, we throw out uninteresting manners in which functions can fail to be disjoint, and this should give us a way of approximating the size of products of cardinals. From here on out, will denote an uncountable regular cardinal.
Proposition: Let be a sequence of cardinals. If we set where , then there is an a.d.t. for with .
To see this, let , and let be a faithful enumeration of . For each and , set . Since , we see that each . Furthermore, for , we see that there is some ordinal where , and thus for every we have that . So, it follows that is an a.d.t. for .
We now only need to show that, under the hypotheses of the theorem, the size of any given a.d.t. for as in the above proposition will be small.
Lemma: Let and be uncountable regular cardinals such that for all , . Suppose that is such that for all . If is an a.d.t. for , then .
From this lemma, and the above proposition, the proof of the theorem is fairly immediate.
Proof of Theorem: Assume the hypotheses of the theorem, and set where . By the proposition, let be an ad.t. for with . Since for each by assumption, it follows from the lemma that .
As one can probably guess, the proof of the lemma requires a bit of work. We begin by noting that the size of an a.d.t. really only cares about the size of the sets involved, and is insensitive to any other structure that the sets themselves may carry. That is, if and are such that for each , then there exists an a.d.t. of size for if and only if there exists an a.d.t. of size for . So instead of looking at arbitrary sets, we can pay attention to canonical objects of a given size, i.e. cardinals. This is a trivial, but extremely useful reduction that occurs quite often when working with infinitary combinatorics.
One thread that is quite basic to modern cardinal arithmetic is looking at the structure of products modulo some ideal. In particular, let be some ideal on , and let be a relation on . We say that two functions are -related modulo if and only if the set of values where and are not related is in the ideal. Intuitively, ideals are collections of small subsets of , and so two functions are related modulo if the set of values where they fail to be related is small. More formally,
Now, let denote the ideal of bounded subsets of , and consider the usual ordering on . In this case, we see that since is uncountable, is closed under countable unions. So, is a well-founded partial order on . Now for a function , set
is an a.d.t. for .
For such a function, let denote the composition of with the function. That is, . In order to prove the lemma, it will suffice to show that , by our earlier remark. Assume otherwise, i.e. that there is some such that . We may assume that is that -least element of since any a.d.t. only cares up to a bounded set (and since is well-founded). In particular, for each .
Intuitively then, given a function with , the collection of where is strictly less than . Additionally, it seems natural that should not take on the value terribly often. With this in mind, we can use the function to define an ideal on as follows.
there is some such that , and for all , , or .
Of course, we need to actually check that is an ideal on .
Claim: is a -complete ideal on extending , the ideal of bounded subsets of .
We begin by noting that itself witness that . Furthermore, if , and witnesses this, then witnesses that every is in as well. To see that extends , let be such that . Now define by if , set for . Since any a.d.t. for depends only on the co-bounded subsets of , it follows that from the fact that .
Now we simply need to show that is closed under unions of length . Let , and let be a sequence of elements of , and for each , let witness that . Define a function by . We claim that witnesses . Next, we partition so that for every , . Of course, some of these sets may be empty, and it may be the case that there are multiple indices for which is minimal. The point is that we have a partition of so that we can use almost disjoint transversal systems for the functions to piece together an a.d.t. for of the appropriate size. With that said, for each , let be an a.d.t. for . For each , define
Since the sets are disjoint, and are such that on , we see that each . Next, we claim that is an a.d.t. for . To see this, let , and note that
by the regularity of . Thus, it follows that , and so witnesses that , and so is -complete.
Earlier, I noted that set where takes on the value should be small, and in fact it turns out that this is a bounded subset of . To see this, simply note that otherwise, elements of would take on finite values -many times. But then, we would have that , and thus is on a bounded subset of . Using this argument, we can refine the above claim a little bit. Using this, we can easily show that is a proper ideal, for suppose otherwise and let witness that . Then, for all , either or . But, we have just shown that any function for which can only take on the value of on a bounded subset of . Thus, , contradicting that -minimality of .
To summarize, we have shown that is a -complete proper ideal extending .
Now we define a partition of as follows.
- is the collection of all such that .
- is the collection of all such that is a non-zero limit ordinal.
- is the collection of all such that is a successor ordinal.
We have already shown that , since .
Claim: . Since is regular, it follows that is not cofinal in , and thus there is some ordinal such that for each . Let
for all , and for each .
Note that by assumption. Since , it follows that for each ordinal , there is some a.d.t. for with .
For , and , set . Note that is an a.d.t. for since is an a.d.t., and every element of is an element of . Next, since is a limit ordinal for each , we see that since outside of , is the same for each . Hence, for , there is some such that . Since is regular, there is some such that . But then, for each , and so . Thus, witnesses that .
Since is a proper ideal, it follows that . We will use this to derive the desired contradiction.
For , define the function by setting for , and if . Note that since for every , is a successor ordinal, we can use this to make sure each is distinct in a uniform way. By assumption, for with , there is some such that . Since there are at most many such sets , we can fix some with and such that for each . Next, fix an a.d.t. for with .
The idea here is that we are creating enough room to derive a contradiction. The same idea is used when proving Shelah’s famous result that which is where the four comes from (in a sense). Of course, the machinery utilized in the proof is much more complex than the machinery that we’re employing here, but the core idea of “creating enough room” is still there.
Getting back to the proof at hand, for and , let . By definition, the elements of are almost disjoint, and in fact is an a.d.t. for where for , and otherwise. Now, for each , we see that . So by our earlier remark, there is an a.d.t. for such that . Thus, we have the following chain of inequalities:
Now let . Then, . That is, for each whereas . Now fix with . So, we have that , , and for each , . Thus it follows that . With that said, fix some . Furthermore, we can find some let . SoWe then have that by definition with , and so . Furthermore, we have that and , and so and . But, which are all in , and thus , which is a contradiction.
One nice thing I really enjoy about above proof is that we see an absurd amount of appeals to the relatively elementary, but absurdly useful pigeonhole principle. Anyway, I plan on going through the corollaries to the theorem that appear in the first section of “Inequalities for Cardinal Powers”. After that, I’m hopefully going to do an entry on the proof of the second formula followed its corollaries.