The Galvin-Hajnal Formulas (Part I)

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 \kappa and \lambda be uncountable regular cardinals such that, for all \delta<\lambda, \delta^\kappa<\lambda. Assume further that \langle \kappa_\alpha : \alpha<\kappa\rangle is a sequence of cardinals such that for all \alpha<\kappa, \prod_{\beta<\alpha} \kappa_\beta<\aleph_\lambda. It then follows that \prod_{\alpha<\kappa} \kappa_\alpha <\aleph_\lambda.

We begin with a definition of the primary tool used in the proof of the above theorem.

Definition: Let \kappa be a regular cardinal. An almost disjoint transversal system (a.d.t.) for a sequence of sets \langle A_\alpha : \alpha<\kappa\rangle is a set F\subseteq \prod_{\alpha<\kappa} A_\alpha such that for each f\neq g\in F, |\{\alpha<\kappa : f(\alpha)=g(\alpha)\}|<\kappa.

The idea here is that almost disjoint transversal systems care about disjointness up to small subsets of \kappa. 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, \kappa will denote an uncountable regular cardinal.

Proposition: Let \langle \kappa_\alpha : \alpha<\kappa\rangle be a sequence of cardinals. If we set A=\langle A_\alpha : \alpha<\kappa\rangle where A_\alpha=\prod_{\beta<\alpha}\kappa_\beta, then there is an a.d.t. F for A with |F|=\prod_{\alpha<\kappa} \kappa_\alpha.

To see this, let \tau=\prod_{\alpha<\kappa} \kappa_\alpha, and let \langle g_\xi : \xi<\tau\rangle be a faithful enumeration of \prod_{\alpha<\kappa} \kappa_\alpha.  For each \xi<\tau and \alpha<\kappa, set f_\xi(\alpha)=g\upharpoonright \alpha. Since g\upharpoonright \alpha\in\prod_{\beta<\alpha} \kappa_\beta, we see that each f_\xi\in \prod_{\alpha<\kappa} A_\alpha. Furthermore, for \eta_o<\eta_1<\tau, we see that there is some ordinal \gamma<\kappa where g_{\eta_0}(\gamma)\neq g_{\eta_1}(\gamma), and thus for every \delta>\gamma we have that f_{\eta_0}(\delta)\neq f_{\eta_1}(\delta). So, it follows that F=\{f_\xi : \xi<\tau\} is an a.d.t. for A.

We now only need to show that, under the hypotheses of the theorem, the size of any given a.d.t. for A as in the above proposition will be small.

Lemma: Let \lambda and \kappa be uncountable regular cardinals such that for all \delta<\lambda, \delta^\kappa<\lambda. Suppose that A=\langle A_\alpha : \alpha<\kappa\rangle is such that |A_\alpha|<\aleph_\lambda for all \alpha<\kappa. If F is an a.d.t. for A, then |F|<\aleph_\lambda.

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 A=\langle A_\alpha : \alpha<\kappa\rangle where A_\alpha=\prod_{\beta<\alpha}\kappa_\beta. By the proposition, let F be an ad.t. for A with |F|=\prod_{\alpha<\kappa}\kappa_\alpha. Since |A_\alpha|<\aleph_\lambda for each \alpha<\kappa by assumption, it follows from the lemma that |F|<\aleph_\lambda.

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 A=\langle A_\alpha : \alpha<\kappa\rangle and B=\langle B_\alpha : \alpha<\kappa\rangle are such that |A_\alpha|=|B_\alpha| for each \alpha<\kappa, then there exists an a.d.t. of size \tau for A if and only if there exists an a.d.t. of size \tau for B. 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 I be some ideal on \kappa, and let R be a relation on \kappa. We say that two functions f,g\in{}^\kappa ON are R-related modulo I if and only if the set of values where f and g are not related is in the ideal. Intuitively, ideals are collections of small subsets of \kappa, and so two functions are related modulo I if the set of values where they fail to be related is small. More formally,

f R_I g\iff \{\alpha<\kappa : \neg(f(\alpha)R g(\alpha))\}\in I.

Now, let J denote the ideal of bounded subsets of \kappa, and consider the usual ordering < on \kappa. In this case, we see that since \kappa is uncountable, J is closed under countable unions. So, <_J is a well-founded partial order on {}^\kappa ON. Now for a function \phi\in {}^\kappa ON, set

T(\phi)=\sup\{|F| : F is an a.d.t. for \phi\}.

For such a function, let \aleph \circ \phi denote the composition of \phi with the \aleph function. That is, \aleph \circ \phi (\alpha)=\aleph_{\phi(\alpha)}. In order to prove the lemma, it will suffice to show that \forall\phi\in{}^\kappa \lambda, T(\aleph\circ \phi)<\aleph_\lambda by our earlier remark. Assume otherwise, i.e. that there is some \phi\in{}^\kappa\lambda such that T(\aleph\circ\phi)\geq\aleph_\lambda. We may assume that \phi is that <_J-least element of {}^\kappa\lambda since any a.d.t. only cares up to a bounded set (and since <_J is well-founded). In particular, T(\aleph\circ\psi)<\aleph_\lambda for each \psi<_J \phi.

Intuitively then, given a function \psi\in{}^\kappa\lambda with T(\aleph\circ\phi)\geq\aleph_\lambda, the collection of \alpha<\kappa where \psi(\alpha) is strictly less than \phi(\alpha). Additionally, it seems natural that \phi should not take on the value 0 terribly often. With this in mind, we can use the function \phi to define an ideal I on \kappa as follows.

X\in I \iff there is some \psi\in{}^\kappa \lambda such that T(\aleph\circ\psi)\geq\aleph_\lambda, and for all \alpha\in X, \psi(\alpha)<\phi(\alpha), or \psi(\alpha)=0.

Of course, we need to actually check that I is an ideal on \kappa.

Claim: I is a \kappa-complete ideal on \kappa extending J, the ideal of bounded subsets of \kappa.

We begin by noting that \phi itself witness that \emptyset\in I. Furthermore, if X\in I, and \psi witnesses this, then \psi witnesses that every Y\subseteq X is in I as well. To see that I extends J, let X\subseteq \kappa be such that |X|<\kappa. Now define \psi\in{}^\kappa\lambda by \psi(\alpha)=0 if \alpha\in X, set \psi(\alpha)=\phi(\alpha) for \alpha\notin X. Since any a.d.t. F for \psi depends only on the co-bounded subsets of \kappa, it follows that T(\aleph\circ \psi) from the fact that \phi=_I\psi.

Now we simply need to show that I is closed under unions of length <\kappa. Let \delta<\kappa, and let \langle X_\mu : \mu<\delta\rangle be a sequence of elements of I, and for each \mu<\delta, let \psi_\mu witness that X_\mu\in I. Define a function \psi\in{}^\kappa\lambda by \psi(\alpha)=min_{\mu<\delta}\psi_\mu(\alpha). We claim that \psi witnesses X=\bigcup_{\mu<\delta}X_\mu\in I. Next, we partition \kappa=\bigcup_{\mu<\delta}S_\mu so that for every \alpha\in S_\mu, \psi(\alpha)=\psi_{\mu}(\alpha). Of course, some of these sets S_\mu may be empty, and it may be the case that there are multiple indices for which \psi_mu(\alpha) is minimal. The point is that we have a partition of \kappa so that we can use almost disjoint transversal systems for the functions \psi_\mu to piece together an a.d.t. for \psi of the appropriate size. With that said, for each \mu<\delta, let F_\mu=\{f^\mu_\xi : \xi<\tau\} be an a.d.t. for \aleph\circ \psi_\mu. For each \mu<\delta, define

f_\xi=\bigcup_{\mu<\delta} f^\mu_\xi\upharpoonright S_\mu.

Since the sets S_\mu are disjoint, and are such that \psi_\mu=\psi on S_\mu, we see that each f_\xi\in\prod \psi. Next, we claim that F=\{f_\xi : \xi<\tau\} is an a.d.t. for \psi. To see this, let \eta_0<\eta_1<\tau, and note that

|\{\alpha<\kappa : f_{\eta_0}(\alpha)=f_{\eta_1}(\alpha)|=|\bigcup_{\mu<\delta}\{\alpha\in S_\mu : f^\mu_{\eta_0}(\alpha)=f^\mu_{\eta_1}(\alpha)\}|<\kappa

by the regularity of \kappa. Thus, it follows that T(\aleph\circ\psi)\geq min_{\mu<\delta} T(\aleph\circ \psi_\mu)\geq \aleph_\lambda, and so \psi witnesses that X\in I, and so I is \kappa-complete.

Earlier, I noted that set where \phi takes on the value 0 should be small, and in fact it turns out that this is a bounded subset of \kappa. To see this, simply note that otherwise, elements of \prod_{\alpha<\kappa} \aleph_{\phi(\alpha)} would take on finite values \kappa-many times. But then, we would have that T(\aleph\circ \phi)\leq \aleph_0^\kappa<\lambda\leq\aleph_\lambda, and thus \phi(\alpha) is 0 on a bounded subset of \kappa. Using this argument, we can refine the above claim a little bit. Using this, we can easily show that I is a proper ideal, for suppose otherwise and let \psi witness that \kappa\in I. Then, for all \alpha<\kappa, either \psi(\alpha)<\phi(\alpha) or \psi(\alpha)=0. But, we have just shown that any function \psi\in{}^\kappa\lambda for which T(\aleph\circ\psi)\geq\aleph_\lambda can only take on the value of 0 on a bounded subset of \kappa. Thus, |\{\alpha<\kappa : \psi(\alpha)\geq \phi(\alpha)\}|<\kappa, contradicting that <_J-minimality of \phi.

To summarize, we have shown that I is a \kappa-complete proper ideal extending J.

Now we define a partition of \kappa=X_0\cup X_1\cup X_2 as follows.

  1. X_0 is the collection of all \alpha<\kappa such that \phi(\alpha)=0.
  2. X_1 is the collection of all \alpha<\kappa such that \phi(\alpha) is a non-zero limit ordinal.
  3. X_2 is the collection of all \alpha<\kappa such that \phi(\alpha) is a successor ordinal.

We have already shown that X_0\in I, since X_0\in J.

Claim: X_1\in I. Since \lambda is regular, it follows that \phi is not cofinal in \lambda, and thus there is some ordinal \rho<\lambda such that \phi(\alpha)\leq\rho for each \alpha<\kappa. Let

Q=\{\psi\in{}^\kappa \lambda : \psi(\alpha)<\phi(\alpha) for all \alpha\in X_1, and \psi(\alpha)=\phi(\alpha) for each \alpha\notin X_1\}.

Note that |Q|\leq |{}^\kappa \rho|<\lambda by assumption. Since T(\aleph\circ \phi)\geq \aleph_\lambda, it follows that for each ordinal \mu<\lambda, there is some  a.d.t. F_\mu for \aleph\circ \phi with |F_\mu|>\aleph_\mu.

For \mu<\lambda, and \psi\in Q, set F^\psi_\mu= F_\mu \cap \prod_{\alpha<\kappa}\aleph_{\psi(\alpha)}. Note that F^\psi_\mu is an a.d.t. for \aleph\circ\psi since F_\mu is an a.d.t., and every element of F^\psi_\mu is an element of \prod_{\alpha<\kappa} \aleph_{\psi(\alpha)}. Next, since \phi(\alpha) is a limit ordinal for each \alpha\in X_1, we see that F_\mu=\bigcup_{\psi\in Q}F^\psi_\mu since outside of X_1, \psi(\alpha) is the same for each \psi\in Q. Hence, for |Q|\leq \mu <\lambda, there is some \psi_\mu\in Q such that |F^{\psi_\mu}_\mu|>\aleph_\mu. Since \lambda is regular, there is some \psi\in Q such that |\{ \mu<\lambda : \psi_\mu=\psi\}|=\lambda. But then, T(\aleph\circ \psi)>\aleph_\mu for each \mu<\lambda, and so T(\aleph\circ\psi)\geq\aleph_\lambda. Thus, \psi witnesses that X_2\in I.

Since I is a proper ideal, it follows that X_2\notin I. We will use this to derive the desired contradiction.

For X\in\mathcal{P}(X_2), define the function \psi_X\in {}^\kappa\lambda by setting \psi_{X}(\alpha)+1=\phi(\alpha) for \alpha\in X, and \psi_X(\alpha)=\phi(\alpha) if \alpha\notin X. Note that since for every \alpha\in X_2, \phi(\alpha) is a successor ordinal, we can use this to make sure each \psi_X is distinct in a uniform way. By assumption, for X\in\mathcal{P}(X_2) with X\notin I, there is some \rho(X)<\lambda such that T(\aleph\circ \psi_X)\leq \aleph_{\rho(X)}. Since there are at most 2^\kappa many such sets X, we can fix some \rho<\lambda with 2^\kappa<\aleph_{\rho} and such that \rho(X)<\rho for each X\in\mathcal{P}(X_2)\setminus I. Next, fix an a.d.t. F for \aleph\circ \phi with |F|>\aleph_{\rho +1}.

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 \aleph_\omega^{\aleph_0}<max\{\aleph_{\omega_4},2^{\aleph_0}\} 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 f\in F and X\in\mathcal{P}(X_2)\setminus I, let H_X(f)=\{g\in F : (\forall \alpha\in X)(g(\alpha)<f(\alpha))\}. By definition, the elements of H_X(f) are almost disjoint, and in fact H_X(f) is an a.d.t. for \langle A_\alpha : \alpha<\kappa\rangle where A_\alpha=f(\alpha) for \alpha\in X, and A_\alpha=\aleph_{\phi(\alpha)} otherwise. Now, for each \alpha<\kappa, we see that |A_\alpha|\leq\aleph_{\psi_X(\alpha)}. So by our earlier remark, there is an a.d.t. G for \aleph\circ \psi_X such that |G|=|H_X(f)|. Thus, we have the following chain of inequalities:

|H_X(f)|= |G|\leq T(\aleph\circ \psi_X)\leq\aleph_{\rho(X)}\leq \aleph_\rho.

Now let H(f)=\bigcup\{H_X(f) : X\in\mathcal{P}(X_2)\setminus I\}. Then, |H_X(f)|\leq 2^\kappa\cdot \aleph_\rho=\aleph_\rho. That is, |H(f)|\leq \aleph_\rho for each f\in F whereas |F|>\aleph_{\rho +1}. Now fix G\subseteq F with |G|=\aleph_{\rho+1}. So, we have that |F|>\aleph_{\rho+1}, |G|=\aleph_{\rho+1}, and for each f\in F, |H(f)|\leq \aleph_\rho. Thus it follows that |(F\setminus G)\setminus \bigcup_{g\in G}H(g)|>\aleph_\rho+1. With that said, fix some f_0\in (F\setminus G)\setminus(\bigcup_{g\in G} H(g)). Furthermore, we can find some let g_0\in G\setminus H(f_0). SoWe then have that f_0,g_0\in F by definition with f_0\neq g_0, and so X_2^0=\{\alpha<\kappa : f_0(\alpha)=g_0(\alpha)\}\in I. Furthermore, we have that f_0\notin H(g_0) and g_0\notin H(f_0), and so X_2^1=\{\alpha<\kappa : f_0(\alpha)<g_0(\alpha)\}\in I and X_2^2=\{\alpha<\kappa : g_0(\alpha)<f_0(\alpha)\}\in I. But, X_2=X_2^0\cup X_2^1\cup X_2^2 which are all in I, and thus X_2\in I, 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s