# 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} 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). 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) and $X_2^2=\{\alpha<\kappa : g_0(\alpha). 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.