Completeness (order theory)
Encyclopedia
In the mathematical
area of order theory
, completeness properties assert the existence of certain infima
or suprema
of a given partially ordered set (poset). A special use of the term refers to complete partial order
s or complete lattice
s. However, many other interesting notions of completeness exist.
The motivation for considering completeness properties derives from the great importance of suprema (least upper bounds, joins, "
") and infima (greatest lower bounds, meets
, "
") to the theory of partial orders. Finding a supremum means to single out one distinguished least element from the set of upper bounds. On the one hand, these special elements often embody certain concrete properties that are interesting for the given application (such as being the least common multiple
of a set of numbers or the union
of a collection of sets). On the other hand, the knowledge that certain types of subsets are guaranteed to have suprema or infima enables us to consider the computation of these elements as total operations on a partially ordered set. For this reason, posets with certain completeness properties can often be described as algebraic structure
s of a certain kind. In addition, studying the properties of the newly obtained operations yields further interesting subjects.
, obtained by inverting the order-dependent definitions in the given statement. Some of the notions are usually not dualized while others may be self-dual (i.e. equivalent to their dual statements).
. By definition, this is the least element among all elements that are greater than each member of the empty set. But this is just the least element of the whole poset. Other common names for the least element are bottom and zero (0). The dual notion, the empty lower bound, is the greatest element
, top, or unit (1).
Posets that have a bottom are sometimes called pointed, while posets with a top are called unital or topped. An order that has both a least and a greatest element is bounded. However, this should not be confused with the notion of bounded completeness given below.
. It is easy to see that it suffices to require that all suprema and infima of two elements exist to obtain all finite ones. A straightforward induction
shows that every finite non-empty supremum/infimum can be decomposed into a finite number of binary suprema/infima. Thus the central operations of lattices are binary suprema
and infima 
. It is in this context that the terms meet for 
and join for 
are most common.
A poset in which only non-empty finite suprema are known to exist is therefore called a join-semilattice
. The dual notion is meet-semilattice
.
s. However, using the given order, one can restrict to further classes of (possibly infinite) subsets, that do not yield this strong completeness at once.
If all directed subsets
of a poset have a supremum, then the order is a directed complete partial order or dcpo. These are especially important in domain theory
. The seldom considered dual notion of a dcpo is the filtered complete poset. Dcpos with a least element ("pointed dcpos") are called complete partial order
or cpo.
If every subset that has some upper bounds has also a least upper bound, then the respective poset is called bounded complete. The term is used widely with this definition that focuses on suprema and there is no common name for the dual property. However, bounded completeness can be expressed in terms of other completeness conditions that are easily dualized (see below). Although concepts with the names "complete" and "bounded" were already defined, confusion is unlikely to occur since one would rarely speak of a "bounded complete poset" when meaning a "bounded cpo" (which is just a "cpo with greatest element"). Likewise, "bounded complete lattice" is almost unambiguous, since one would not state the boundedness property for complete lattices, where it is implied anyway. Also note that the empty set usually has upper bounds (if the poset is non-empty) and thus a bounded complete poset has a least element.
One may also consider the subsets of a poset which are totally ordered
, i.e. the chains. If all chains have a supremum, the order is called chain-complete (sometimes also "omega-complete", written ω-complete). Again, this concept is rarely needed in the dual form.
often there is an intuitive sense in which some elements of partially ordered sets are finite. E.g., in denotational semantics
, they may be partial functions defined for only finitely many values or they may be finite partial computations in the Actor model
. This sense of finiteness lies behind the following abstract definition:
The least element of a partially ordered set is always isolated provided it exists. 0 is the least element of the nonnegative rationals under the usual ordering, and it is also the only isolated element. The entire set of rationals has no isolated elements under the usual ordering.
For purposes of programming language semantics, partially ordered sets with least elements form too general a category. The partially ordered sets of greatest interest for computer science are those whose isolated elements are dense in the sense that every element is a least upper bound of a countable set of isolated elements. To avoid transfinite induction, and to make directed completeness equivalent to ω-completeness, it is convenient to assume also that there are only countably many isolated elements which motivates the following definition.
The above definition is a generalization of the traditional definition. The traditional definition requires also that D be ω-complete, so that ω-continuous functions from D to D will have fixed points.
An ω-complete domain is complete in the sense that every directed subset has a least upper bound. An ω-complete domain is also known as a countably algebraic complete partial order [Smyth 1978].
Every domain D can be embedded in an ω-complete domain completion[D] (called the ω-completion or simply the completion of D) that is, in a precise sense, the smallest ω-complete domain containing D. The isolated elements of completion[D] are precisely the isolated elements of D, but in general completion[D] contains limit points that are not found in D. completion[D] is uniquely determined up to isomorphism. In Clinger [1981], it is shown that for any domain D the power domain of D is isomorphic to the power domain of completion[D]. So why not use ω-complete domains only, as is traditional? Because the power domain is interpreted with reference to the domain from which it is built. As explained in denotational semantics of concurrency, the underlying domain is incomplete in Actor semantics
.
s in the sense of universal algebra
, which are equipped with operations like
or 
. By imposing additional conditions (in form of suitable identities
) on these operations, one can then indeed derive the underlying partial order exclusively from such algebraic structures. Details on this characterization can be found in the articles on the "lattice-like" structures for which this is typically considered: see semilattice
, lattice
, Heyting algebra
, and Boolean algebra. Note that the latter two structures extend the application of these principles beyond mere completeness requirements by introducing an additional operation of negation.
s, i.e. adjunctions between partial orders. In fact this approach offers additional insights both in the nature of many completeness properties and in the importance of Galois connections for order theory. The general observation on which this reformulation of completeness is based is that the construction of certain suprema or infima provides left or right adjoint parts of suitable Galois connections.
Consider a partially ordered set (X, ≤). As a first simple example, let 1 = {*} be a specified one-element set with the only possible partial ordering. There is an obvious mapping j: X → 1 with j(x) = * for all x in X. Now it is easy to see that X has a least element if and only if
the function j has a lower adjoint j*: 1 → X. Indeed the definition for Galois connections yields that in this case j*(*) ≤ x if and only if * ≤ j(x), where the right hand side obviously holds for any x. Dually, the existence of an upper adjoint for j is equivalent to X having a greatest element.
Another simple mapping is the function q: X → (X x X) given by q(x) = (x, x). Naturally, the intended ordering relation for (X x X) is just the usual product order
. Now it is easy to see that q has a lower adjoint q* if and only if all binary joins in X exist. Conversely, the join operation
: (X x X) → X can always provide the (necessarily unique) lower adjoint for q. Dually, q allows for an upper adjoint if and only if X has all binary meets. Thus the meet operation 
, if it exists, always is an upper adjoint. If both 
and 
exist and, in addition, 
is also a lower adjoint, then the poset X is a Heyting algebra
-- another important special class of partial orders.
Further completeness statements can be obtained by exploiting suitable completion procedures. For example, it is well-known that the collection of all lower sets of a poset X, ordered by subset inclusion
, yields a complete lattice D(X) (the downset-lattice). Furthermore, there is an obvious embedding e: X → D(X) that maps each element x of X to its principal ideal
{y in X | y ≤ x}. A little reflection now shows that e has a lower adjoint if and only if X is a complete lattice. In fact, this lower adjoint will map any lower set of X to its supremum in X. Composing this with the function that maps any subset of X to its lower closure (again an adjunction for the inclusion of lower sets in the powerset), one obtains the usual supremum map from the powerset 2X to X. As before, another important situation occurs whenever this supremum map is also an upper adjoint: in this case the complete lattice X is constructively completely distributive. See also the articles on complete distributivity
and distributivity (order theory)
.
The considerations in this section suggest a reformulation of (parts of) order theory in terms of category theory
, where properties are usually expressed by referring to the relationships (morphism
s, more specifically: adjunctions) between objects, instead of considering their internal structure. For more detailed considerations of this relationship see the article on the categorical formulation of order theory.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
area of order theory
Order theory
Order theory is a branch of mathematics which investigates our 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 introduces the field and gives some basic definitions...
, completeness properties assert the existence of certain infima
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
or suprema
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
of a given partially ordered set (poset). A special use of the term refers to complete partial order
Complete partial order
In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...
s or complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
s. However, many other interesting notions of completeness exist.
The motivation for considering completeness properties derives from the great importance of suprema (least upper bounds, joins, "
") and infima (greatest lower bounds, meetsMeet (mathematics)
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
, "
") to the theory of partial orders. Finding a supremum means to single out one distinguished least element from the set of upper bounds. On the one hand, these special elements often embody certain concrete properties that are interesting for the given application (such as being the least common multipleLeast common multiple
In arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
of a set of numbers or the union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of a collection of sets). On the other hand, the knowledge that certain types of subsets are guaranteed to have suprema or infima enables us to consider the computation of these elements as total operations on a partially ordered set. For this reason, posets with certain completeness properties can often be described as algebraic structure
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
s of a certain kind. In addition, studying the properties of the newly obtained operations yields further interesting subjects.
Types of completeness properties
All completeness properties are described along a similar scheme: one describes a certain class of subsets of a partially ordered set that are required to have a supremum or infimum. Hence every completeness property has its dualDuality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
, obtained by inverting the order-dependent definitions in the given statement. Some of the notions are usually not dualized while others may be self-dual (i.e. equivalent to their dual statements).
Least and greatest elements
The easiest example of a supremum is the empty one, i.e. the supremum of the empty setEmpty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
. By definition, this is the least element among all elements that are greater than each member of the empty set. But this is just the least element of the whole poset. Other common names for the least element are bottom and zero (0). The dual notion, the empty lower bound, is the greatest element
Greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, top, or unit (1).
Posets that have a bottom are sometimes called pointed, while posets with a top are called unital or topped. An order that has both a least and a greatest element is bounded. However, this should not be confused with the notion of bounded completeness given below.
Finite completeness
Further simple completeness conditions arise from the consideration of all non-empty finite sets. An order in which all finite sets have both a supremum and an infimum is called a latticeLattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
. It is easy to see that it suffices to require that all suprema and infima of two elements exist to obtain all finite ones. A straightforward induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
shows that every finite non-empty supremum/infimum can be decomposed into a finite number of binary suprema/infima. Thus the central operations of lattices are binary suprema
and infima . It is in this context that the terms meet for and join for are most common.A poset in which only non-empty finite suprema are known to exist is therefore called a join-semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...
. The dual notion is meet-semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...
.
Further completeness conditions
The strongest form of completeness is the existence of all suprema and all infima. The posets with this property are the complete latticeComplete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
s. However, using the given order, one can restrict to further classes of (possibly infinite) subsets, that do not yield this strong completeness at once.
If all directed subsets
Directed set
In mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...
of a poset have a supremum, then the order is a directed complete partial order or dcpo. These are especially important in domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
. The seldom considered dual notion of a dcpo is the filtered complete poset. Dcpos with a least element ("pointed dcpos") are called complete partial order
Complete partial order
In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...
or cpo.
If every subset that has some upper bounds has also a least upper bound, then the respective poset is called bounded complete. The term is used widely with this definition that focuses on suprema and there is no common name for the dual property. However, bounded completeness can be expressed in terms of other completeness conditions that are easily dualized (see below). Although concepts with the names "complete" and "bounded" were already defined, confusion is unlikely to occur since one would rarely speak of a "bounded complete poset" when meaning a "bounded cpo" (which is just a "cpo with greatest element"). Likewise, "bounded complete lattice" is almost unambiguous, since one would not state the boundedness property for complete lattices, where it is implied anyway. Also note that the empty set usually has upper bounds (if the poset is non-empty) and thus a bounded complete poset has a least element.
One may also consider the subsets of a poset which are totally ordered
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, i.e. the chains. If all chains have a supremum, the order is called chain-complete (sometimes also "omega-complete", written ω-complete). Again, this concept is rarely needed in the dual form.
Relationships between completeness properties
It was already observed that binary meets/joins yield all non-empty finite meets/joins. Likewise, many other (combinations) of the above conditions are equivalent.- The most well-known example is the existence of all suprema, which is in fact equivalent to the existence of all infima. Indeed, for any subset X of a poset, one can consider its set of lower bounds B. The supremum of B is then equal to the infimum of X: since each element of X is an upper bound of B, sup B is smaller than all elements of X, i.e. sup B is in B. It is obvious that it is the greatest element of B and hence the infimum of X. In a dual way, the existence of all infima implies the existence of all suprema.
- Bounded completeness can also be characterized differently. By an argument similar to the above, one finds that the supremum of a set with upper bounds is the infimum of the set of upper bounds. Consequently, bounded completeness is equivalent to the existence of all non-empty lower bounded infima.
- A poset is a complete lattice if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
it is a cpo and a join-semilattice. Indeed, for any subset X, the set of all finite suprema (joins) of X is directed and the supremum of this set (which exists by directed completeness) is equal to the supremum of X. Thus every set has a supremum and by the above observation we have a complete lattice. The other direction of the proof is trivial.
- The following equivalence requires the Axiom of Choice:
-
- A poset is chain-complete if and only if it is a dcpo.
Completions of domains
According to Clinger [1981],often there is an intuitive sense in which some elements of partially ordered sets are finite. E.g., in denotational semantics
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
, they may be partial functions defined for only finitely many values or they may be finite partial computations in the Actor model
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
. This sense of finiteness lies behind the following abstract definition:
- Let (D, ≤) be a partially ordered set. An element x∈D is isolated if and only if whenever A⊆D is directed, ∪A exists and x≤∪A, there exists a∈A with x≤a. In other words, x is isolated if one must go through x to get up to or above x via the limit process. As examples, the finite sets are the isolated elements of the power set of ω ordered by inclusion; the ordinal ω+1 is isolated in the set of countable ordinals under the usual ordering.
The least element of a partially ordered set is always isolated provided it exists. 0 is the least element of the nonnegative rationals under the usual ordering, and it is also the only isolated element. The entire set of rationals has no isolated elements under the usual ordering.
For purposes of programming language semantics, partially ordered sets with least elements form too general a category. The partially ordered sets of greatest interest for computer science are those whose isolated elements are dense in the sense that every element is a least upper bound of a countable set of isolated elements. To avoid transfinite induction, and to make directed completeness equivalent to ω-completeness, it is convenient to assume also that there are only countably many isolated elements which motivates the following definition.
- Definition. A domain is a partially ordered set (D, ≤) such that
- D has a least element Λ
- Every element of D is the least upper bound of a countable increasing sequence of isolated elements.
- The isolated elements of D are countable.
The above definition is a generalization of the traditional definition. The traditional definition requires also that D be ω-complete, so that ω-continuous functions from D to D will have fixed points.
An ω-complete domain is complete in the sense that every directed subset has a least upper bound. An ω-complete domain is also known as a countably algebraic complete partial order [Smyth 1978].
Every domain D can be embedded in an ω-complete domain completion[D] (called the ω-completion or simply the completion of D) that is, in a precise sense, the smallest ω-complete domain containing D. The isolated elements of completion[D] are precisely the isolated elements of D, but in general completion[D] contains limit points that are not found in D. completion[D] is uniquely determined up to isomorphism. In Clinger [1981], it is shown that for any domain D the power domain of D is isomorphic to the power domain of completion[D]. So why not use ω-complete domains only, as is traditional? Because the power domain is interpreted with reference to the domain from which it is built. As explained in denotational semantics of concurrency, the underlying domain is incomplete in Actor semantics
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
.
Completeness in terms of universal algebra
As explained above, the presence of certain completeness conditions allows to regard the formation of certain suprema and infima as total operations of an ordered set. It turns out that in many cases it is possible to characterize completeness solely by considering appropriate algebraic structureAlgebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
s in the sense of universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
, which are equipped with operations like
or . By imposing additional conditions (in form of suitable identitiesIdentity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...
) on these operations, one can then indeed derive the underlying partial order exclusively from such algebraic structures. Details on this characterization can be found in the articles on the "lattice-like" structures for which this is typically considered: see semilattice
Semilattice
In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...
, lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
, Heyting algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
, and Boolean algebra. Note that the latter two structures extend the application of these principles beyond mere completeness requirements by introducing an additional operation of negation.
Completeness in terms of adjunctions
Another interesting way to characterize completeness properties is provided through the concept of (monotone) Galois connectionGalois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...
s, i.e. adjunctions between partial orders. In fact this approach offers additional insights both in the nature of many completeness properties and in the importance of Galois connections for order theory. The general observation on which this reformulation of completeness is based is that the construction of certain suprema or infima provides left or right adjoint parts of suitable Galois connections.
Consider a partially ordered set (X, ≤). As a first simple example, let 1 = {*} be a specified one-element set with the only possible partial ordering. There is an obvious mapping j: X → 1 with j(x) = * for all x in X. Now it is easy to see that X has a least element if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
the function j has a lower adjoint j*: 1 → X. Indeed the definition for Galois connections yields that in this case j*(*) ≤ x if and only if * ≤ j(x), where the right hand side obviously holds for any x. Dually, the existence of an upper adjoint for j is equivalent to X having a greatest element.
Another simple mapping is the function q: X → (X x X) given by q(x) = (x, x). Naturally, the intended ordering relation for (X x X) is just the usual product order
Product order
In mathematics, given two ordered sets A and B, one can induce a partial ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets ≤...
. Now it is easy to see that q has a lower adjoint q* if and only if all binary joins in X exist. Conversely, the join operation
: (X x X) → X can always provide the (necessarily unique) lower adjoint for q. Dually, q allows for an upper adjoint if and only if X has all binary meets. Thus the meet operation , if it exists, always is an upper adjoint. If both and exist and, in addition, is also a lower adjoint, then the poset X is a Heyting algebraHeyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
-- another important special class of partial orders.
Further completeness statements can be obtained by exploiting suitable completion procedures. For example, it is well-known that the collection of all lower sets of a poset X, ordered by subset inclusion
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
, yields a complete lattice D(X) (the downset-lattice). Furthermore, there is an obvious embedding e: X → D(X) that maps each element x of X to its principal ideal
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
{y in X | y ≤ x}. A little reflection now shows that e has a lower adjoint if and only if X is a complete lattice. In fact, this lower adjoint will map any lower set of X to its supremum in X. Composing this with the function that maps any subset of X to its lower closure (again an adjunction for the inclusion of lower sets in the powerset), one obtains the usual supremum map from the powerset 2X to X. As before, another important situation occurs whenever this supremum map is also an upper adjoint: in this case the complete lattice X is constructively completely distributive. See also the articles on complete distributivity
Completely distributive lattice
In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets....
and distributivity (order theory)
Distributivity (order theory)
In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima...
.
The considerations in this section suggest a reformulation of (parts of) order theory in terms of category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
, where properties are usually expressed by referring to the relationships (morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
s, more specifically: adjunctions) between objects, instead of considering their internal structure. For more detailed considerations of this relationship see the article on the categorical formulation of order theory.
See also
- Limit-preserving functionLimit-preserving function (order theory)In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set...
on the preservation of existing suprema/infima.