In
mathematics, especially in
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intro ...
, the cofinality cf(''A'') of a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
''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 number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
s 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
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
. 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
In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive and transitive binary relation \,\leq\, (that is, a preorder), with the additional property that every pair of elements has ...
and is used to generalize the notion of a
subsequence
In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is ...
in a
net.
Examples
* The cofinality of a partially ordered set with
greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an elem ...
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 element
In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is defi ...
s 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 number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s
is cofinal in
if and only if it is infinite, and therefore the cofinality of
is
Thus
is a
regular cardinal
In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. More explicitly, this means that \kappa is a regular cardinal if and only if every unbounded subset C \subseteq \kappa has cardinality \kappa. Infinite ...
.
* The cofinality of the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every r ...
s with their usual ordering is
since
is cofinal in
The usual ordering of
is not
order isomorphic
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be cons ...
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
If
admits a
totally ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
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
The cofinality of an ordinal
is the smallest ordinal
that is the
order type
In mathematics, especially in set theory, two ordered sets and are said to have the same order type if they are order isomorphic, that is, if there exists a bijection (each element pairs with exactly one in the other set) f\colon X \to Y such t ...
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
In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists an ...
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 In set theory, the successor of an ordinal number ''α'' is the smallest ordinal number greater than ''α''. An ordinal number that is a successor is called a successor ordinal. Properties
Every ordinal other than 0 is either a successor ordin ...
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
In a written or published work, an initial capital, also referred to as a drop capital or simply an initial cap, initial, initcapital, initcap or init or a drop cap or drop, is a letter at the beginning of a word, a chapter, or a paragraph tha ...
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
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of p ...
.
Cofinality of cardinals
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
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ( ...
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
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that
or equivalently, that
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
, 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
*
*
References
* Jech, Thomas, 2003. ''Set Theory: The Third Millennium Edition, Revised and Expanded''. Springer. .
* Kunen, Kenneth, 1980. ''Set Theory: An Introduction to Independence Proofs''. Elsevier. .
{{Order theory
Cardinal numbers
Order theory
Ordinal numbers
Set theory