nLab
cofinality

Idea

The cofinality of a quoset (quasi-ordered set) is a measure of the size of the quoset and in particular of the size of its tails. An important special case is the cofinality of an ordinal number, and there is a related concept of the cofinality of a cardinal number.

Definitions

We begin with definitions that work even in weak foundations of mathematics.

Given a quasi-ordered set $Q$, the cofinality of $Q$ is the collection of all cardinal numbers $\kappa$ such that every function $f:[\kappa ]\to Q$ (where $[\kappa ]$ is any set of cardinality $\kappa$) has a (strict) upper bound: an element $x$ of $Q$ such that, whenever $y$ belongs to the image of $f$, $y<x$. A priori, this collection $\mathrm{Cf}(Q)$ may be a proper class, but it is often a set, indeed always in classical mathematics (as shown below). We traditionally write $\kappa <\mathrm{cf}(Q)$ to mean $\kappa \in \mathrm{Cf}(Q)$ (for reasons to be seen below).

The ordinal cofinality of $Q$ is the collection $\mathrm{Ocf}(Q)$ of all ordinal numbers $\alpha$ such that $\mid \alpha \mid <\mathrm{cf}(Q)$. This collection is clearly a down-set and so may be identified with an ordinal number $ocf(Q)$, also called the ordinal cofinality; so we may write $\alpha <\mathrm{ocf}(Q)$ in place of $\alpha \in \mathrm{Ocf}(Q)$, although traditionally we simply write $\alpha <\mathrm{cf}(Q)$.

If we start with a collection $C$ of cardinal numbers, the cardinal cofinality of $C$ is the collection $\mathrm{Ccf}(C)$ of all cardinal numbers $\kappa$ such that, given any $[\kappa ]$-indexed family $F$ of sets, each of which has cardinality in $C$, the disjoint union of this family (or equivalently the union in a material set theory) also has cardinality in $C$. Again we write $\kappa <\mathrm{ccf}(C)$ or even $\kappa <\mathrm{cf}(C)$ to mean $\kappa \in \mathrm{Ccf}(C)$.

Identifications

Assume the axiom of choice. Then we may identify and simplify some of the concepts above.

• As a class of cardinal numbers, $\mathrm{cf}(Q)$ is clearly a down-set (that is closed under subsets), so it must be the set $\{\kappa \mid \kappa <\mathrm{cf}(Q)\}$ for some cardinal number $\mathrm{cf}(Q)$, also called the cofinality. (Note that $\mathrm{cf}(Q)\le \mid Q\mid$, equivalently $\mid Q\mid \nless \mathrm{cf}(Q)$, since the identity function $Q\to Q$ has no upper bound, so in particular we are not dealing with proper classes.) In this case, we conclude that there is a function $[\mathrm{cf}(Q)]\to Q$ that has no strong upper bound, and that $\mathrm{cf}(Q)$ is the smallest cardinal number with this property, which is the usual definition. Assuming that $Q$ is a linear order, it follows that the image of some function $[\mathrm{cf}(Q)]\to Q$ is cofinal? in $Q$ (whence the terminology).

• Using the identification of cardinal numbers with certain von Neumann ordinals, the ordinal cofinality $\mathrm{Ocf}(Q)$ or $\mathrm{ocf}(Q)$ becomes identified with the classical cofinality $\mathrm{cf}(Q)$. (But note that $\mathrm{Cf}(Q)$, the collection of cardinal numbers, is only a subset of $\mathrm{Ocf}(Q)$ when we identify cardinals as certain ordinals.)

• Every cardinal cofinality $\mathrm{Ccf}(C)$ is also a down-set of cardinal numbers, hence of the form $\{\kappa \mid \kappa <\mathrm{ccf}(C)\}$ for some cardinal number $\mathrm{ccf}(C)$. Furthermore, if we start with a cardinal number $\lambda$ and define the collection $C_{\lambda }≔\{\kappa \mid \kappa <\lambda \}$ of cardinal numbers, then $\mathrm{cf}([\lambda ])=\mathrm{ccf}(C_{\lambda })$. If we identify $\lambda$ with a von Neumann ordinal, then we also have $\mathrm{cf}([\lambda ])=\mathrm{ocf}(\lambda )$, so all notions of cofinality agree.

Properties

Here is an important theorem on ordinal cofinality, which following our definitions is entirely constructive:

$$\mathrm{ocf}(\mathrm{ocf}(Q))=\mathrm{ocf}(Q).$$ocf(ocf(Q)) = ocf(Q) .

In general, an ordinal number $\alpha$ such that $\mathrm{ocf}(\alpha )=\alpha$ is called regular, so every ordinal cofinality is regular. For example, $0$, $1$, and $\omega$ are regular ordinals.

A regular cardinal may be defined to be a collection of cardinals $C$ such that $\mathrm{Ccf}(C)=C$. Assuming the axiom of choice and making identifications as above, the regular cardinals and the regular ordinals are the same, except that $2$ is a regular cardinal (but not a regular ordinal). Also, $\{1\}$ is a regular collection of cardinals that is not a down-set, although every other regular cardinal is (and so can be identified with a cardinal number), classically.

Traditionally, one requires a regular ordinal or cardinal to be infinite, and thus classically they are the same with no exceptions.