Cofinality
From Free net encyclopedia
In mathematics, especially in order theory, a subset B of a partially ordered set A is cofinal if for every a in A there is a b in B such that a ≤ b. The cofinality of A is the least cardinality of a cofinal subset and is denoted cf(A). Cofinality is only an interesting concept if there is no greatest element in A since otherwise the cofinality is 1.
A cardinal κ such that cf(κ) = κ is called regular; otherwise it is called singular.
Note that the definition of cofinality given above 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 also be similarly defined for a directed set and it is used to generalize the notion of a subsequence in a net.
Examples
- The set of all maximal elements M, of a partially ordered set A, is a subset of every cofinal set in A. Thus if A is finite, its cofinality is equal to the cardinality of M.
- A subset of the natural numbers N, is cofinal in N, if and only if it is infinite.
- It follows from the above example that, the cofinality of <math>\aleph_0</math> is <math>\aleph_0</math>. Thus <math>\aleph_0</math> is regular.
- Let A be a set of order n, and consider the subsets of A with order less than or equal to m. This is a partial order under inclusion with cofinality n choose m.
- The cofinality of any nonzero finite ordinal, or indeed any finite directed set, is 1, since they have a greatest element.
- The cofinality of the real numbers with their usual ordering is <math>\aleph_0</math>, since N is cofinal in R. Note that the usual ordering of R is not order isomorphic to c, the cardinality of the continuum, so 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. Moreover, any cofinal subset of B whose cardinality is equal to the cofinality of B is well-ordered, and these sets are all order isomorphic.
For any infinite cardinal number κ, one equivalent definition is cf(κ) is the least cardinal such that there is an unbounded function from it to κ. Another closely related equivalent definition is cf(κ) = the cardinality of the smallest collection of sets of strictly smaller cardinals such that their sum is κ; more precisely
- <math>\mathrm{cf}(\kappa) = \inf \{ \mathrm{card}(I)\ |\ \kappa = \sum_{i \in I} \lambda_i\ \mathrm{and}\ (\forall i)(\lambda_i < \kappa)\}</math>
That the set above is nonempty comes from the fact that
- <math>\kappa = \bigcup_{i \in \kappa} \{i\}</math>
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,
- <math> \aleph_\omega = \bigcup_{n < \omega} \aleph_n </math>.
the ordinal number ω being the first infinite ordinal, so that the cofinality of <math>\aleph_\omega</math> is card(ω) = <math>\aleph_0</math>. (In particular, <math>\aleph_\omega</math> is singular.) Therefore,
- <math>2^{\aleph_0}\neq\aleph_\omega,</math>
(Compare to the continuum hypothesis, which states <math>2^{\aleph_0}= \aleph_1</math>.)
Generalizing this argument, one can prove that for a limit ordinal δ
- <math>\mathrm{cf} (\aleph_\delta) = \mathrm{cf} (\delta) </math>.
Cofinality in the special case of well-ordered sets
The cofinality of an ordinal <math>\alpha</math> is the smallest ordinal <math>\delta</math> which is the order type of a cofinal subset of <math>\alpha</math>. 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 <math>\delta</math>-indexed strictly increasing sequence with limit <math>\alpha</math>. 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 <math>\omega_\omega</math> or an uncountable cofinality.
The cofinality of 0 is 0. And the cofinality of any successor ordinal is 1. The cofinality of any limit ordinal is at least <math>\omega</math>.
An ordinal which is equal to its cofinality is called regular and it is always the initial ordinal of a cardinal. Any limit of regular ordinals is a limit of initial ordinals and thus is also initial even if it is not regular which it usually is not. If the Axiom of Choice, then <math>\omega_{\alpha+1}</math> is regular for each α. In this case, the ordinals 0, 1, <math>\omega</math>, <math>\omega_1</math>, and <math>\omega_2</math> are regular, whereas 2, 3, <math>\omega_\omega</math>, 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.
A singular ordinal is any ordinal which is not regular.
See also: