In mathematics, especially in order theory, the cofinality cf(A) of a partially ordered set A is the least of the cardinalities of the cofinal subsets of A.

This definition of cofinality relies on the axiom of choice, as it uses the fact that every non-empty set of cardinal numbers has a least member. The cofinality of a partially ordered set A can alternatively be defined as the least ordinal x such that there is a function from x to A with cofinal image. 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 a directed set and is used to generalize the notion of a subsequence in a net.

Examples edit

  • The cofinality of a partially ordered set with greatest 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 all maximal 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   be a set of size   and consider the set of subsets of   containing no more than   elements. This is partially ordered under inclusion and the subsets with   elements are maximal. Thus the cofinality of this poset is   choose  
  • A subset of the natural numbers   is cofinal in   if and only if it is infinite, and therefore the cofinality of   is   Thus   is a regular cardinal.
  • The cofinality of the real numbers with their usual ordering is   since   is cofinal in   The usual ordering of   is not order isomorphic to   the cardinality of the real numbers, which has cofinality strictly greater than   This demonstrates that the cofinality depends on the order; different orders on the same set may have different cofinality.

Properties edit

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

Cofinality of ordinals and other well-ordered sets edit

The cofinality of an ordinal   is the smallest ordinal   that is the order type of a cofinal subset of   The cofinality of a set of ordinals or any other well-ordered set is the cofinality of the order type of that set.

Thus for a limit ordinal   there exists a  -indexed strictly increasing sequence with limit   For example, the cofinality of   is   because the sequence   (where   ranges over the natural numbers) tends to   but, more generally, any countable limit ordinal has cofinality   An uncountable limit ordinal may have either cofinality   as does   or an uncountable cofinality.

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

Regular and singular ordinals edit

A regular ordinal is an ordinal that is equal to its cofinality. A singular ordinal is any ordinal that is not regular.

Every regular ordinal is the initial 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,   is regular for each   In this case, the ordinals   and   are regular, whereas   and   are initial ordinals that are not regular.

The cofinality of any ordinal   is a regular ordinal, that is, the cofinality of the cofinality of   is the same as the cofinality of   So the cofinality operation is idempotent.

Cofinality of cardinals edit

If   is an infinite cardinal number, then   is the least cardinal such that there is an unbounded function from   to     is also the cardinality of the smallest set of strictly smaller cardinals whose sum is   more precisely


That the set above is nonempty comes from the fact that

that is, the disjoint union of   singleton sets. This implies immediately that   The cofinality of any totally ordered set is regular, so  

Using König's theorem, one can prove   and   for any infinite cardinal  

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   is card(ω) =   (In particular,   is singular.) Therefore,


(Compare to the continuum hypothesis, which states  )

Generalizing this argument, one can prove that for a limit ordinal  


On the other hand, if the axiom of choice holds, then for a successor or zero ordinal  


See also edit

  • Club set – Set theory concept
  • Initial ordinal – mathematical concept

References edit

  • Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.
  • Kunen, Kenneth, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9.