Cofinality

related topics
{math, number, function}

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.

Contents

Examples

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

Full article ▸

related documents
Semi-continuity
Ternary numeral system
Upper and lower bounds
Iterative method
Division ring
Conjugacy class
Homomorphism
Lambert W function
Infimum
Elliptic function
Principal ideal domain
ZPP
Pointless topology
Shannon–Fano coding
Counting sort
Five lemma
Dedekind cut
Distributivity
Intermediate value theorem
Arithmetic function
Multiplication table
Cyclone (programming language)
Möbius function
Soundness
Linear cryptanalysis
Commutator
Pseudocode
Group isomorphism
Banach algebra
Elementary function