Covering numbers and pcf theory

Introduction

This paper develops an idea appearing as part of a proof from [7] with the intent of providing a general technique for deriving bounds on covering numbers from pcf-theoretic information. The relationship between these two types of data is a major theme of pcf theory: for example, the proof of Shelah’s famous $\aleph_{\omega_4}$ theorem involves showing that the cofinality of the structure $([\aleph_\omega]^{\aleph_0}, \subseteq)$ is equal to $\max\operatorname{pcf}\{\aleph_n : n < \omega\}$, with subsequent pcf analysis proving that this cardinal is less than $\aleph_{\omega_4}$.

The covering problems under consideration all ask how large a family of small subsets of $\lambda$ must be in order to cover all subsets of a prescribed size in a certain way. Shelah has introduced notation for handling some of this complexity, and we recall it now:

As usual, for a set $X$ and a cardinal $\tau$, we write $[X]^{<\tau}$ and $[X]^{\leq\tau}$ for the subsets of $X$ of cardinality less than, or at most, $\tau$. The four parameters all play roles here, as we are asking how many sets from $[\lambda]^{<\kappa}$ it takes so that any member of $[\lambda]^{<\theta}$ is contained in some union of fewer than $\sigma$ of them. There are also some familiar instances of this definition, for example, $\operatorname{cov}(\lambda,\kappa^+,\kappa^+,2)$ is just the cardinal $\operatorname{cf}([\lambda]^\kappa,\subseteq)$. Another common setting is $\operatorname{cov}(\lambda,\kappa^+,\theta^+,\sigma)$ with $\theta\le\kappa< \lambda$. With this configuration, the sets from our covering family are allowed to have cardinality at most $\kappa$, and the requirement is that every set of cardinality at most $\theta$ can be covered using fewer than $\sigma$ of them.

There is an easy reason to expect a connection between these covering numbers and products of regular cardinals. Let us define

as our notation for the set of regular cardinals in the interval $(\kappa,\lambda]$. Suppose $X \in[\lambda]^{\leq\kappa}$ and $A \subseteq R(\kappa,\lambda]$. We write $\prod A$ for the set of functions $f$ with domain $A$ such that $f(a) < a$ for every $a \in A$. Since $|X| \leq\kappa< a$ and $a$ is regular, the function

belongs to $\prod A$. Moreover, if $\gamma\in X \cap a$, then $\gamma< h_X(a)$. Covering a set of ordinals by a few small sets therefore gives bounds for those ordinals in the corresponding coordinates of a product. The main task is to go in the other direction and use bounds in products to construct coverings, and this paper exploits one natural way of doing this.

We recall the pcf notation needed to make this correspondence precise. Our conventions mostly follow [1] and [6]. For more obscure material, we keep close to [8] and note that the analytical guide [10] gives a useful account of the relevant parts of the book and later developments. The surveys [2, 5] provide other introductions to pcf theory.

A set $A$ of regular cardinals is progressive if

For a proper ideal $J$ on $A$, we write $J^{+}$ for the collection of $J$-positive subsets of $A$, and use the usual ordering modulo $J$:

Similarly, $f <_J g$ means that $\{a \in A : f(a) \geq g(a)\} \in J$. The ideal specifies which sets of coordinates may be ignored when comparing functions. If there is a regular cardinal $\tau$ and a $<_J$-increasing cofinal sequence

in $\prod A/J$, then the true cofinality of the product is $\tau$, written

Such a sequence is called a scale modulo $J$.

For progressive $A$, $\operatorname{pcf}(A)$ is the set of possible cofinalities of ultraproducts of $A$. For a cardinal $\tau$, the ideal

consists of those subsets whose possible cofinalities are all less than $\tau$. The following standard facts about pcf generators are the ones we will use; see [8] and § 5 of [10].

If $J$ is a proper ideal on $A$ with $J_{<\tau}[A] \subseteq J$ and $B_\tau[A] \notin J$, then

Conversely, if $\tau=\operatorname{tcf}(\prod A/J)$, then $\tau\in\operatorname{pcf}(A)$, $J_{<\tau}[A]\subseteq J$, and $B_\tau[A]\notin J$.

Here $J_{<\tau}[A]+B_\tau[A]$ is the ideal generated by $J_{<\tau}[A]$ together with $B_\tau[A]$. More generally, $J_{<\tau}[A]$ is generated by the sets $B_\rho[A]$ for $\rho\in\operatorname{pcf}(A)\cap\tau$. Consequently, given any proper ideal $J$ on $A$, we may choose the least $\tau$ for which $B_\tau[A]\notin J$ and obtain true cofinality $\tau$ by restricting to that generator. Taking $\tau=\Lambda$ also gives the familiar equality $\operatorname{cf}(\prod A,\le)=\max\operatorname{pcf}(A)$. We fix a generating sequence for each progressive set under consideration.

For the covering problems we have in mind, we are going to need to consider several variations of the idea of cofinality in a product of cardinals. The following pins down one such notion of cofinality, in a context that will allow us to talk about Shelah’s previous work.

Definition 1.3. Let $\sigma=\operatorname{cf}(\sigma)<\theta$ be infinite cardinals, and let $A$ be a set of regular cardinals.

1. A family $\mathcal{F}\subseteq\prod A$ is $\Gamma(\theta,\sigma)$-cofinal in $\prod A$ if, whenever $B\in[A]^{<\theta}$ and $g\in\prod B$, there is a family $\mathcal{F}_0\in[\mathcal{F}]^{<\sigma}$ such that for every $b\in B$ there is an $f\in\mathcal{F}_0$ with $g(b)<f(b)$. The minimum cardinality of such a family is denoted by $\operatorname{cf}_{\Gamma(\theta,\sigma)}(\prod A)$.

2. If $A$ is progressive, then $\operatorname{pcf}_{\Gamma(\theta,\sigma)}(A)$ is the set of all cardinals of the form $\operatorname{tcf}(\prod B/J)$, where $B\in[A]^{<\theta}$, $J$ is a proper $\sigma$-complete ideal on $B$, and the true cofinality exists.

The family $\mathcal{F}_0$ may depend on both $B$ and $g$, and different members of $\mathcal{F}_0$ may provide the bound at different coordinates. The first parameter of $\Gamma(\theta,\sigma)$ controls the size of $B$, and the second controls the size of $\mathcal{F}_0$. The $\sigma$-completeness condition on the ideals gives the corresponding restriction on the quotient side: a union of fewer than $\sigma$ exceptional sets still belongs to the ideal. Lemma 3.1 shows that the minimum size of a $\Gamma(\theta,\sigma)$-cofinal family is exactly $\sup\operatorname{pcf}_{\Gamma(\theta,\sigma)}(A)$ when $A$ is progressive.

We can now express the elementary connection with coverings more precisely. If $\mathcal{P}$ witnesses $\operatorname{cov}(\lambda,\kappa^+,\theta^+,\sigma)$ and $A\subseteq\mathop{\mathrm{R}}(\kappa,\lambda]$, then $\{h_X:X\in\mathcal{P}\}$ is $\Gamma(\theta^+,\sigma)$-cofinal in $\prod A$. To see this, take $B\in[A]^{\le\theta}$ and $g\in\prod B$, and cover the range of $g$ by fewer than $\sigma$ members of $\mathcal{P}$. For every $b\in B$, one of these sets $X$ contains $g(b)$, and hence $g(b)<h_X(b)$.

To describe the same information in terms of singular cardinals, we use pseudopowers. These collect true cofinalities of products of regular cardinals approaching a fixed singular cardinal, with restrictions on the size of the product and the completeness of the ideal.

Definition 1.4. Let $\nu$ be singular and suppose $\sigma=\operatorname{cf}(\sigma)\le\operatorname{cf}(\nu)<\theta$. Then $\operatorname{pp}_{\Gamma(\theta,\sigma)}(\nu)$ is the supremum of all cardinals of the form $\operatorname{tcf}(\prod B/J)$, where $B\subseteq\nu\cap\operatorname{Reg}$ is cofinal in $\nu$, $|B|<\theta$, and $J$ is a proper $\sigma$-complete ideal on $B$ containing every bounded subset of $B$. We write $J^{\mathrm{bd}}[B]$ for the ideal of bounded subsets of $B$.

The requirement $J^{\mathrm{bd}}[B]\subseteq J$ ensures that discarding a bounded initial segment of $B$ does not change the true cofinality. The restriction $\sigma\le\operatorname{cf}(\nu)$ is necessary: otherwise, $B$ would be the union of fewer than $\sigma$ bounded sets, and no proper $\sigma$-complete ideal on $B$ could contain all of them.

The state of the art for these covering numbers is Shelah’s cov vs. pp theorem (Theorem 5.4 of Chapter II of [8]), which we state here in the configuration of parameters used in this paper.

Further results concerning the theorem appear in [9]. Our prior work in the area gave a second proof of Shelah’s cov vs. pp theorem in [3], and further developed the theory of representation to establish a combinatorial principle we called the Pseudopower Dichotomy in [4]. The work in this paper should be viewed as a continuation of this project. We show that our techniques quickly imply the cov vs. pp theorem, and then we deploy them to obtain some new results.

Section 2 develops the partition refinement machinery used throughout the paper, including the elementary closure observation. In Section 3 we apply this machinery to give a new and direct proof of Shelah’s cov vs. pp theorem, together with four characterizations of the covering number. Section 4 develops a corresponding theorem for normal ideals and diagonal coverings, and Section 5 treats coverings modulo an arbitrary $\sigma$-complete ideal. In all of these settings, we will obtain the same four types of characterizations of the cardinal under consideration.

Coverings from partitions

In this section we develop the general technique that underlies our results. The two main ingredients are Lemma 2.4, which turns suitable trees of refinements into coverings, and Lemma 2.7, which uses bounds in products of regular cardinals to supply the required refinements. We finish with an elementary closure construction that controls the size of the family of partition sequences.

If $\bar{d}$ refines $\bar{c}$, then $g^{\bar{d}}(\beta) \subseteq g^{\bar{c}}(\beta)$ for every $\beta< \theta$. We will use cofinal families in products of regular cardinals to shrink cells whose cardinality exceeds $\kappa$. The next definition identifies the regular cardinals involved.

The idea is to start with a function $g:\theta\to\lambda$ and some $(\kappa,\theta)$-partition sequence for $\lambda$, and do successive refinements of a certain form. Our refining process treats the three classes of cells discussed above in different ways, and it is our pcf assumptions that allow us to deal sensibly with the large cells. We iterate our refinement process through countably many stages: since cell cardinalities cannot decrease indefinitely, suitable refinements eventually place the relevant values of $g$ in small cells.

When we refine a partition sequence, we want to make sure that in each column the resulting partition has at most $\kappa$ cells, but we also want to make sure that we are breaking cells up into smaller pieces where possible. The small cells already have the required size for the type of covering we seek and are left alone. The medium cells can be partitioned into at most $\kappa$ sets of smaller cardinality because of our cofinality assumptions, so we can break them apart accordingly.

For a large cell, we need to do something smarter as we cannot just break it into pieces of smaller cardinality: this would result in a partition with more than $\kappa$ cells. Instead, we will use a function in a product to tell us how we carve off a suitable smaller set. To see how this works, note that the large cells determine a natural set of regular cardinals: for a partition sequence $\bar{c}$, define

Then $A^{\bar{c}}\subseteq\mathrm{R}(\kappa,\lambda]$ and $|A^{\bar{c}}|\leq\kappa$, so $A^{\bar{c}}$ is a progressive set of regular cardinals whenever it is nonempty, and we can use our pcf assumptions applied to $\prod A^{\bar{c}}$. (Be warned that in the future we will omit the superscript $\bar{c}$ when the partition sequence is fixed.) With this goal in mind, the following definition makes sense.

• for every $\beta< \theta$, if $g^{\bar{c}}(\beta)$ is not small in $\bar{c}$, then there is a $\zeta< \zeta^*$ such that $|g^{\bar{c}^{\zeta}}(\beta)| < |g^{\bar{c}}(\beta)|$.

Already we can see that this is useful! Suppose the singleton collection $\{\bar{c}_{n+1}\}$ reduces $g$ over $\bar{c}_n$ for every $n < \omega$. If $C_n$ is the union of the small cells of $\bar{c}_n$, then $\bigcup_{n<\omega} C_n$ covers the range of $g$. Otherwise, for some $\beta< \theta$, the sequence $\langle|g^{\bar{c}_n}(\beta)| : n < \omega\rangle$ would be strictly decreasing. Different refinements may shrink the cells containing different values of $g$, so the next lemma extends this argument to one organized along a tree. We will use this lemma repeatedly: it supplies the mechanism for building covering families from partition sequences.

Proof. Suppose that $g^{\bar{c}^{s}}(\beta)$ is not small for any $s \in T$. By hypothesis, every $s \in T$ has an immediate successor $t \in T$ satisfying

Starting from the root, we may recursively choose an infinite branch $\langle s_n : n < \omega\rangle$ through $T$ such that

for each $n < \omega$. This gives a strictly decreasing sequence of cardinals, a contradiction. $\square$

Our next move is to develop a way of producing partition sequences that satisfy the assumptions of the preceding lemma. To accomplish this goal, we fix for each $X \subseteq\lambda$ of cardinality greater than $\kappa$ a filtration $\langle X[\varepsilon] : \varepsilon< \operatorname{cf}(|X|)\rangle$ such that

• the sequence $\langle X[\varepsilon] : \varepsilon< \operatorname{cf}(|X|)\rangle$ is increasing and continuous with union $X$, and

• $|X[\varepsilon]| < |X|$ for each $\varepsilon$.

We do not need to make any special assumptions about these filtrations; all that matters is that we fix the assignment

as a parameter. Each filtration induces a partition of $X$ by assigning every $\delta\in X$ to the least $\varepsilon$ such that $\delta\in X[\varepsilon]$.

• If $(\alpha,\beta)$ is large in $\bar{c}$, then $X_{\alpha\beta}$ is split into the two sets

and

There are at most $\kappa$ resulting cells in each column. We fix reindexings by ordinals below $\kappa$, so that $\bar{c} \downarrow h$ is again a $(\kappa,\theta)$-partition sequence and refines $\bar{c}$. In particular,

for every $\beta< \theta$. Every medium cell is split into cells of smaller cardinality. To obtain a smaller cell containing $g(\beta)$ when $X_{\alpha\beta}$ is large, it suffices for $h(\kappa_{\alpha\beta})$ to exceed the least $\epsilon$ such that $g(\beta) \in X_{\alpha\beta}[\epsilon]$. The next definition packages these requirements into a single function.

The function $\hat{g}$ is well-defined. For a fixed $\eta\in A$, at most one cell in each column contains $g(\beta)$, so there are at most $\theta$ relevant filtration stages. Since $\eta$ is regular and $\theta\leq\kappa< \eta$, those stages are bounded below $\eta$. Moreover, $\hat{g}$ is zero except possibly on a set of at most $\theta$ cardinals of the form $\operatorname{cf}(|g(\beta)|)$. Our next lemma shows us how to translate bounds on $\hat{g}$ into the shrinking refinements needed to apply Lemma 2.4.

We finish with an elementary closure observation that will be used without further comment in the later proofs.

In each of the following sections, we will supply the refining families and use the resulting closed family of partition sequences to obtain the required covering.

Characterizing covering numbers

We now combine the partition machinery of § 2 with pcf theory to prove Shelah’s cov vs. pp theorem and characterize the covering number in terms of small products, pseudopowers, and the full product $\prod R(\kappa,\lambda]$. Our proof bypasses the Skolem hulls and characteristic functions used by previous proofs of this theorem.

We start with a reformulation of Claim 3.2 of Chapter IX of [8]. This lemma translates the local product cofinalities needed below into statements about standard pcf theory. Analogous local characterizations will be used in later sections, and all will have similar proofs grounded in the pcf theory of products of progressive sets of cardinals. Note that this lemma also applies when $\sigma=\aleph_0$, although other parts of our proof will require the uncountability assumption.

Since $A \setminus B \in K$, this is equivalently a representation over $B$, and therefore $\tau\in\operatorname{pcf}_{\Gamma(\theta,\sigma)}(A)$. Extend $g$ to $\widetilde{g} \in\prod A$. Applying pointwise cofinality to $\widetilde{g}+1$, choose $f \in\mathcal{F}_{\tau}$ such that $\widetilde{g}(a)<f(a)$ for every $a \in B_{\tau}[A]$. Then

a contradiction. □

The next corollary applies Lemma 2.7 to $\Gamma(\theta^{+},\sigma)$-cofinal families.

Proof. Fix $g:\theta\to\lambda$, and let

Since $|B| \leq\theta$, apply $\Gamma(\theta^{+},\sigma)$-cofinality to $\widehat{g}\mathbin{\upharpoonright}B$ to obtain $\mathcal{H}_0 \in[\mathcal{H}]^{<\sigma}$. If this family is empty, enlarge it by one member of $\mathcal{H}$. At each coordinate where the selected cell is not small, Lemma 2.7 gives a shrinking refinement: any member of $\mathcal{H}_0$ works for a medium cell, and cofinality supplies a suitable member for a large cell. Thus $\{\bar{c}\mathbin{\downarrow}h:h \in\mathcal{H}_0\}$ reduces $g$ over $\bar{c}$. □

The next proposition applies Lemma 2.4 to ordinary coverings.

Proof. For each $\bar{c} \in\mathcal{S}$, let $C^{\bar{c}}$ be the union of its small cells, and set

Then $\mathcal{P} \subseteq[\lambda]^{\leq\kappa}$ and $|\mathcal{P}| \leq|\mathcal{S}|$.

Fix $g:\theta\to\lambda$. Starting with any member of $\mathcal{S}$ at the root, recursively construct a tree $T \subseteq{}^{<\omega}\sigma$ and label its nodes by partition sequences $\bar{c}^{s} \in\mathcal{S}$. At a node $s$, choose a family $\mathcal{S}_s \in[\mathcal{S}]^{<\sigma}$ that reduces $g$ over $\bar{c}^{s}$, and label the immediate successors of $s$ by the members of $\mathcal{S}_s$. The assigned partition sequences refine along branches, and the shrinking hypothesis of Lemma 2.4 holds at every coordinate $\beta< \theta$.

Each node has fewer than $\sigma$ immediate successors. Regularity of $\sigma$ implies that every level of $T$ has cardinality less than $\sigma$, and uncountability of $\sigma$ then gives $|T| < \sigma$. Applying Lemma 2.4 at each coordinate, we obtain

Thus, fewer than $\sigma$ members of $\mathcal{P}$ cover the range of $g$. Every set in $[\lambda]^{\leq\theta}$ is contained in the range of some such function, so $\mathcal{P}$ witnesses the desired inequality. □

The next theorem is our treatment of Shelah’s cov vs. pp theorem. We have limited ourselves to a particular configuration of the parameters, but the full theorem (as presented in Chapter II of [8]) can be derived from the following result fairly easily. Our proof gives the added equivalences of (2) and (4), showing that under our hypotheses, the same phenomenon registers in four different contexts,

Proof. Let $R=R(\kappa,\lambda]$, and let $\mu_i$ denote the cardinal in item $(i)$. We prove

To prove $\mu_1\le\mu_2$, note that singleton sets $A$ give $\lambda=\sup R\le\mu_2$.¹ For each $(\kappa,\theta)$-partition sequence $\bar{c}$ of $\lambda$ with $A^{\bar{c}}\ne\varnothing$, Lemma 3.1 gives a nonempty $\Gamma(\theta^{+},\sigma)$-cofinal family

of cardinality at most $\mu_2$. If $A^{\bar{c}}=\varnothing$, take $\mathcal{H}_{\bar{c}}=\{\varnothing\}$.

Next, we choose a family $S$ of partition sequences of cardinality at most $\mu_2$, containing the trivial partition sequence and closed under the operation $\bar{c}\mapsto\bar{c}\downarrow h$ for $h\in\mathcal{H}_{\bar{c}}$.

Given a partition sequence $\bar{c}\in S$ and function $g:\theta\to\lambda$, we can apply Corollary 3.2 and conclude there is a family $\mathcal{H}_0\subseteq\mathcal{H}_{\bar{c}}$ of cardinality less than $\sigma$ such that the collection $\{\bar{c}\downarrow h:h\in\mathcal{H}_0\}$ reduces $g$ over $\bar{c}$. Every member of this family belongs to $S$ by closure. Thus $S$ satisfies the hypothesis of Proposition 3.3, and consequently

To prove $\mu_2\le\mu_3$, we use a standard argument from pcf-theory that we will spell out carefully for the benefit of the reader. Consider a representation $\tau=\operatorname{tcf}(\prod B/J)$ contributing to $\mu_2$, where $B\subseteq R$, $|B|\le\theta$, and $J$ is a proper $\sigma$-complete ideal on $B$. If $\tau\le\lambda$, then $\tau\le\mu_3$. Assume, therefore, that $\tau>\lambda$. It follows that $J$ must contain every singleton from $B$, and $B\cap\lambda$ must be $J$-positive (even in the dual filter!). We can let $\nu\le\lambda$ be the least ordinal such that $C:=B\cap\nu$ is $J$-positive. Since $J$ must contain singletons $\nu$ cannot be a successor ordinal. By minimality, $C$ is cofinal in $\nu$, and every bounded subset of $C$ belongs to $J\mathbin{\upharpoonright}C$. Since $C$ consists of cardinals and $\nu$ is a limit ordinal, $\nu$ is a limit cardinal. Also, $C$ is nonempty and its members are greater than $\kappa$, so $\kappa<\nu$.

If $\operatorname{cf}(\nu)<\sigma$, then $C$ would be the union of fewer than $\sigma$ bounded sets, contrary to the $\sigma$-completeness and properness of $J\mathbin{\upharpoonright}C$. Consequently,

so $\nu$ is singular. Restricting a scale for $\prod B/J$ to the $J$-positive set $C$ preserves both strict increase and cofinality, and therefore

Thus, $\tau$ contributes to $\operatorname{pp}_{\Gamma(\theta^{+},\sigma)}(\nu)$, and hence $\tau\le\mu_3$. Taking suprema gives $\mu_2\le\mu_3$.

The inequality $\mu_3 \le\mu_4$ is also very easy. Let $\mathcal{F} \subseteq\prod R$ be $\Gamma(\theta^+,\sigma)$-cofinal in $\prod R$ of cardinality $\mu_4$. Singleton coordinates give

Now suppose $\kappa< \nu\le\lambda$ with $\sigma\le\operatorname{cf}(\nu) \le\theta$, and let

contribute to $\operatorname{pp}_{\Gamma(\theta^+,\sigma)}(\nu)$. Discarding the bounded initial segment $B \cap(\kappa+1)$ preserves true cofinality, so we may assume $B \subseteq R$ and clearly our choice of $B$ guarantees $|B| \le\theta$.

If $\mu_4 < \tau$, the restrictions of the members of $\mathcal{F}$ to $B$ have a common upper bound $g \in\prod B$ modulo $J$. By $\Gamma(\theta^+,\sigma)$-cofinality, there is an $\mathcal{F}_0 \in[\mathcal{F}]^{<\sigma}$ such that

Each comparison set belongs to $J$, contradicting the $\sigma$-completeness and properness of $J$. Thus every such $\tau$ is at most $\mu_4$, and hence $\mu_3 \le\mu_4$.

To prove $\mu_4 \le\mu_1$, let $\mathcal{P} \subseteq[\lambda]^{\le\kappa}$ witness $\mu_1$. For each $X \in\mathcal{P}$ define

for $\rho\in R$. Since $|X| \le\kappa< \rho$, we have $f_X(\rho) < \rho$. We claim that

is $\Gamma(\theta^+,\sigma)$-cofinal. Indeed, suppose

and $g \in\prod B$. The range of $g$ has cardinality at most $\theta$, so there is a family $\mathcal{P}_0 \in[\mathcal{P}]^{<\sigma}$ covering it. For each $\rho\in B$, choose $X \in\mathcal{P}_0$ with $g(\rho) \in X$; then

Thus, $\mu_4 \le\mu_1$, and all four cardinals are therefore equal. □

Coverings and normal ideals

We now consider the corresponding covering problem for normal ideals. In this setting the role of a union of fewer than $\sigma$ sets in the preceding section will be taken by a diagonal union. Recall that if $\kappa$ is an uncountable regular cardinal and $\langle X_i : i < \kappa\rangle$ is a sequence of subsets of $\kappa$, its diagonal union is

An ideal on $\kappa$ is normal if it contains the bounded subsets of $\kappa$ and is closed under diagonal unions.

Some of the definitions in this section trace back to Section 4 of Chapter VIII of [8] and the first part of [7]. There, Shelah is concerned with a more abstract covering property he calls prc, but here we restrict our attention to the concrete case of measuring cofinality modulo normal ideals. We develop the material locally in two steps: first for sequences of regular cardinals and normal ideals on $\kappa$, and then for progressive sets of regular cardinals without a fixed enumeration.

Diagonally cofinal families in $\prod\bar{\kappa}$ are precisely those collections of functions that remain unbounded modulo any normal ideal on $\kappa$:

Proof. Suppose first that $\mathcal{F}$ is diagonally cofinal, and let $J$ be a proper normal ideal on $\kappa$. To see that $\mathcal{F}$ is unbounded modulo $J$, fix $h\in\prod\bar{\kappa}$. Choose a sequence $\langle f_\alpha:\alpha<\kappa\rangle$ from $\mathcal{F}$ and a club $C\subseteq\kappa$ such that

For each $\alpha<\kappa$, let

Then

If every $X_\alpha$ belonged to $J$, normality would imply that the diagonal union on the right belonged to $J$. This is impossible, since a proper normal ideal contains every nonstationary set and hence no club. Thus, $X_\alpha$ is $J$-positive for some $\alpha<\kappa$, so $f_\alpha\not\le_J h$. Since $h$ was arbitrary, $\mathcal{F}$ is unbounded in $\prod\bar{\kappa}/J$.

Conversely, suppose $\mathcal{F}$ is not diagonally cofinal. Fix $h\in\prod\bar{\kappa}$ witnessing this, so that for every sequence $\langle f_\alpha:\alpha<\kappa\rangle$ from $\mathcal{F}$, the set

is stationary. For each $f\in\mathcal{F}$, define

and let $J$ be the normal ideal generated by $\mathrm{NS}_\kappa$ together with the sets $X_f$ for $f\in\mathcal{F}$.

We claim that $J$ is proper. Otherwise, there would be a sequence $\langle f_\alpha:\alpha<\kappa\rangle$ from $\mathcal{F}$ and a nonstationary set $N\subseteq\kappa$ such that

Choose a club $C\subseteq\kappa$ disjoint from $N$. Then for every $\delta\in C$ there is an $\alpha<\delta$ such that

contradicting the choice of $h$. Therefore, $J$ is a proper normal ideal. But $X_f\in J$ for every $f\in\mathcal{F}$, so $f\le_J h$ for every $f\in\mathcal{F}$. Thus, $\mathcal{F}$ is bounded in $\prod\bar{\kappa}/J$, completing the proof. □

Now we can make the natural definition associated with diagonally cofinal subsets of $\prod\bar{\kappa}$. The following is equivalent to that given as Definition 4.4 on page 343 of [8], and better captures a sense of what is being measured.

Definition 4.3. Suppose $\kappa$ and $\bar{\kappa}$ are as above. Then $\operatorname{nor\text{-}cf}(\prod\bar{\kappa})$ is the minimum cardinality of a diagonally cofinal subset of $\prod\bar{\kappa}$.

In general, $\operatorname{nor\text{-}cf}(\prod\bar{\kappa})$ is going to depend on the enumeration $\bar{\kappa}$, although it will be unchanged if the sequence is modified only on a nonstationary set. We can, however, still characterize it in terms of the pcf structure of the product $\prod_{i<\kappa}\kappa_i$.

Definition 4.4. Let $\bar{\kappa}=\langle\kappa_i:i<\kappa\rangle$ be a progressive sequence of regular cardinals, and let $\langle B_\tau[\bar{\kappa}]:\tau\in\operatorname{pcf}(\bar{\kappa})\rangle$ be a generating sequence.²

1. If $I$ is an ideal on $\kappa$, let $\operatorname{Ncl}(I)$ denote the normal ideal generated by $I$. Thus, $X\in\operatorname{Ncl}(I)$ if and only if there are a nonstationary set $N\subseteq\kappa$ and a sequence $\langle X_\alpha:\alpha<\kappa\rangle$ from $I$ such that

2. Finally, define $\operatorname{pcf}_{\operatorname{nor}}(\bar{\kappa})=\{\tau\in\operatorname{pcf}(\bar{\kappa}):B_\tau[\bar{\kappa}]\notin\operatorname{Ncl}(J_{<\tau}[\bar{\kappa}])\}$.

Before moving on, we note that standard pcf arguments tell us that the definition of $\operatorname{pcf}_{\operatorname{nor}}$ we give above yields exactly the set of true cofinalities obtained from $\prod\bar{\kappa}$ modulo proper normal ideals on $\kappa$. Indeed, if

for such an ideal $J$, then the generator theorem gives $J_{<\tau}[\bar{\kappa}]\subseteq J$ and $B_\tau[\bar{\kappa}]\notin J$. Since $J$ is normal, it contains $\operatorname{Ncl}(J_{<\tau}[\bar{\kappa}])$, and hence $\tau\in\operatorname{pcf}_{\operatorname{nor}}(\bar{\kappa})$.

Conversely, suppose $\tau\in\operatorname{pcf}_{\operatorname{nor}}(\bar{\kappa})$, and set

Define an ideal $J$ on $\kappa$ by

Then $J$ is a proper normal ideal extending $J_{<\tau}[\bar{\kappa}]$ and containing $\kappa\setminus B_\tau[\bar{\kappa}]$. The generator theorem gives

With this observation, we are now in a position to characterize $\operatorname{nor\text{-}cf}(\prod\bar{\kappa})$.

For the reverse inequality, choose for each $\tau\in\operatorname{pcf}_{\mathrm{nor}}(\bar{\kappa})$ a family $\mathcal{F}_{\tau} \subseteq\prod\bar{\kappa}$ of cardinality $\tau$ whose restrictions to $B_{\tau}[\bar{\kappa}]$ are pointwise cofinal in $\prod_{i \in B_{\tau}[\bar{\kappa}]} \kappa_i$. Set

There are at most $\mu$ cardinals in $\operatorname{pcf}_{\mathrm{nor}}(\bar{\kappa})$, and each $\mathcal{F}_{\tau}$ has cardinality at most $\mu$, so $|\mathcal{F}| \leq\mu$.

By Proposition 4.2, it suffices to show that $\mathcal{F}$ is unbounded modulo every proper normal ideal on $\kappa$. Fix such an ideal $J$, let $h$ be a function in $\prod\bar{\kappa}$, and let $\tau$ be least such that $B_{\tau}[\bar{\kappa}] \notin J$.

By the minimality of $\tau$, $J_{<\tau}[\bar{\kappa}] \subseteq J$, so normality gives

and therefore $\tau\in\operatorname{pcf}_{\mathrm{nor}}(\bar{\kappa})$. Applying pointwise cofinality to $h+1$, choose $f \in\mathcal{F}_{\tau}$ with $h(i)<f(i)$ for every $i \in B_{\tau}[\bar{\kappa}]$. The set $\{i<\kappa:h(i)<f(i)\}$ is therefore $J$-positive and we are done. □

We next modify these concepts to remove dependence on a particular enumeration. The following does the trick, and the natural characterization follows by arguments similar to what we saw above.

Moving on to pseudopowers, we arrive at a notion that has been studied in several contexts by Shelah.

We would like to use the above pcf-theoretic information as part of a cov vs. pp theorem that focuses on normal ideals. In order for that to work, we need to think about what sort of covering number might correspond to $\operatorname{pcf}_{\mathrm{nor}}$ and $\operatorname{pp}_{\mathrm{nor}}$, and we are led to the following definition:

We are now in a position to state and prove an analogue of Theorem 1 tailored to normal ideals. The following theorem is a relative of Lemma 1.1 of [7], where Shelah characterizes a cardinal he calls $\operatorname{prc}_{J}$. The argument given there is quite sketchy, but it does provide the seed of the idea we are developing in this paper.

Proof. Let $R=R(\kappa,\lambda]$, and let $\mu_i$ denote the cardinal in item $(i)$. We prove

To prove $\mu_1\leq\mu_2$, first note that constant sequences give $\rho\in\operatorname{pcf}_{\operatorname{nor}}(\{\rho\})$ for every $\rho\in R$, and hence

For each $(\kappa,\kappa)$-partition sequence $\vec{c}$ of $\lambda$ with $A^{\vec{c}}\neq\varnothing$, use Lemma 4.7 to choose a normally $\kappa$-cofinal family $\mathcal{F}_{\vec{c}}\subseteq\prod A^{\vec{c}}$ of cardinality at most $\mu_2$. If $A^{\vec{c}}=\varnothing$, set $\mathcal{F}_{\vec{c}}=\{\varnothing\}$. Choose a family $\mathcal{S}$ of cardinality at most $\mu_2$ containing the trivial partition sequence and closed under $\vec{c}\mapsto\vec{c}\mathbin{\downarrow}f$ for $f\in\mathcal{F}_{\vec{c}}$.

Let $C^{\vec{c}}$ be the union of the small cells of $\vec{c}$, and put

Then $|\mathcal{P}|\leq\mu_2$. We show that $\mathcal{P}$ is diagonally cofinal. Fix $g:\kappa\to\lambda$. Starting with the trivial partition sequence at the root, construct partition sequences $\vec{c}^{\,s}\in\mathcal{S}$ for $s\in{}^{<\omega}\kappa$. At a node $s$, set $A^s=A^{\vec{c}^{\,s}}$. If $A^s$ is nonempty, let $g^s\in\prod A^s$ be the function from Definition 2.6. Set $\eta^s_\beta=\operatorname{cf}(|g^s(\beta)|)$ when this cell is large, and $\eta^s_\beta=\min(A^s)$ otherwise. Normal $\kappa$-cofinality of $\mathcal{F}_{\vec{c}^{\,s}}$ gives a sequence $\langle f^s_\xi:\xi<\kappa\rangle$ from this family and a club $D_s\subseteq\kappa$ such that

If $A^s$ is empty, let every $f^s_\xi$ be the empty function and put $D_s=\kappa$. In either case, set

These successors belong to $\mathcal{S}$ and refine $\vec{c}^{\,s}$. Put $Y^s=C^{\vec{c}^{\,s}}\cup\kappa\in\mathcal{P}$.

Fix a bijection $\pi:{}^{<\omega}\kappa\to\kappa$, and choose a club $E\subseteq\kappa$ of nonzero limit ordinals such that

for every $\delta\in E$. Then

is club. Set $Y_{\zeta}=Y^{\pi^{-1}(\zeta)}$. If $\delta\in D$ and $s \in{}^{<\omega}\delta$, then $\pi(s)<\delta$ and $\delta\in D_s$.

Fix $\delta\in D$ and consider the tree $T={}^{<\omega}\delta$. At a node $s\in T$, if $g^{\bar{\varepsilon}}(\delta)$ is medium, choose any $\xi<\delta$. If it is large, $\delta\in D_s$ gives a $\xi<\delta$ such that $\widehat{g}^{\bar{\varepsilon}}(\eta_s^{\delta})<f_s^{\xi}(\eta_s^{\delta})$. In either case, Lemma 2.7 shows that the chosen successor shrinks the cell containing $g(\delta)$. Applying Lemma 2.4 at coordinate $\delta$, we obtain

Thus $\mathcal{P}$ is diagonally cofinal and $\mu_1\leq\mu_2$.

To prove $\mu_2\leq\mu_3$, consider a representation

contributing to $\mu_2$, where each $\rho_i\in R$ and $J$ is a proper normal ideal on $\kappa$. For each $\rho\in R$, the fiber $\{i<\kappa:\rho_i=\rho\}$ belongs to $J$: otherwise, restricting the scale to that fiber would give $\tau=\rho\leq\lambda$. Consequently, there is a least $\nu\leq\lambda$ such that

Minimality implies that $\nu$ is a limit cardinal greater than $\kappa$, that $\{\rho_i:i\in S\}$ is cofinal in $\nu$, and that

for every $\alpha<\nu$. Since $J$ is $\kappa$-complete and the range on $S$ has cardinality at most $\kappa$, we have $\operatorname{cf}(\nu)=\kappa$.

The ideal

is proper and normal, and restricting the scale to $S$ preserves true cofinality $\tau$. Replace each $\rho_i$ for $i\notin S$ by a fixed member of $\{\rho_i:i\in S\}$. The resulting sequence, together with $J_S$, witnesses $\tau\leq\operatorname{pp}_{\mathrm{nor}}(\nu)\leq\mu_3$. True cofinalities at most $\lambda$ are already bounded by $\mu_3$, so taking suprema gives $\mu_2\leq\mu_3$.

To prove $\mu_3\leq\mu_4$, let $\mathcal{F}\subseteq\prod R$ witness $\mu_4$. Constant maps give $\lambda\leq\mu_4$. If $\tau=\operatorname{tcf}(\prod\bar{\nu}/J)$ contributes to $\operatorname{pp}_{\mathrm{nor}}(\nu)$ for $\kappa<\nu\leq\lambda$ with $\operatorname{cf}(\nu)=\kappa$, then $\bar{\nu}:\kappa\to R$. The pullback of $\mathcal{F}$ along $\bar{\nu}$ is diagonally cofinal and hence unbounded modulo $J$ by Proposition 4.2. A family of cardinality less than $\tau$ is bounded modulo $J$, so $\tau\leq|\mathcal{F}|=\mu_4$. Taking suprema gives $\mu_3\leq\mu_4$.

To prove $\mu_4\leq\mu_1$, let $\mathcal{P}\subseteq[\lambda]^\kappa$ witness $\mu_1$. For $X\in\mathcal{P}$ and $\rho\in R$, define

Since $|X|=\kappa<\rho=\operatorname{cf}(\rho)$, we have $f_X\in\prod R$. Put $\mathcal{F}=\{f_X:X\in\mathcal{P}\}$. Given $\bar{\eta}:\kappa\to R$ and $h\in\prod\bar{\eta}$, diagonal cofinality of $\mathcal{P}$ gives a sequence $\langle X_\alpha:\alpha<\kappa\rangle$ from $\mathcal{P}$ and a club $C\subseteq\kappa$ such that

For each $\delta\in C$, some $\alpha<\delta$ therefore satisfies

Thus $\mathcal{F}$ is normally $\kappa$-cofinal and $\mu_4 \leq|\mathcal{F}| \leq\mu_1$, completing the cycle. $\square$

Coverings modulo an ideal

Suppose $\theta\leq\kappa< \lambda$ and $I$ is a proper ideal on $\theta$. For our final example, we now ask how many sets from $[\lambda]^{\leq\kappa}$ are needed so that, for every $g:\theta\to\lambda$, fewer than $\sigma$ of them cover $g(\beta)$ for $I$-almost every $\beta< \theta$. Our partition method gives a complete answer whenever $\aleph_0 < \sigma= \operatorname{cf}(\sigma) \leq\theta$ and $I$ is $\sigma$-complete. In particular, the case $\sigma= \aleph_1$ allows countably many covering sets and requires only countable completeness of $I$. The following definitions describe the corresponding pcf information.

The sequence $\bar{\eta}$ need not be one-to-one. In Rudin–Keisler terminology, the images of $I$ are exactly the ideals $J \leq_{\mathrm{RK}} I$.

We allow extensions because the construction must sometimes restrict attention to an $I$-positive set of coordinates. If $X \in I^{+}$, then

is a proper ideal extending $I$, and it is $\sigma$-complete whenever $I$ is $\sigma$-complete. The image of $I_X$ under a sequence $\bar{\eta}$ extends the image of $I$ under the same sequence. This is the localization used in the covering argument below.

If $J$ is a proper ideal on $A$, we say that $F \subseteq\prod A$ is $<\sigma$-cofinal in $\prod A/J$ if for every $g \in\prod A$ there is an $F_0 \in[F]^{<\sigma}$ such that

(2) $\operatorname{cf}_{\Gamma(I,\sigma)}\left(\prod A\right)$.

Proof. The proof is a routine modification of that of Lemma 3.1. The class of proper $\sigma$-complete ideals extending an image of $I$ is closed under proper $\sigma$-complete extensions, so the ideals constructed in that argument remain admissible. $\square$

As in Section 3, we will also characterize the covering number using pseudopowers. Here the representing ideals must extend an image of $I$.

Definition 5.5. Let $I$ be a proper ideal on $\theta$, let $\sigma$ be an infinite regular cardinal, and let $\nu$ be singular with $\sigma\le\operatorname{cf}(\nu) \le\theta< \nu$. Then $\operatorname{pp}_{\Gamma(I,\sigma)}(\nu)$ is the supremum of all cardinals of the form $\operatorname{tcf}(\prod A/J)$, where $A \subseteq\nu\cap\operatorname{Reg}$ is cofinal in $\nu$, $|A| \le\theta< \min(A)$, and $J$ is a proper $\sigma$-complete ideal on $A$ extending an image of $I$ and containing every bounded subset of $A$.

Proof. Let $R = \operatorname{R}(\kappa,\lambda]$, and let $\mu_i$ denote the cardinal in item $(i)$. We prove

To prove $\mu_1 \le\mu_2$, note that for each $\rho\in R$ the constant map $\theta\to\{\rho\}$ sends $I$ to the ideal $\{\varnothing\}$ on $\{\rho\}$. Thus $\rho\in\operatorname{pcf}_{\Gamma(I,\sigma)}(\{\rho\})$, and

For each $(\kappa,\theta)$-partition sequence $\vec{c}$ of $\lambda$ with $A^{\vec{c}} \ne\varnothing$, Lemma 5.4 gives a $\Gamma(I,\sigma)$-cofinal family $\mathcal{H}_{\vec{c}} \subseteq\prod A^{\vec{c}}$ of cardinality at most $\mu_2$. Adjoin the zero function to each such family, and take $\mathcal{H}_{\vec{c}} = \{\varnothing\}$ when $A^{\vec{c}} = \varnothing$. Choose a family $\mathcal{S}$ of cardinality at most $\mu_2$ containing the trivial partition sequence and closed under these refinements.

Let $\mathcal{C}^{\vec{c}}$ be the union of the small cells of $\vec{c}$, and put

We show that $\mathcal{C}$ witnesses $\mu_1 \le\mu_2$.

Fix $g:\theta\to\lambda$. Starting with the trivial partition sequence at the root, construct a $<\sigma$-branching tree $T \subseteq{}^{<\omega}\sigma$ whose nodes carry partition sequences $\vec{c}^{\,s} \in\mathcal{S}$ and exceptional sets $E_s \in I$. At a node $s$, set $A_s = A^{\vec{c}^{\,s}}$, $C^s = \mathcal{C}^{\vec{c}^{\,s}}$, and

If $X_s \in I$, let $\mathcal{H}^s$ consist of the zero function on $A^s$, including the empty function when $A^s$ is empty, and put $E_s = X_s$. If $X_s \in I^+$, then $A^s$ is nonempty. Set $\eta^s_\beta=\operatorname{cf}(\lvert g^{\bar{s}}(\beta)\rvert)$ for $\beta\in X_s$ and $\eta^s_\beta=\min(A^s)$ otherwise. Define an ideal $J_s$ on $A^s$ by

This is the image under $\bar{\eta}^s$ of the proper $\sigma$-complete ideal $I_{X_s}$, so it is proper and $\sigma$-complete and extends the image of $I$ under $\bar{\eta}^s$. Let $\hat{g}^s \in\prod A^s$ be the function from Definition 2.6. Choose a nonempty $H^s \in[H_{\bar{c}^s}]^{<\sigma}$ such that

and put

In either case, enumerate $H^s$ as $\langle h_i^s : i < \delta_s\rangle$, where $0 < \delta_s < \sigma$, and set

for $i < \delta_s$. Closure ensures that these successors belong to $S$. If $\beta\notin E_s$ and the cell containing $g(\beta)$ is large, the definition of $E_s$ gives an $h \in H^s$ with $\hat{g}^s(\eta^s_\beta) < h(\eta^s_\beta)$. For a medium cell, any member of $H^s$ is suitable. Lemma 2.7 therefore shows that whenever $\beta\notin E_s$ and the cell containing $g(\beta)$ is not small, some successor decreases its cardinality.

Since $\sigma$ is uncountable and regular, $\lvert T\rvert< \sigma$. The $\sigma$-completeness of $I$ therefore gives

For each $\beta\notin E$, the shrinking hypothesis holds at every node of $T$. Applying Lemma 2.4 at coordinate $\beta$, we obtain

Each $C^s$ belongs to $C$, and $\lvert T\rvert< \sigma$, so $C$ has the required covering property. Hence $\mu_1 \le\lvert C\rvert\le\mu_2$.

For the pseudopower comparisons, note that if $J$ extends an image of $I$ and $B \in J^+$, then $J \mathbin{\upharpoonright} B$ also extends an image of $I$. Indeed, let $\langle\eta_\beta: \beta< \theta\rangle$ witness the image condition, choose $b \in B$, and set $\eta'_\beta=\eta_\beta$ when $\eta_\beta\in B$ and $\eta'_\beta=b$ otherwise. For $C \subseteq B$, if $\{\beta< \theta: \eta'_\beta\in C\} \in I$, then $\{\beta< \theta: \eta_\beta\in C\} \in I$, and hence $C \in J \mathbin{\upharpoonright} B$.

To prove $\mu_2 \le\mu_3$, let $\tau=\operatorname{tcf}(\prod A/J)>\lambda$ contribute to $\mu_2$, and let $\bar{\eta}=\langle\eta_\beta: \beta< \theta\rangle$ witness that $J$ extends an image of $I$. The complement of $\operatorname{ran}(\bar{\eta})$ belongs to $J$. Restricting to this range therefore preserves true cofinality, and we may assume $\lvert A\rvert\le\theta$. As in § 3, every singleton belongs to $J$, and we choose the least $\nu\le\lambda$ for which $B=A\cap\nu$ is $J$-positive. The same argument gives

and $J \mathbin{\upharpoonright} B$ contains every bounded subset of $B$. It also extends an image of $I$, so restricting the scale to $B$ shows that $\tau$ contributes to $\operatorname{pp}_{\Gamma(I,\sigma)}(\nu)$. True cofinalities at most $\lambda$ are already bounded by $\mu_3$, and hence $\mu_2 \le\mu_3$.

To prove $\mu_3 \le\mu_4$, let $F \subseteq\prod R$ witness $\mu_4$. Constant maps give $\lambda\le\mu_4$. Consider a representation

contributing to $\operatorname{pp}_{\Gamma(I,\sigma)}(\nu)$, where $\kappa< \nu\le\lambda$ and $\sigma\le\operatorname{cf}(\nu) \le\theta$. Restricting to $B \setminus(\kappa+ 1)$ preserves true cofinality and the image condition, so we may assume $B \subseteq R$. Extend $J$ to an ideal $\widehat{J}$ on $R$ by

Then $\widehat{J}$ is proper and $\sigma$-complete, extends an image of $I$, and satisfies

If $|F| < \tau$, its members have a common upper bound modulo $\widehat{J}$. The $<\sigma$-cofinality of $F$ then contradicts the $\sigma$-completeness and properness of $\widehat{J}$. Thus $\tau\le|F| = \mu_4$, and taking suprema gives $\mu_3 \le\mu_4$.

To prove $\mu_4 \le\mu_1$, let $\mathcal{C}$ witness $\mu_1$. For each $X \in\mathcal{C}$, define

for $\rho\in R$. Since $|X| \le\kappa< \rho= \operatorname{cf}(\rho)$, we have $h_X \in\prod R$. We show that

is $\Gamma(I,\sigma)$-cofinal in $\prod R$.

Fix a proper $\sigma$-complete ideal $J$ on $R$ extending an image of $I$, and choose $\bar{\eta} = \langle\eta_\beta: \beta< \theta\rangle$ witnessing the extension property. Given $f \in\prod R$, apply the covering property to $\beta\mapsto f(\eta_\beta)$ and choose $\mathcal{X} \in[\mathcal{C}]^{<\sigma}$ such that

Put

If $\eta_\beta\in B_f$, then $f(\eta_\beta)$ belongs to none of the sets in $\mathcal{X}$, so $\beta\in E$. Thus the preimage of $B_f$ under $\bar{\eta}$ belongs to $I$, and hence $B_f \in J$. This proves that $F$ is $\Gamma(I,\sigma)$-cofinal, and therefore

This completes the cycle.

Conclusion

We conclude by emphasizing how the results of this paper should be viewed. Our main point is not that we have three different theorems characterizing various covering numbers in terms of pcf data. Instead, we want to demonstrate that there is a general technique that works here and that can easily be adapted to other settings: suitable local bounds in products of regular cardinals can be converted into global coverings by an elementary partition argument. The bounds supply refinements that shrink the relevant cells, and a tree of these refinements yields a covering because cell cardinalities cannot decrease indefinitely.

The three applications demonstrate how to reuse this mechanism. For ordinary coverings, diagonal coverings, and coverings modulo a complete ideal, the task is to identify the appropriate notion of cofinality and organize the resulting refinements to meet the covering requirement. The parallel characterizations by local true cofinalities, pseudopowers, and cofinal families in full products arise from this common method.

Finally, in the spirit of the times we add a disclosure on the use of AI in the preparation of this paper: the use of AI was limited to assistance with editing and proofreading, and the author is fully responsible for the mathematics. We wrote the paper using the AI capabilities built into the latex editor at murphy.ai.

Department of Mathematics, Ohio University, Athens OH, 45701

Email address: [email protected]