HOME

TheInfoList



OR:

In the
mathematical 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 ...
area of
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 ...
, completeness properties assert the existence of certain
infima 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 ...
or
suprema 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 low ...
of a given
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 ...
(poset). The most familiar example is the
completeness of the real numbers Completeness is a property of the real numbers that, intuitively, implies that there are no "gaps" (in Dedekind's terminology) or "missing points" in the real number line. This contrasts with the rational numbers, whose corresponding number l ...
. A special use of the term refers to complete partial orders or
complete lattice In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
s. However, many other interesting notions of completeness exist. The motivation for considering completeness properties derives from the great importance of
suprema 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 low ...
(least upper bounds, joins, "\vee") and
infima 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 ...
(greatest lower bounds, meets, "\wedge") to the theory of partial orders. Finding a supremum means to single out one distinguished least element from the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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 In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by ...
of a set of numbers or the union of a collection of sets). On the other hand, the knowledge that certain types of
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 of ...
s 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,
poset 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 r ...
s with certain completeness properties can often be described as
algebraic structure In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
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 Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differently ...
of subsets of a partially ordered set that are required to have a supremum or required to have an infimum. Hence every completeness property has its dual, 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 set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in othe ...
. 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, if it has one, since the empty subset of a poset ''P'' is conventionally considered to be both bounded from above and from below, with every element of ''P'' being both an upper and lower bound of the empty subset. 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.


Finite completeness

Further simple completeness conditions arise from the consideration of all non-empty
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...
s. An order in which all non-empty finite sets have both a supremum and an infimum is called a lattice. It suffices to require that all suprema and infima of ''two'' elements exist to obtain all non-empty finite ones; a straightforward induction argument 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 \vee and infima It is in this context that the terms meet for \wedge and join for \vee 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.


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 lattice In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
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 (dcpo). These are especially important in domain theory. The seldom-considered dual notion to a dcpo is the filtered-complete poset. Dcpos with a least element ("pointed dcpos") are one of the possible meanings of the phrase complete partial order (cpo). If every subset that has ''some'' upper bound 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 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 ( reflexive ...
, i.e. the
chains 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. ...
. If all chains have a supremum, the order is called
chain complete In mathematics, specifically order theory, a partially ordered set is chain-complete if every chain 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; ...
. 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 best-known example is the existence of all suprema, which is in fact equivalent to the existence of all infima, provided a bottom exists. Indeed, for any subset ''X'' of a poset, one can consider its set of lower bounds ''B'', which is not empty since it contains at least the bottom. 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 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 infima. * A poset is a complete lattice
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
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. * Assuming 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 ...
, a poset is chain complete if and only if it is a dcpo.


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 a partially ordered set. It turns out that in many cases it is possible to characterize completeness solely by considering appropriate
algebraic structure In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
s in the sense of
universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular groups as the object of study ...
, which are equipped with operations like \vee or \wedge. 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 In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
. 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 connection In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the funda ...
s, i.e. adjunctions between partial orders. In fact this approach offers additional insights both into the nature of many completeness properties and into 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''. ''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'' given by ''q''(''x'') = (''x'', ''x''). Naturally, the intended ordering relation for ''X'' × ''X'' is just the usual product order. ''q'' has a lower adjoint ''q''* if and only if all binary joins in ''X'' exist. Conversely, the join operation \vee: ''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 \wedge, if it exists, always is an upper adjoint. If both \vee and \wedge exist and, in addition, \wedge 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 set In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
s 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 In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
. 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 lower adjoint 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 In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
), one obtains the usual supremum map from the powerset 2''X'' 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) 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. Most of these apply to partially ordered sets that are at least lattices, but the concep ...
. The considerations in this section suggest a reformulation of (parts of) order theory in terms of
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, where properties are usually expressed by referring to the relationships (
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
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 function on the ''preservation'' of existing suprema/infima. *


Notes


References

* G. Markowsky and B.K. Rosen. ''Bases for chain-complete posets'' IBM Journal of Research and Development. March 1976. * Stephen Bloom. ''Varieties of ordered algebras'' Journal of Computer and System Sciences. October 1976. * Michael Smyth. ''Power domains'' Journal of Computer and System Sciences. 1978. * Daniel Lehmann. ''On the algebra of order'' Journal of Computer and System Sciences. August 1980. {{Order theory Order theory