In the Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. One reason is that... mathematical area of Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. This article gives a detailed introduction to the field and includes some of the most basic definitions. For a quick lookup of order theoretic terms, there is... order theory, completeness properties assert the existence of certain In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is smaller than all other elements of the subset. Consequently the term greatest lower bound is also commonly used. Infima of real numbers are a common special case that is... infima or In mathematics, the supremum of an ordered set S is the least element (not necessarily in S) which is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound. If the set contains a greatest element, then that element is... suprema of a given partially ordered set. In a more special usage of the term one also talks about In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. These orders, called dcpos and cpos for short, are characterized by particular completeness properties. Both dcpos and cpos are considered in domain theory and have major applications in theoretical computer science and denotational... complete partial orders or See lattice for other mathematical as well as non-mathematical meanings of the term. In mathematics, a lattice is a poset (i.e. a partially ordered set), in which all nonempty finite subsets have both a supremum (join) and an infimum (meet). On the other hand, lattices can also be... complete lattices. However, many other interesting notions of completeness exist. This article gives an overview and discusses the relationships among those properties.

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 In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. If there is no such positive integer, e.g., if a ... least common multiple of a set of numbers or the In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. This article uses mathematical symbols. Basic definition The union of A and B If A and B are sets... 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 In abstract algebra, an algebraic structure consists of a set together with a collection of operations or relations defined on it which satisfy certain axioms. When there are no ambiguities, we usually identify the set with the algebraic structure. For example, a group (G,*) is usually referred simply as a... 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 partial order that are required to have a supremum or infimum. Hence every completeness property has its In the mathematical area of order theory, every partially ordered set P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop... 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 In mathematics, the empty set is the set with no elements. Notation The standard notation for denoting the empty set, invented by Nicholas Bourbaki, is the symbol , also written as or ∅, and sometimes approximated by the glyph Ø, (not to be confused with the Greek letter φ). However, for wider... 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 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. Formally, given a partially ordered set (P, ≤... 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 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. Formally, given a partially ordered set (P, ≤... 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 finite sets have both a supremum and an infimum is called a See lattice for other mathematical as well as non-mathematical meanings of the term. In mathematics, a lattice is a poset (i.e. a partially ordered set), in which all nonempty finite subsets have both a supremum (join) and an infimum (meet). On the other hand, lattices can also be... lattice. 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 Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. A somewhat more general form of argument used in mathematical logic and computer science shows that expressions... 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 v. It is in this context that the terms meet for ^ and join for v are most common.

A poset in which only non-empty finite suprema are known to exist is therefore called a In mathematical order theory, a semilattice is a partially ordered set (poset) within which all binary sets have a supremum (join) or infimum (meet), respectively. Consequently, one speaks of either a join-semilattice or a meet-semilattice. Semilattices provide a generalization of the more prominent concept of a lattice and... join-semilattice. The dual notion is In mathematical order theory, a semilattice is a partially ordered set (poset) within which all binary sets have a supremum (join) or infimum (meet), respectively. Consequently, one speaks of either a join-semilattice or a meet-semilattice. Semilattices provide a generalization of the more prominent concept of a lattice and... 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 See lattice for other mathematical as well as non-mathematical meanings of the term. In mathematics, a lattice is a poset (i.e. a partially ordered set), in which all nonempty finite subsets have both a supremum (join) and an infimum (meet). On the other hand, lattices can also be... 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 In mathematics, a directed set is a set A together with a binary relation ≤ having the following properties: a ≤ a for all a in A (reflexivity) if a ≤ b and b ≤ c, then a ≤ c (transitivity) for any two a and b in A, there... directed subsets of a poset have a supremum, then the order is a In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. These orders, called dcpos and cpos for short, are characterized by particular completeness properties. Both dcpos and cpos are considered in domain theory and have major applications in theoretical computer science and denotational... directed complete partial order or dcpo. These are especially important in 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 semantics, especially for functional programming... domain theory. The seldom considered dual notion of a dcpo is the filtered complete poset. Dcpos with a least element ("pointed dcpos") are called In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. These orders, called dcpos and cpos for short, are characterized by particular completeness properties. Both dcpos and cpos are considered in domain theory and have major applications in theoretical computer science and denotational... 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 In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets which have some upper bound also have a least upper bound. Such a partial order can also be called consistently complete, since any upper bound of a set can be interpreted... 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 In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. This means that, if we denote the relation by ≤, the following statements hold for all a, b and c in X: if a ≤ b... 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.

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 In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. It is often, not always, written italicized: iff. Although P iff Q is most standard, common alternative phrases include P is necessary and sufficient for Q and P... iff 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 In mathematics, the axiom of choice is an axiom of set theory. It was formulated about a century ago by Ernst Zermelo and has remained controversial to this day. It states the following: Let X be a collection of non-empty sets. Then we can choose a member from each... Axiom of Choice:

A poset is chain-complete iff it is a dcpo.

Can anybody give a proof of this proposition?

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 In abstract algebra, an algebraic structure consists of a set together with a collection of operations or relations defined on it which satisfy certain axioms. When there are no ambiguities, we usually identify the set with the algebraic structure. For example, a group (G,*) is usually referred simply as a... algebraic structures in the sense of Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. Basic idea From the point of view of universal algebra, an algebra is a set A together with a collection of operations on A. An n-ary operation on A is a function that... universal algebra, which are equipped with operations like or . By imposing additional conditions (in form of suitable In philosophy, identity is the quality of being the same as. It is of particular interest to logicians and metaphysicians. Logic In logic, the identity relation is normally, (by definition), the transitive, symmetric, and reflexive relation that holds only between a thing and itself. That is, identity is the two... 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 In mathematical order theory, a semilattice is a partially ordered set (poset) within which all binary sets have a supremum (join) or infimum (meet), respectively. Consequently, one speaks of either a join-semilattice or a meet-semilattice. Semilattices provide a generalization of the more prominent concept of a lattice and... semilattice, See lattice for other mathematical as well as non-mathematical meanings of the term. In mathematics, a lattice is a poset (i.e. a partially ordered set), in which all nonempty finite subsets have both a supremum (join) and an infimum (meet). On the other hand, lattices can also be... lattice, In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. Heyting algebras arise as models of intuitionistic logic, a logic in which the law of excluded middle does not in general hold. Complete Heyting algebras are a central object of study in pointless topology... Heyting algebra, and In mathematics and computer science, Boolean algebras, or Boolean lattices, are algebraic structures which capture the essence of the logical operations AND, OR and NOT as well as the corresponding set theoretic operations intersection, union and complement. They are named after George Boole, an English mathematician at University College Cork... 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 and way to characterize completeness properties is provided through the concept of (monotone) In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. They find applications in various mathematical theories as well as in the theory of programming. A Galois connection... Galois connections, 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 In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. It is often, not always, written italicized: iff. Although P iff Q is most standard, common alternative phrases include P is necessary and sufficient for Q and P... iff the function j has a lower adjoint j^*: 1 → X. Indeed the definition for Galois connections yields that in this case j^*(*) ≤ x iff * ≤ 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^* iff 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 iff 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 In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. Heyting algebras arise as models of intuitionistic logic, a logic in which the law of excluded middle does not in general hold. Complete Heyting algebras are a central object of study in pointless topology... 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 A is a subset of B If X and Y are sets and every element of X is also an element of Y, then we say or write: X is a subset of (or is included in) Y; X ⊆ Y; Y is a superset of (or includes) X; Y... 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 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. Ideals are of great importance for many constructions in order... principal ideal {y in X | y ≤ x}. A little reflection now shows that e has a lower adjoint iff 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 In mathematics, given a set S, the power set of S, written P(S) or 2S, is the set of all subsets of S. In formal language, the existence of power set of any set is presupposed by the axiom of power set. In this case S is usually called... powerset), 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 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... distributivity (order theory).

The considerations in this section suggest a reformulation of (parts of) order theory in terms of Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. It is half-jokingly known as generalized abstract nonsense. The use of this phrase does not mean that mathematicians consider category theory to be fuzzy or non-rigorous, merely that a... category theory, where properties are usually expressed by referring to the relationships ( In mathematics, a morphism is an abstraction of a function or mapping between two spaces. The word can mean different things depending on the type of space in question. In set theory, for example, morphisms are just functions, in group theory they are group homomorphisms, while in topology they are... 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

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... limit-preserving function (order theory) on the preservation of existing suprema/infima.

Literature

Notions of completeness are standard and can be found in any textbook in this area. See especially the literature for Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. This article gives a detailed introduction to the field and includes some of the most basic definitions. For a quick lookup of order theoretic terms, there is... order theory.