Cofinality

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.

Properties

If A admits a totally ordered cofinal subset, then we can find a subset B which is well-ordered and cofinal in A. Any subset of B is also well-ordered. If two cofinal subsets of B have minimal cardinality (i.e. their cardinality is the cofinality of B), then they are order isomorphic to each other.

Cofinality of ordinals and other well-ordered sets

The cofinality of an ordinal α is the smallest ordinal δ which 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 ω·m (where m 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 limit ordinal is at least ω.

Regular and singular ordinals

A regular ordinal is an ordinal which is equal to its cofinality. A singular ordinal is any ordinal which 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, ωα + 1 is regular for each α. In this case, the ordinals 0, 1, ω, ω1, and ω2 are regular, whereas 2, 3, ωω, and ωω·2 are initial ordinals which are not regular.

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

Cofinality of cardinals

If κ is an infinite cardinal number, then cf(κ) is the least cardinal such that there is an unbounded function from it to κ; and cf(κ) = the cardinality of the smallest collection of sets of strictly smaller cardinals such that their sum is κ; more precisely

\mathrm{cf}(\kappa) = \inf \left\{ \mathrm{card}(I)\ |\ \kappa = \sum_{i \in I} \lambda_i\ \mathrm{and}\ (\forall i)(\lambda_i < \kappa)\right\}

That the set above is nonempty comes from the fact that

\kappa = \bigcup_{i \in \kappa} \{i\}

i.e. the disjoint union of κ singleton sets. This implies immediately that cf(κ) ≤ κ. The cofinality of any totally ordered set is regular, so one has cf(κ) = cf(cf(κ)).

Using König's theorem, one can prove κ < κcf(κ) and κ < cf(2κ) for any infinite cardinal κ.

The last inequality implies that the cofinality of the cardinality of the continuum must be uncountable. On the other hand,

 \aleph_\omega = \bigcup_{n < \omega} \aleph_n .

the ordinal number ω being the first infinite ordinal, so that the cofinality of \aleph_\omega is card(ω) = \aleph_0. (In particular, \aleph_\omega is singular.) Therefore,

2^{\aleph_0}\neq\aleph_\omega.

(Compare to the continuum hypothesis, which states 2^{\aleph_0}= \aleph_1.)

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

\mathrm{cf} (\aleph_\delta) = \mathrm{cf} (\delta) .

See also

  • Initial ordinal

References

  • 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.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Ordinal number — This article is about the mathematical concept. For number words denoting a position in a sequence ( first , second , third , etc.), see Ordinal number (linguistics). Representation of the ordinal numbers up to ωω. Each turn of the spiral… …   Wikipedia

  • Real closed field — In mathematics, a real closed field is a field F in which any of the following equivalent conditions are true:#There is a total order on F making it an ordered field such that, in this ordering, every positive element of F is a square in F and… …   Wikipedia

  • Stationary set — In mathematics, particularly in set theory and model theory, there are at least three notions of stationary set:Classical notionIf kappa is a cardinal of uncountable cofinality, Csubseteqkappa, and C intersects every club in kappa, then C is… …   Wikipedia

  • Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia

  • Singular cardinals hypothesis — In set theory, the singular cardinals hypothesis (SCH) arose from the question of whether the least cardinal number for which the generalized continuum hypothesis (GCH) might fail could be a singular cardinal.According to Mitchell (1992), the… …   Wikipedia

  • List of forcing notions — In mathematics, forcing is a method of constructing new models M[G] of set theory by adding a generic subset G of a poset P to a model M. The poset P used will determine what statements hold in the new universe (the extension ); to force a… …   Wikipedia

  • Mahlo cardinal — In mathematics, a Mahlo cardinal is a certain kind of large cardinal number. Mahlo cardinals were first described by Paul Mahlo (1911, 1912, 1913). As with all large cardinals, none of these varieties of Mahlo cardinals can be proved to… …   Wikipedia

  • PCF theory — is the name of a mathematical theory, introduced by Saharon Shelah (1978), that deals with the cofinality of the ultraproducts of ordered sets. It gives strong upper bounds on the cardinalities of power sets of singular cardinals, and has… …   Wikipedia

  • Easton's theorem — In set theory, Easton s theorem is a result on the possible cardinal numbers of powersets. W. B. harvtxt|Easton|1970 (extending a result of Robert M. Solovay) showed via forcing that : kappa < operatorname{cf}(2^kappa),and, for kappale lambda,,… …   Wikipedia

  • König's theorem (set theory) — For other uses, see König s theorem. In set theory, König s theorem (named after the Hungarian mathematician Gyula König) colloquially states that if the axiom of choice holds, I is a set, mi and ni are cardinal numbers for every i in I , and m i …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”