Cofinality

 ( Cardinal Numbers ) 

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

$\backslash operatorname\{cf\}(A)\; =\; \backslash inf\; \backslash \{|B|\; :\; B\; \backslash subseteq\; A,\; (\backslash forall\; x\; \backslash in\; A)\; (\backslash exists\; y\; \backslash in\; B)\; (x\; \backslash leq\; y)\backslash \}$

This definition of cofinality relies on the axiom of choice, as it uses the fact that every non-empty set of has a least member. The cofinality of a partially ordered set A can alternatively be defined as the least ordinal number 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

• 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. The cofinality of any successor ordinal is 1.
• Every cofinal subset of a partially ordered set must contain all 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 $\backslash N$ is cofinal in $\backslash N$ if and only if it is infinite, and therefore the cofinality of $\backslash aleph\_0$ is $\backslash aleph\_0.$ Thus $\backslash aleph\_0$ is a regular cardinal.
• The cofinality of the with their usual ordering is $\backslash aleph\_0,$ since $\backslash N$ is cofinal in $\backslash R.$ The usual ordering of $\backslash R$ is not order isomorphic to $c,$ the cardinality of the real numbers, which has cofinality strictly greater than $\backslash 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 total order cofinal subset, then we can find a subset $B$ that is well-ordered and cofinal in $A.$ Any subset of $B$ is also well-ordered. Two cofinal subsets of $B$ with minimal cardinality (that is, their cardinality is the cofinality of $B$) need not be order isomorphic (for example if $B\; =\; \backslash omega\; +\; \backslash omega,$ then both $\backslash omega\; +\; \backslash omega$ and viewed as subsets of $B$ have the countable cardinality of the cofinality of $B$ but are not order isomorphic). But cofinal subsets of $B$ with minimal order type will be order isomorphic.

---

Cofinality of ordinals and other well-ordered sets The cofinality of an ordinal $\backslash alpha$ is the smallest ordinal $\backslash delta$ that is the order type of a cofinal subset of $\backslash alpha.$ 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 $\backslash alpha,$ there exists a $\backslash delta$-indexed strictly increasing sequence with limit $\backslash alpha.$ For example, the cofinality of $\backslash omega^2$ is $\backslash omega,$ because the sequence $\backslash omega\; \backslash cdot\; m$ (where $m$ ranges over the natural numbers) tends to $\backslash omega^2;$ but, more generally, any countable limit ordinal has cofinality $\backslash omega.$ An uncountable limit ordinal may have either cofinality $\backslash omega$ as does $\backslash omega\_\backslash omega$ 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 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, $\backslash omega\_\{\backslash alpha+1\}$ is regular for each $\backslash alpha.$ In this case, the ordinals $0,\; 1,\; \backslash omega,\; \backslash omega\_1,$ and $\backslash omega\_2$ are regular, whereas $2,\; 3,\; \backslash omega\_\backslash omega,$ and $\backslash omega\_\{\backslash omega\; \backslash cdot\; 2\}$ are initial ordinals that are not regular.

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

---

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

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

Using Kőnig's theorem, one can prove and for any infinite cardinal $\backslash 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 $\backslash aleph\_\backslash omega$ is card(ω) = $\backslash aleph\_0.$ (In particular, $\backslash aleph\_\backslash omega$ is singular.) Therefore, $$2^\{\backslash aleph\_0\}\; \backslash neq\; \backslash aleph\_\backslash omega.$$

(Compare to the continuum hypothesis, which states $2^\{\backslash aleph\_0\}\; =\; \backslash aleph\_1.$)

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

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

---

See also

• Thomas Jech, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. .
• Kenneth Kunen, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. .

Post Comment