# 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:\left[\kappa \right]\to Q$ (where $\left[\kappa \right]$ 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. A priori, this collection $\mathrm{Cf}\left(Q\right)$ 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}\left(Q\right)$ to mean $\kappa \in \mathrm{Cf}\left(Q\right)$ (for reasons to be seen below).

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

If we start with a collection $C$ of cardinal numbers, the cardinal cofinality of $C$ is the collection $\mathrm{Ccf}\left(C\right)$ of all cardinal numbers $\kappa$ such that, given any $\left[\kappa \right]$-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}\left(C\right)$ or even $\kappa <\mathrm{cf}\left(C\right)$ to mean $\kappa \in \mathrm{Ccf}\left(C\right)$.

## 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}\left(Q\right)$ is clearly a down-set (that is closed under subsets), so it must be the set $\left\{\kappa \phantom{\rule{thickmathspace}{0ex}}\mid \phantom{\rule{thickmathspace}{0ex}}\kappa <\mathrm{cf}\left(Q\right)\right\}$ for some cardinal number $\mathrm{cf}\left(Q\right)$, also called the cofinality. (Note that $\mathrm{cf}\left(Q\right)\le \mid Q\mid$, equivalently $\mid Q\mid \nless \mathrm{cf}\left(Q\right)$, 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 $\left[\mathrm{cf}\left(Q\right)\right]\to Q$ that has no strong upper bound, and that $\mathrm{cf}\left(Q\right)$ 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 $\left[\mathrm{cf}\left(Q\right)\right]\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}\left(Q\right)$ or $\mathrm{ocf}\left(Q\right)$ becomes identified with the classical cofinality $\mathrm{cf}\left(Q\right)$. (But note that $\mathrm{Cf}\left(Q\right)$, the collection of cardinal numbers, is only a subset of $\mathrm{Ocf}\left(Q\right)$ when we identify cardinals as certain ordinals.)

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

## Properties

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

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

In general, an ordinal number $\alpha$ such that $\mathrm{ocf}\left(\alpha \right)=\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}\left(C\right)=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, $\left\{1\right\}$ 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.

Revised on March 11, 2012 15:16:36 by Toby Bartels (75.88.85.16)