In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). 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. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... 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. ... 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. ... Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science | Academic disciplines ... The term lattice derives from the shape of the Hasse diagrams that result from depicting these orders. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ...

Complete lattices must not be confused with complete partial orders (cpos), which constitute a strictly more general class of partially ordered sets. More specific complete lattices are complete Boolean algebras and complete Heyting algebras (locales). In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. ... A complete boolean algebra is a collection of boolean operators which permits the realisation of any possible truth table. ... In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. ...

Formal definition

A partially ordered set (L, ≤) is a complete lattice if every subset A of L has both a greatest lower bound (infimum, meet) and a least upper bound (supremum, join). These are denoted by: In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... 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 ⊇ X... 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. ... 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. ...

A (meet) and A (join).

Note that in the special case where A is the empty set the meet of A will be the greatest element of L. Likewise, the join of the empty set yields the least element. Since the definition also assures the existence of binary meets and joins, complete lattices do thus form a special class of bounded lattices. In mathematics, the empty set is the set with no elements. ... 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. ... 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. ... See lattice for other mathematical as well as non-mathematical meanings of the term. ...

More implications of the above definition are discussed in the article on completeness properties in order theory. In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ...

Complete semilattices

It is a well-known fact of order theory that arbitrary meets can be expressed in terms of arbitrary joins and vice versa (for details, see completeness (order theory)). In effect, this means that it is sufficient to require the existence of either all meets or all joins to obtain the class of all complete lattices. In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ...

As a consequence, some authors use the terms complete meet-semilattice or complete join-semilattice as another way to refer to complete lattices. Though similar on objects, the terms entail different notions of homomorphisms, as will be explained in the below section on morphisms. 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. ... 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. ... In abstract algebra, a homomorphism is a map from one algebraic structure to another of the same type that preserves all the relevant structure. ...

On the other hand, some authors have no use for this distinction of morphisms (especially since the emerging concepts of "complete semilattice morphisms" can as well be specified in general terms). Consequently, complete meet-semilattices have also been defined as those meet-semilattices that are also complete partial orders. This concept is arguably the "most complete" notion of a meet-semilattice that is not yet a lattice (in fact, only the top element may be missing). This discussion is also found in the article on semilattices. 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. ... In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. ... In mathematical order theory, a semilattice is a partially ordered set (poset) within which either all binary sets have either a supremum (join) or all binary sets have an infimum (meet). ...

Examples

• The power set of a given set, ordered by inclusion. The supremum is given by the union and the infimum by the intersection of subsets.
• The unit interval [0,1] and the extended real number line, with the familiar total order and the ordinary suprema and infima. Indeed, a totally ordered set (with its order topology) is compact as a topological space if it is complete as a lattice.
• The non-negative integers, ordered by divisibility. The least element of this lattice is the number 1, since it divides any other number. Maybe surprisingly, the greatest element is 0, because it can be divided by any other number. The supremum of finite sets is given by the least common multiple and the infimum by the greatest common divisor. For infinite sets, the supremum will always be 0 while the infimum can well be greater than 1. For example, the set of all even numbers has 2 as the greatest common divisor. If 0 is removed from this structure it remains a lattice but ceases to be complete.
• The submodules of a module, ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection.
• The ideals of a ring, ordered by inclusion. The supremum is given by the sum of ideals and the infimum by the intersection.
• The open sets of a topological space, ordered by inclusion. The supremum is given by the union of open sets and the infimum by the interior of the intersection.
• The convex subsets of a real or complex vector space, ordered by inclusion. The infimum is given by the intersection of convex sets and the supremum by the convex hull of the union.
• The topologies on a set, ordered by inclusion. The infimum is given by the intersection of topologies, and the supremum by the topology generated by the union of topologies.
• The lattice of all transitive relations on a set.
• The lattice of all sub-multisets of a multiset.
• The lattice of all equivalence relations on a set; the equivalence relation ~ is considered to be smaller (or "finer") than ≈ if x~y always implies x≈y.

In mathematics, a set S, the power set of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In mathematics, inclusion is a partial order on sets. ... 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. ... In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ... In mathematics, the unit interval is the interval [0,1], that is the set of all real numbers x such that zero is less than or equal to x and x is less than or equal to one. ... The extended real number line is obtained from the real number line R by adding two elements: +∞ and −∞ (which are not considered to be real numbers). ... 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. ... 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. ... In mathematics, the order topology is a topology that can be defined on any totally ordered set. ... Several specialized usages of the terms compact and compactness exist. ... Topological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... 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. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ... In abstract algebra, a module is a generalization of a vector space. ... In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers like even number or multiple of 3. For instance, in rings one studies prime ideals instead of prime numbers, one defines coprime ideals as a generalization of... In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have similar (but not identical) properties to those familiar from the integers. ... Topological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. ... In mathematics, the interior of a set S consists of all points which are intuitively not on the edge of S. A point which is in the interior of S is an interior point of S. The notion of interior is in many ways dual to the notion of closure. ... In mathematics, an object is convex if for any pair of points within the object, any point on the straight line segment that joins them is also within the object. ... In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ... In mathematics, the complex numbers are an extension of the real numbers by the inclusion of the imaginary unit i, satisfying . ... A vector space (or linear space) is the basic object of study in the branch of mathematics called linear algebra. ... In mathematics, the convex hull for an object or a set of objects is the minimal convex set containing the given objects. ... Topological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ... In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a cardinal number indicating (loosely speaking) how many times it is a member, or perhaps how many memberships it has in the multiset. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...

Morphisms of complete lattices

The traditional morphisms between complete lattices are the complete homomorphisms (or complete lattice homomorphisms). These are characterized as functions that preserve all joins and all meets. Explicitly, this means that a function f: L→M between two complete lattices L and M is a complete homomorphism if In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i. ...

• and
• ,

for all subsets A of L. Such functions are automatically monotonic, but the condition of being a complete homomorphism is in fact much more specific. For this reason, it can be useful to consider weaker notions of morphisms, that are only required to preserve all meets or all joins, which are indeed no equivalent conditions. This notion may be considered as a homomorphism of complete meet-semilattices or complete join-semilattices, respectively. In mathematics, functions between ordered sets are monotonic (or monotone) if they preserve the given order. ...

Furthermore, morphisms that preserve all joins are equivalently characterized as the lower adjoint part of a unique Galois connection. Each of these determines a unique upper adjoint in the inverse direction that preserves all meets. Hence, considering complete lattices with complete semilattice morphisms boils down to considering Galois connections as morphisms. This also yields the insight that the introduced morphisms do basically describe just two different categories of complete lattices: one with complete homomorphisms and one with meet-preserving functions (upper adjoints), dual to the one with join-preserving mappings (lower adjoints). 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. ... Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same. There are numerous examples of categorical equivalences from many areas of mathematics. ...

Free construction and completion

Free "complete semilattices"

As usual, the construction of free objects depends on the chosen class of morphisms. Let us first consider functions that preserve all joins (i.e. lower adjoints of Galois connections), since this case is simpler than the situation for complete homomorphisms. Using the aforementioned terminology, this could be called a free complete join-semilattice. The idea of a free object in mathematics is one of the basics of abstract algebra. ...

Using the standard definition from universal algebra, a free complete lattice over a generating set S is a complete lattice L together with a function i:S→L, such that any function f from S to the underlying set of some complete lattice M can be factored uniquely through a morphism f° from L to M. Stated differently, for every element s of S we find that f(s) = f°(i(s)) and that f° is the only morphism with this property. These conditions basically amount to saying that there is a functor from the category of sets and functions to the category of complete lattices and join-preserving functions which is left adjoint to the forgetful functor from complete lattices to their underlying sets. Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ... The existence of many pairs of adjoint functors is a major observation of the branch of mathematics known as category theory. ... A forgetful functor is a type of functor in mathematics. ...

Free complete lattices in this sense can be constructed very easily: the complete lattice generated by some set S is just the powerset 2^S, i.e. the set of all subsets of S, ordered by subset inclusion. The required unit i:S→2^S maps any element s of S to the singleton set {s}. Given a mapping f as above, the function f°:2^S→M is defined by 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. ... 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 ⊇ X...

f°(X) = {f(s)|s in X}.

It is obvious that f° transforms unions into suprema and thus preserves joins.

Our considerations also yield a free construction for morphisms that do preserve meets instead of joins (i.e. upper adjoints of Galois connections). In fact, we merely have to dualize what was said above: free objects are given as powersets ordered by reverse inclusion, such that set union provides the meet operation, and the function f° is defined in terms of meets instead of joins. The result of this construction could be called a free complete meet-semilattice. One should also note how these free constructions extend those that are used to obtain free semilattices, where we only need to consider finite sets. 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. ... In mathematical order theory, a semilattice is a partially ordered set (poset) within which either all binary sets have either a supremum (join) or all binary sets have an infimum (meet). ...

Free complete lattices

The situation for complete lattices with complete homomorphisms obviously is more intricate. In fact, free complete lattices do generally not exist. Of course, one can formulate a word problem similar to the one for the case of lattices, but the collection of all possible "words" (or "terms") in this case would be a proper class, because arbitrary meets and joins comprise operations for argument-sets of every cardinality. The term lattice derives from the shape of the Hasse diagrams that result from depicting these orders. ... In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. ... The cardinality of a set is a property that describes the size of the set by describing it using a cardinal number. ...

This property in itself is not a problem: as the case of free complete semilattices above shows, it can well be that the solution of the word problem leaves only a set of equivalence classes. In other words, it is possible that proper classes of the class of all terms have the same meaning and are thus identified in the free construction. However, the equivalence classes for the word problem of complete lattices are "too small", such that the free complete lattice would still be a proper class, which is not allowed.

Now one might still hope that there are some useful cases where the set of generators is sufficiently small for a free complete lattice to exist. Unfortunatelly, the size limit is very low and we have the following theorem:

The free complete lattice on three generators does not exist (is a proper class).

A proof of this statement can be found in paragraph 4.7 of P. T. Johnstone: Stone Spaces, Cambridge University Press, 1982, where the original argument is attributed to A. W. Hales: On the non-existence of free complete Boolean algebras, Fundamenta Mathematica 54, 45-66. The Fundamenta Mathematicae is a mathematical research journal with special focus on the foundations of mathematics. ...

Completion

If a complete lattice is freely generated from a given poset used in place of the set of generators considered above, then one speaks of a completion of the poset. The definition of the result of this operation is similar to the above definition of free objects, where "sets" and "functions" are replaced by "posets" and "monotone mappings". Likewise, one can describe the completion process as a functor from the category of posets with monotone functions to some category of complete lattices with appropriate morphisms that is left adjoint to the forgetful functor in the converse direction.

As long as one considers meet- or join-preserving functions as morphisms, this can easily be achieved through the so-called Dedekind-MacNeille completion. For this process, elements of the poset are mapped to (Dedekind-) cuts, which can then be mapped to the underlying posets of arbitrary complete lattices in much the same way as done for sets and free complete (semi-) lattices above. In mathematics, a Dedekind cut in a totally ordered set S is a partition of it, (A, B), such that A is closed downwards (meaning that for any element x in S, if a is in A and x ≤ a, then x is in A as well) and B is...

The aforementioned result that free complete lattices do not exist entails that an according free construction from a poset is not possible either. This is easily seen by considering posets with a discrete order, where every element only relates to itself. These are exactly the free posets on an underlying set. Would there be a free construction of complete lattices from posets, then both constructions could be composed, which contradicts the negative result above.

Representation

There are various other mathematical concepts that can be used to represent complete lattices. One means of doing so is the Dedekind-MacNeille completion. When this completion is applied to a poset that already is a complete lattice, then the result is a complete lattice of sets which is isomorphic to the original one. Thus we immediately find that every complete lattice is isomorphic to a complete lattice of sets. In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets. ...

Another representation is obtained by noting that the image of any closure operator on a complete lattice is again a complete lattice (called its closure system). Since the identity function is a closure operator too, this shows that the complete lattices are exactly the images of closure operators on complete lattices. Now the Dedekind-MacNeille completion can also be cast into a closure operator: every set of elements is mapped to the least lower (or upper) Dedekind cut that contains this set. Such a least cut does indeed exist and one has a closure operator on the powerset lattice of all elements. In summary, one can say that every complete lattice is isomorphic to the image of a closure operator on a powerset lattice. In mathematics, given a partially ordered set (P, ≤), a closure operator on P is a function C : P → P with the following properties: if x ≤ y, then C(x) ≤ C(y), i. ... In mathematics, a Dedekind cut in a totally ordered set S is a partition of it, (A, B), such that A is closed downwards (meaning that for any element x in S, if a is in A and x ≤ a, then x is in A as well) and B is...

This in turn is utilized in formal concept analysis, where one uses binary relations (called formal contexts) to represent such closure operators. Formal concept analysis is a method of data analysis that takes an input matrix specifying a set of objects and the properties thereof, and finds both all the natural clusters of properties and all the natural clusters of objects in the input data, where a natural property cluster is a...

Further results

Besides the previous representation results, there are some other statements that can be made about complete lattices, or that take a particularly simple form in this case. An example is the Knaster-Tarski theorem, which states that the set of fixed points of a monotone function on a complete lattice is again a complete lattice. This is easily seen to be a generalization of the above observation about the images of closure operators, since these are exactly the sets of fixed points of such operators. In the mathematical areas of order and lattice theory, the Knaster-Tarski theorem, named after Bronislaw Knaster and Alfred Tarski, states the following: Let L be a complete lattice and let f : L → L be an order-preserving function. ... In mathematics, a fixed point of a function f is an argument x such that f(x) = x; see fixed point (mathematics). ...

Literature

See the article lattice (order). The term lattice derives from the shape of the Hasse diagrams that result from depicting these orders. ...