In mathematics, specifically

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

, 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 binar ...

is chain-complete if every

chain A chain is a wikt:series#Noun, 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 (physics), compression but line (g ...

in it has a

least upper bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...

. It is ω-complete when every increasing

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...

of elements (a type of

countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...

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

lattice is chain-complete. Unlike complete lattices, chain-complete posets are relatively common. Examples include: * The set of all

linearly independent In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts ...

subset In mathematics, set ''A'' is a subset of a set ''B'' if all 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 unequal, then ''A'' is a proper subset o ...

s of a

vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...

''V'', ordered by inclusion. * The set of all

partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is ...

s 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 ideals of a ring, ordered by inclusion. * The set of all

consistent In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consisten ...

theories A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be ...

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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...

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

. 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 In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed point theorem for partially ordered sets. It states that if ''X'' is a non-empty chain complete poset, and f : X \to X s ...

, 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 In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and construc ...

of a partially ordered set, every partially ordered set can be extended uniquely to a minimal chain-complete poset.

References

{{DEFAULTSORT:Chain Complete Order theory

Examples

Properties

See also

References