Completeness (order theory)

Last updated

In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist.

Contents

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

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 lattices. 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, i.e. the chains. If all chains have a supremum, the order is called chain 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.

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

Completeness in terms of adjunctions

Another interesting way to characterize completeness properties is provided through the concept of (monotone) Galois connections, 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: XX × 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 : X × XX 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: XD(X) that maps each element x of X to its principal ideal {y in X | yx}. 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), 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 (morphisms, 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

Notes

    Related Research Articles

    In mathematics, the infimum of a subset of a partially ordered set is a greatest element in that is less than or equal to each element of if such an element exists. Consequently, the term greatest lower bound is also commonly used.

    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. Specifically, every non-empty finite lattice is complete. Complete lattices appear in many applications in mathematics and computer science. Being a special instance of lattices, they are studied both in order theory and universal algebra.

    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 fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.

    Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) 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 semantics, especially for functional programming languages. Domain theory formalizes the intuitive ideas of approximation and convergence in a very general way and is closely related to topology.

    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 introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

    This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

    A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

    In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets

    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. Depending on the type of sets for which a function satisfies this property, it may preserve finite, directed, non-empty, or just arbitrary suprema or infima. Each of these requirements appears naturally and frequently in many areas of order theory and there are various important relationships among these concepts and other notions such as monotonicity. If the implication of limit preservation is inverted, such that the existence of limits in the range of a function implies the existence of limits in the domain, then one obtains functions that are limit-reflecting.

    In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). 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. Ideals are of great importance for many constructions in order and lattice theory.

    In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science: in denotational semantics and domain 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 concept can in fact reasonably be generalized to semilattices as well.

    In the mathematical area of order theory, the compact elements or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element. This notion of compactness simultaneously generalizes the notions of finite sets in set theory, compact sets in topology, and finitely generated modules in algebra.

    In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded-complete cpo. They are named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory. Scott domains are very closely related to algebraic lattices, being different only in possibly lacking a greatest element. They are also closely related to Scott information systems, which constitute a "syntactic" representation of Scott domains.

    In mathematics, a join-semilattice is a partially ordered set that 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. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

    In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum. Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolean algebra A has an essentially unique completion, which is a complete Boolean algebra containing A such that every element is the supremum of some subset of A. As a partially ordered set, this completion of A is the Dedekind–MacNeille completion.

    <span class="mw-page-title-main">Join and meet</span>

    In mathematics, specifically order theory, the join of a subset of a partially ordered set is the supremum of denoted and similarly, the meet of is the infimum, denoted In general, the join and meet of a subset of a partially ordered set need not exist. Join and meet are dual to one another with respect to order inversion.

    In the mathematics of matroids and lattices, a geometric lattice is a finite atomistic semimodular lattice, and a matroid lattice is an atomistic semimodular lattice without the assumption of finiteness. Geometric lattices and matroid lattices, respectively, form the lattices of flats of finite and infinite matroids, and every geometric or matroid lattice comes from a matroid in this way.

    In order theory, a continuous poset is a partially ordered set in which every element is the directed supremum of elements approximating it.

    References