Inmathematics, especially inorder theory, thecofinality cf(A) of apartially ordered setA is the least of thecardinalities of thecofinal subsets ofA. Formally,^[1]

${\displaystyle \mathrm{cf}(A)=inf\{|B|:B\subseteq A,(\mathrm{\forall }x\in A)(\mathrm{\exists }y\in B)(x\le y)\}}$

This definition of cofinality relies on theaxiom of choice, as it uses the fact that every non-empty set ofcardinal numbers has a least member. The cofinality of a partially ordered setA can alternatively be defined as the leastordinalx such that there is a function fromx toA with cofinalimage. This second definition makes sense without the axiom of choice. If the axiom of choice is assumed, as will be the case in the rest of this article, then the two definitions are equivalent.

Cofinality can be similarly defined for adirected set and is used to generalize the notion of asubsequence in anet.

• The cofinality of a partially ordered set withgreatest element is 1 as the set consisting only of the greatest element is cofinal (and must be contained in every other cofinal subset).
  • In particular, the cofinality of any nonzero finite ordinal, or indeed any finite directed set, is 1, since such sets have a greatest element.
• Every cofinal subset of a partially ordered set must contain allmaximal elements of that set. Thus the cofinality of a finite partially ordered set is equal to the number of its maximal elements.
  • In particular, let${\displaystyle A}$ be a set of size${\displaystyle n,}$ and consider the set of subsets of${\displaystyle A}$ containing no more than${\displaystyle m}$ elements. This is partially ordered under inclusion and the subsets with${\displaystyle m}$ elements are maximal. Thus the cofinality of this poset is${\displaystyle n}$choose${\displaystyle m.}$
• A subset of thenatural numbers${\displaystyle \mathbb{N}}$ is cofinal in${\displaystyle \mathbb{N}}$ if and only if it is infinite, and therefore the cofinality of${\displaystyle {\mathrm{\aleph }}_0}$ is${\displaystyle {\mathrm{\aleph }}_0.}$ Thus${\displaystyle {\mathrm{\aleph }}_0}$ is aregular cardinal.
• The cofinality of thereal numbers with their usual ordering is${\displaystyle {\mathrm{\aleph }}_0,}$ since${\displaystyle \mathbb{N}}$ is cofinal in${\displaystyle \mathbb{R}.}$ The usual ordering of${\displaystyle \mathbb{R}}$ is notorder isomorphic to${\displaystyle c,}$ thecardinality of the real numbers, which has cofinality strictly greater than${\displaystyle {\mathrm{\aleph }}_0.}$ This demonstrates that the cofinality depends on the order; different orders on the same set may have different cofinality.

If${\displaystyle A}$ admits atotally ordered cofinal subset, then we can find a subset${\displaystyle B}$ that is well-ordered and cofinal in${\displaystyle A.}$ Any subset of${\displaystyle B}$ is also well-ordered. Two cofinal subsets of${\displaystyle B}$ with minimal cardinality (that is, their cardinality is the cofinality of${\displaystyle B}$) need not be order isomorphic (for example if${\displaystyle B=\omega +\omega ,}$ then both${\displaystyle \omega +\omega }$ and viewed as subsets of${\displaystyle B}$ have the countable cardinality of the cofinality of${\displaystyle B}$ but are not order isomorphic). But cofinal subsets of${\displaystyle B}$ with minimal order type will be order isomorphic.

Thecofinality of an ordinal${\displaystyle \alpha }$ is the smallest ordinal${\displaystyle \delta }$ that is theorder type of acofinal subset of${\displaystyle \alpha .}$ The cofinality of a set of ordinals or any otherwell-ordered set is the cofinality of the order type of that set.

Thus for alimit ordinal${\displaystyle \alpha ,}$ there exists a${\displaystyle \delta }$-indexed strictly increasing sequence with limit${\displaystyle \alpha .}$ For example, the cofinality of${\displaystyle {\omega }^2}$ is${\displaystyle \omega ,}$ because the sequence${\displaystyle \omega \cdot m}$ (where${\displaystyle m}$ ranges over the natural numbers) tends to${\displaystyle {\omega }^2;}$ but, more generally, any countable limit ordinal has cofinality${\displaystyle \omega .}$ An uncountable limit ordinal may have either cofinality${\displaystyle \omega }$ as does${\displaystyle {\omega }_{\omega }}$ or an uncountable cofinality.

The cofinality of 0 is 0. The cofinality of anysuccessor ordinal is 1. The cofinality of any nonzero limit ordinal is an infinite regular cardinal.

Aregular ordinal is an ordinal that is equal to its cofinality. Asingular ordinal is any ordinal that is not regular.

Every regular ordinal is theinitial ordinal of a cardinal. Any limit of regular ordinals is a limit of initial ordinals and thus is also initial but need not be regular. Assuming the axiom of choice,${\displaystyle {\omega }_{\alpha +1}}$ is regular for each${\displaystyle \alpha .}$ In this case, the ordinals${\displaystyle 0,1,\omega ,{\omega }_1,}$ and${\displaystyle {\omega }_2}$ are regular, whereas${\displaystyle 2,3,{\omega }_{\omega },}$ and${\displaystyle {\omega }_{\omega \cdot 2}}$ are initial ordinals that are not regular.

The cofinality of any ordinal${\displaystyle \alpha }$ is a regular ordinal, that is, the cofinality of the cofinality of${\displaystyle \alpha }$ is the same as the cofinality of${\displaystyle \alpha .}$ So the cofinality operation isidempotent.

If${\displaystyle \kappa }$ is an infinite cardinal number, then${\displaystyle \mathrm{cf}(\kappa )}$ is the least cardinal such that there is anunbounded function from${\displaystyle \mathrm{cf}(\kappa )}$ to${\displaystyle \kappa ;}$${\displaystyle \mathrm{cf}(\kappa )}$ is also the cardinality of the smallest set of strictly smaller cardinals whose sum is${\displaystyle \kappa ;}$ more precisely

That the set above is nonempty comes from the fact that$${\displaystyle \kappa =\bigcup _{i\in \kappa }\{i\}}$$that is, thedisjoint union of${\displaystyle \kappa }$ singleton sets. This implies immediately that${\displaystyle \mathrm{cf}(\kappa )\le \kappa .}$ The cofinality of any totally ordered set is regular, so${\displaystyle \mathrm{cf}(\kappa )=\mathrm{cf}(\mathrm{cf}(\kappa )).}$

UsingKönig's theorem, one can prove and for any infinite cardinal${\displaystyle \kappa .}$

The last inequality implies that the cofinality of the cardinality of the continuum must be uncountable. On the other hand,the ordinal number ω being the first infinite ordinal, so that the cofinality of${\displaystyle {\mathrm{\aleph }}_{\omega }}$ is card(ω) =${\displaystyle {\mathrm{\aleph }}_0.}$ (In particular,${\displaystyle {\mathrm{\aleph }}_{\omega }}$ is singular.) Therefore,$${\displaystyle 2^{{\mathrm{\aleph }}_0}\ne {\mathrm{\aleph }}_{\omega }.}$$

(Compare to thecontinuum hypothesis, which states${\displaystyle 2^{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_1.}$)

Generalizing this argument, one can prove that for a limit ordinal${\displaystyle \delta }$$${\displaystyle \mathrm{cf}({\mathrm{\aleph }}_{\delta })=\mathrm{cf}(\delta ).}$$

On the other hand, if theaxiom of choice holds, then for a successor or zero ordinal${\displaystyle \delta }$$${\displaystyle \mathrm{cf}({\mathrm{\aleph }}_{\delta })={\mathrm{\aleph }}_{\delta }.}$$

• Club set – Set theory concept
• Initial ordinal – Mathematical conceptPages displaying short descriptions of redirect targets

• Cardinal numbers
• Order theory
• Ordinal numbers
• Set theory

• Articles with short description
• Short description is different from Wikidata
• Pages displaying short descriptions of redirect targets via Module:Annotated link