Kerodon

$\Newextarrow{\xRightarrow}{5,5}{0x21D2}$ $\newcommand\empty{}$
$\Newextarrow{\xhookrightarrow}{10,10}{0x21AA}$

5.4.3 Smallness of Sets

We now introduce some terminology which will be useful for measuring the sizes of various mathematical objects.

Definition 5.4.3.1. Let $\kappa $ be a cardinal. We say that a set $S$ is $\kappa $-small if the cardinality $|S|$ is strictly smaller than $\kappa $.

Example 5.4.3.2. Let $\aleph _0$ denote the first infinite cardinal (Example 5.4.2.10). Then a set $S$ is $\aleph _0$-small if and only if it is finite.

Example 5.4.3.3. Let $\aleph _1$ denote the first uncountable cardinal (Example 5.4.2.12). Then a set $S$ is $\aleph _1$-small if and only if it is countable.

Remark 5.4.3.4. Let $\kappa $ be a cardinal and let $T$ be a $\kappa $-small set. Then:

  • Any subset of $T$ is also $\kappa $-small (see Proposition 5.4.2.3).

  • The set $T$ is $\lambda $-small for every cardinal $\lambda \geq \kappa $.

  • For every surjective morphism of sets $T \twoheadrightarrow S$, the set $S$ is also $\kappa $-small.

Proposition 5.4.3.5. Let $\kappa $ be an infinite cardinal. Then the collection of $\kappa $-small sets is closed under finite products.

Proof. We first note that the collection of finite sets is closed under finite products. It will therefore suffice to show that, for every infinite cardinal $\lambda $, the following condition is satisfied:

$(\ast _{\lambda })$

If $S$ and $T$ are sets of cardinality $\leq \lambda $, then the product $S \times T$ has cardinality $\leq \lambda $.

By virtue of Remark 5.4.2.9, we may assume that condition $(\ast _{\mu } )$ is satisfied for every cardinal $\mu < \lambda $. Without loss of generality, we may assume that $S = \mathrm{Ord}_{< \lambda } = T$, where $\mathrm{Ord}_{< \lambda }$ denotes the collection of ordinals smaller than $\lambda $. Given a pair of elements $(\alpha ,\beta ), (\alpha ', \beta ') \in S \times T$, let us write $(\alpha ', \beta ') \preceq (\alpha , \beta )$ if either $\mathrm{max}( \alpha ', \beta ') < \mathrm{max}( \alpha , \beta )$, or $\mathrm{max}( \alpha ', \beta ') = \mathrm{max}( \alpha , \beta )$ and $\alpha ' < \alpha $, or $\mathrm{max}( \alpha ', \beta ' ) = \mathrm{max}(\alpha , \beta )$ and $\alpha ' = \alpha $ and $\beta ' \leq \beta $. The relation $\preceq $ defines a well-ordering of the set $S \times T$. To prove $(\ast _{\lambda })$, it will suffice to show this well ordering has order type $\leq \lambda $. Assume otherwise. Then there exists an element $(\alpha ,\beta ) \in S \times T$ such that $\lambda $ is the order type of the initial segment $K = \{ (\alpha ',\beta ') \in S \times T: (\alpha ', \beta ') \prec (\alpha , \beta ) \} $. Note that $K$ is a subset of the product $\mathrm{Ord}_{ \leq \alpha }$ and $\mathrm{Ord}_{ \leq \beta }$. Our inductive hypothesis guarantees that $K$ has cardinality $< \lambda $, contradicting Corollary 5.4.2.5. $\square$

Corollary 5.4.3.6. Let $\kappa $ be an infinite cardinal. Then the collection of $\kappa $-small sets is closed under finite coproducts.

Proof. Let $\{ S_ i \} _{i \in I}$ be a finite collection of $\kappa $-small sets. Then the disjoint union $\coprod _{ i \in I} S_ i$ can be identified with a subset of the product $\prod _{i \in I} (S_ i \coprod \{ i \} )$, which is $\kappa $-small by virtue of Proposition 5.4.3.5. $\square$

We will need the following generalization of Corollary 5.4.3.6:

Proposition 5.4.3.7. Let $\kappa $ and $\lambda $ be cardinals, where $\lambda $ is infinite. The following conditions are equivalent:

$(1)$

The cardinal $\kappa $ is strictly smaller than the cofinality $\mathrm{cf}(\lambda )$ (see Definition 5.4.1.28).

$(2)$

Let $\{ T_{s} \} _{s \in S}$ be a collection of $\lambda $-small sets indexed by a set $S$ of cardinality $\leq \kappa $. Then the coproduct $\coprod _{s \in S} T_{s}$ is $\lambda $-small.

Proof. Assume first that condition $(1)$ is satisfied. Let $\{ T_{s} \} _{s \in S}$ be a collection of $\lambda $-small sets indexed by a set $S$ of cardinality $\leq \kappa $; we wish to show that the coproduct $T = \coprod _{s \in S} T_{s}$ is $\lambda $-small. Using Theorem 5.4.1.34, we can choose a well-ordering $\leq _{S}$ on the set $S$, and a well-ordering $\leq _{s}$ on the set $T_{s}$ for each $s \in S$. For elements $t \in T_{s}$ and $t' \in T_{s'}$, write $t \leq _{T} t'$ if either $s <_{S} s'$, or $s = s'$ and $t \leq _{s} t'$. Then $\leq _{T}$ is a well-ordering of the set $T$. If $T$ is not $\lambda $-small, then it has an initial segment of order type $\lambda $. Passing to subsets, we may assume without loss of generality that $T$ itself has order type $\lambda $. Moreover, we may assume without loss of generality that each of the sets $T_{s}$ is nonempty, and therefore contains a smallest element $t_{s}$. We consider two cases:

  • Suppose that $S$ contains a largest element $s$. In this case, we can write $T$ as the disjoint union of the initial segment $T' = \coprod _{s' < s} T_{s'}$ with the set $T_{s}$. Since $T_{s}$ is nonempty, $T'$ has order type smaller than $\lambda $, and is therefore $\lambda $-small. Applying Corollary 5.4.3.6, we deduce that $T = T' \coprod T_{s}$ is also $\lambda $-small.

  • Suppose that $S$ does not have a largest element. In this case, the construction $(s \in S) \mapsto (t_ s \in T)$ is a cofinal function from $S$ to $T$. It follows that the order type of $(S, \leq _{S} )$ is greater than or equal to the cofinality $\mathrm{cf}(T) = \mathrm{cf}(\lambda )$, contradicting assumption $(1)$.

We now prove the reverse implication. Assume that condition $(2)$ is satisfied. Choose a well-ordering $(S, \leq _{S} )$ of order type $\mathrm{cf}(\lambda )$ and a cofinal map $f: S \rightarrow \mathrm{Ord}_{< \lambda }$. If $\kappa \geq \mathrm{cf}(\lambda )$, then condition $(2)$ implies that the disjoint union $\coprod _{s \in S} \mathrm{Ord}_{ < f(s) }$ is $\lambda $-small. Since $f$ is cofinal, the tautological map $\coprod _{s \in S} \mathrm{Ord}_{ < f(s) } \rightarrow \mathrm{Ord}_{< \lambda }$ is surjective. It follows that $\mathrm{Ord}_{< \lambda }$ is $\lambda $-small, which is a contradiction. $\square$

Corollary 5.4.3.8. Let $\lambda $ be an infinite cardinal. Then $\kappa = \mathrm{cf}(\lambda )$ is the smallest cardinal for which there exists a set $S$ of cardinality $\kappa $ and a collection of $\lambda $-small sets $\{ T_{s} \} _{s \in S}$, where the coproduct $\coprod _{s \in S} T_ s$ is not $\lambda $-small.

Proof. Proposition 5.4.2.14 guarantees that $\kappa $ is a cardinal. The characterization is a restatement of Proposition 5.4.3.7. $\square$

Corollary 5.4.3.9. Let $\lambda $ be an infinite cardinal and let $\kappa = \mathrm{cf}(\lambda )$ be its cofinality. Suppose we are given a collection of $\lambda $-small sets $\{ T_{s} \} _{s \in S}$. If the index set $S$ is $\kappa $-small, then coproduct $\coprod _{s \in S} T_ s$ is $\lambda $-small.

Definition 5.4.3.10 (Regular Cardinals). Let $\kappa $ be a cardinal. We say that $\kappa $ is regular if it is infinite and $\mathrm{cf}(\kappa ) = \kappa $. Here $\mathrm{cf}(\kappa )$ denotes the cofinality of $\kappa $ (Definition 5.4.1.28). We say that $\kappa $ is singular if it is infinite but not regular.

Remark 5.4.3.11. Let $\kappa $ be an infinite cardinal. Then $\kappa $ is regular if and only if the collection of $\kappa $-small sets is closed under $\kappa $-small coproducts (this is a special case of Corollary 5.4.3.8).

Example 5.4.3.12. Let $\aleph _0$ denote the first infinite cardinal (Example 5.4.2.10). Then $\aleph _0$ is regular: that is, the collection of finite sets is closed under finite coproducts.

Example 5.4.3.13 (Successor Cardinals). Let $\kappa $ be an infinite cardinal and let $\kappa ^{+}$ be its successor (Example 5.4.2.11). Then a set $S$ is $\kappa ^{+}$-small if and only if it has cardinality $\leq \kappa $. It follows that $\kappa ^{+}$ is a regular cardinal. That is, if $\{ T_ s \} _{s \in S}$ is a collection of sets of cardinality $\leq \kappa $ indexed by a set $S$ of cardinality $\leq \kappa $, then the disjoint union $\coprod _{s \in S} T_{s}$ also has cardinality $\leq \kappa $. To prove this, choose a collection of monomorphisms $\{ i_ s: T_ s \hookrightarrow T \} _{s \in S}$, where $T$ is a set of cardinality $\kappa $. We then obtain a monomorphism

\[ \coprod _{ s \in S} T_{s} \hookrightarrow S \times T \quad \quad (x \in T_ s) \mapsto ( s, i_ s(x) ), \]

where the set $S \times T$ has cardinality $\leq \kappa $ by virtue of Proposition 5.4.3.5.

Example 5.4.3.14. Let $\aleph _1$ denote the first uncountable cardinal (Example 5.4.2.12). Then $\aleph _1$ is regular: that is, the collection of countable sets is closed under the formation of countable disjoint unions. This is a special case of Example 5.4.3.13, since $\aleph _1 = \aleph _0^{+}$.

Example 5.4.3.15. Let $(T, \leq )$ be a nonempty linearly ordered set with no largest element. Then the cofinality $\kappa = \mathrm{cf}(T)$ is a regular cardinal. To see this, choose a well-ordered set $(S, \leq )$ of order type $\kappa $ and a cofinal function $f: S \rightarrow T$. Proposition 5.4.2.14 guarantees that $\kappa $ is a cardinal, and Example 5.4.1.31 shows that $\kappa $ is infinite. If it is not regular, then there exists a cofinal map $g: R \rightarrow S$, where $(R, \leq )$ is a well-ordered set of order type $\alpha < \kappa $. This contradicts the definition of $\kappa = \mathrm{cf}(T)$, since the composite map $(f \circ g): R \rightarrow T$ is cofinal.

It will be convenient to introduce the following bit of nonstandard terminology:

Definition 5.4.3.16. Let $\lambda $ be an infinite cardinal. We let $\mathrm{ecf}(\lambda )$ denote the least cardinal $\kappa $ with the following property: there exists a set $S$ of cardinality $\kappa $ and a collection of $\lambda $-small sets $\{ T_{s} \} _{s \in S}$ for which the product $\prod _{s \in S} T_ s$ is not $\lambda $-small. We will refer to $\mathrm{ecf}(\lambda )$ as the exponential cofinality of $\lambda $.

Remark 5.4.3.17. Let $\lambda $ be an infinite cardinal. Then the exponential cofinality $\mathrm{ecf}(\lambda )$ satisfies $\aleph _0 \leq \mathrm{ecf}(\lambda ) \leq \mathrm{cf}(\lambda )$. In particular, we have $\mathrm{ecf}(\lambda ) \leq \lambda $. The inequality $\aleph _0 \leq \mathrm{ecf}(\lambda )$ is a reformulation of the fact that the collection of $\lambda $-small sets is closed under finite products (Proposition 5.4.3.5). To prove the other inequality, choose a set $S$ of cardinality $\mathrm{cf}(\lambda )$ and a collection of $\lambda $-small sets $\{ T_ s \} _{s \in S}$ for which the coproduct $T = \coprod _{s \in S} T_{s}$ is not $\lambda $-small. We now observe that $T$ can be identified with a subset of the product $\prod _{s \in S} ( T_ s \coprod \{ s\} )$. Since each of the sets $T_{s} \coprod \{ s\} $ is also $\lambda $-small, we obtain $\mathrm{ecf}(\lambda ) \leq \mathrm{cf}(\lambda )$.

Remark 5.4.3.18. Let $\kappa $ and $\lambda $ be infinite cardinals. Then $\kappa \leq \mathrm{ecf}(\lambda )$ if and only if the following condition is satisfied: for every collection of $\lambda $-small sets $\{ T_ s \} _{s \in S}$ indexed by a $\kappa $-small set $S$, the product $\prod _{s \in S} T_{s}$ is also $\lambda $-small.

Remark 5.4.3.19. Let $\kappa $ be an infinite cardinal. Then there are arbitrarily large regular cardinals $\lambda $ satisfying $\mathrm{ecf}(\lambda ) > \kappa $. To see this, it will suffice (by enlarging $\kappa $) to show that there exists some regular cardinal $\lambda $ of exponential cofinality $\geq \kappa $. Let $S$ be a set of cardinality $\kappa $ and let $2^{\kappa }$ denote the cardinality of the power set $P(S) = \{ S_0: S_0 \subseteq S\} $. Proposition 5.4.3.5 implies that the product $S \times S$ also has cardinality $\kappa $, so that $P(S \times S) \simeq \prod _{s \in S} P(S)$ also has cardinality $2^{\kappa }$. It follows that the collection of sets of cardinality $\leq 2^{\kappa }$ is closed under the formation of products indexed by sets of cardinality $\leq \kappa $, so that $\lambda = ( 2^{\kappa } )^{+}$ has exponential cofinality $> \kappa $.

Definition 5.4.3.20. Let $\kappa $ be an infinite cardinal. We say that $\kappa $ is strongly inaccessible if $\kappa = \mathrm{ecf}(\kappa )$. In other words, $\kappa $ is strongly inaccessible if the collection of $\kappa $-small sets is closed under the formation of $\kappa $-small products.

Example 5.4.3.21. Let $\aleph _0$ be the least infinite cardinal. Then $\aleph _0$ is strongly inaccessible. That is, the collection of finite sets is closed under finite products.

Remark 5.4.3.22. Let $\kappa $ be a strongly inaccessible cardinal. Then $\kappa $ is regular: this follows immediately from the inequality $\mathrm{ecf}(\kappa ) \leq \mathrm{cf}(\kappa )$ of Remark 5.4.3.17.

Warning 5.4.3.23. The existence of uncountable strongly inaccessible cardinals cannot be proven from the axioms of Zermelo-Fraenkel set theory (assuming those axioms are consistent).

Proposition 5.4.3.24. Let $\lambda $ be an infinite cardinal and let $\kappa = \mathrm{ecf}(\lambda )$ be the exponential cofinality of $\lambda $. Then $\kappa $ is a regular cardinal.

Proof. Suppose that $\kappa $ is not regular: that is, there is a collection of $\kappa $-small sets $\{ T_{s} \} _{s \in S}$ indexed by a $\kappa $-small set $S$ such that $T = \coprod _{s \in S} T_ s$ has cardinality $\geq \kappa $. Choose a collection of $\lambda $-small sets $\{ U_{t} \} _{t \in T}$ for which the product $U = \prod _{t \in T} U_ t$ is not $\lambda $-small. For each $s \in S$, let $U_{s}$ denote the product $\prod _{ t \in T_{s} } U_{t}$. Since $T_{s}$ is $\mathrm{ecf}(\lambda )$-small, the set $U_{s}$ is $\lambda $-small. Since $S$ is also $\mathrm{ecf}(\lambda )$-small, it follows that $U \simeq \prod _{s \in S} U_ s$ is also $\lambda $-small, which is a contradiction. $\square$