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.
We begin with definitions that work even in weak foundations of mathematics.
Given a quasi-ordered set , the cofinality of is the collection of all cardinal numbers such that every function (where is any set of cardinality ) has a (strict) upper bound: an element of such that, whenever belongs to the image of , . A priori, this collection may be a proper class, but it is often a set, indeed always in classical mathematics (as shown below). We traditionally write to mean (for reasons to be seen below).
The ordinal cofinality of is the collection of all ordinal numbers such that . This collection is clearly a down-set and so may be identified with an ordinal number , also called the ordinal cofinality; so we may write in place of , although traditionally we simply write .
If we start with a collection of cardinal numbers, the cardinal cofinality of is the collection of all cardinal numbers such that, given any -indexed family of sets, each of which has cardinality in , the disjoint union of this family (or equivalently the union in a material set theory) also has cardinality in . Again we write or even to mean .
Assume the axiom of choice. Then we may identify and simplify some of the concepts above.
As a class of cardinal numbers, is clearly a down-set (that is closed under subsets), so it must be the set for some cardinal number , also called the cofinality. (Note that , equivalently , since the identity function has no upper bound, so in particular we are not dealing with proper classes.) In this case, we conclude that there is a function that has no strong upper bound, and that is the smallest cardinal number with this property, which is the usual definition. Assuming that is a linear order, it follows that the image of some function is cofinal? in (whence the terminology).
Using the identification of cardinal numbers with certain von Neumann ordinals, the ordinal cofinality or becomes identified with the classical cofinality . (But note that , the collection of cardinal numbers, is only a subset of when we identify cardinals as certain ordinals.)
Every cardinal cofinality is also a down-set of cardinal numbers, hence of the form for some cardinal number . Furthermore, if we start with a cardinal number and define the collection of cardinal numbers, then . If we identify with a von Neumann ordinal, then we also have , so all notions of cofinality agree.
Here is an important theorem on ordinal cofinality, which following our definitions is entirely constructive:
In general, an ordinal number such that is called regular, so every ordinal cofinality is regular. For example, , , and are regular ordinals.
A regular cardinal may be defined to be a collection of cardinals such that . Assuming the axiom of choice and making identifications as above, the regular cardinals and the regular ordinals are the same, except that is a regular cardinal (but not a regular ordinal). Also, 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.