In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, specifically
order theory, a
partially ordered set is chain-complete if every
chain
A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
in it has a
least upper bound. It is ω-complete when every increasing
sequence of elements (a type of
countable chain) has a least upper bound; the same notion can be extended to other
cardinalities of chains.
[.]
Examples
Every
complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
lattice is chain-complete. Unlike complete lattices, chain-complete posets are relatively common. Examples include:
* The set of all
linearly independent subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of a
vector space ''V'', ordered by
inclusion.
* The set of all
partial functions on a set, ordered by
restriction
Restriction, restrict or restrictor may refer to:
Science and technology
* restrict, a keyword in the C programming language used in pointer declarations
* Restriction enzyme, a type of enzyme that cleaves genetic material
Mathematics and log ...
.
* The set of all partial
choice functions on a collection of
non-empty sets, ordered by restriction.
* The set of all
prime ideal
In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together with ...
s of a
ring, ordered by inclusion.
* The set of all
consistent theories of a
first-order language.
Properties
A poset is chain-complete if and only if it is a
pointed dcpo.
However, this equivalence requires the
axiom of choice.
Zorn's lemma states that, if a poset has an upper bound for every chain, then it has a
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 defin ...
. Thus, it applies to chain-complete posets, but is more general in that it allows chains that have upper bounds but do not have least upper bounds.
Chain-complete posets also obey the
Bourbaki–Witt theorem, a
fixed point theorem
In mathematics, a fixed-point theorem is a result saying that a function ''F'' will have at least one fixed point (a point ''x'' for which ''F''(''x'') = ''x''), under some conditions on ''F'' that can be stated in general terms. Some authors clai ...
stating that, if ''f'' is a
function from a chain complete poset to itself with the property that ''f''(''x'') ≥ ''x'' for all ''x'', then ''f'' has a
fixed point. This theorem, in turn, can be used to
prove
Proof most often refers to:
* Proof (truth), argument or sufficient evidence for the truth of a proposition
* Alcohol proof, a measure of an alcoholic drink's strength
Proof may also refer to:
Mathematics and formal logic
* Formal proof, a con ...
that Zorn's lemma is a consequence of the axiom of choice.
[.]
By analogy with the
Dedekind–MacNeille completion of a partially ordered set, every partially ordered set can be extended uniquely to a minimal chain-complete poset.
See also
*
Completeness (order theory)
References
{{DEFAULTSORT:Chain Complete
Order theory