Complete lattice
Encyclopedia
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
.
Complete lattices must not be confused with complete partial order
s (cpos), which constitute a strictly more general class of partially ordered sets. More specific complete lattices are complete Boolean algebra
s and complete Heyting algebra
s (locales).
(L, ≤) is a complete lattice if every subset
A of L has both a greatest lower bound (the infimum
, also called the meet) and a least upper bound (the supremum
, also called the join) in (L, ≤).
The meet is denoted by
, and the join by 
.
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.
More implications of the above definition are discussed in the article on completeness properties
in 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.
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 homomorphism
, as will be explained in the below section on morphisms.
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 order
s. 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 semilattice
s.
A and 
A, as defined in L, are actually in M.
If the above requirement is lessened to require only non-empty meet and joins to be in L, the sublattice M is called a closed sublattice of M.
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 inequivalent conditions. This notion may be considered as a homomorphism of complete meet-semilattices or complete join-semilattices, respectively.
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).
s 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.
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.
Free complete lattices in this sense can be constructed very easily: the complete lattice generated by some set S is just the powerset 2S, i.e. the set of all subsets of S, ordered by subset inclusion
. The required unit i:S→2S maps any element s of S to the singleton set {s}. Given a mapping f as above, the function f°:2S→M is defined by
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.
, 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.
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. Unfortunately, the size limit is very low and we have the following theorem:
A proof of this statement is given by Johnstone; the original argument is attributed to Hales; see also the article on free lattice
s.
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.
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.
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.
This in turn is utilized in formal concept analysis
, where one uses binary relations (called formal contexts) to represent such closure operators.
, which states that the set of fixed point
s 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.
Partially ordered set
In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...
in which all subsets have both a supremum
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...
(join) and an infimum
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...
(meet). Complete lattices appear in many applications in mathematics
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...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. Being a special instance of lattices
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...
, they are studied both in 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...
and universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
.
Complete lattices must not be confused with 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 (cpos), which constitute a strictly more general class of partially ordered sets. More specific complete lattices are complete Boolean algebra
Complete Boolean algebra
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...
s and complete Heyting algebra
Complete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames...
s (locales).
Formal definition
A partially ordered setPartially ordered set
In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...
(L, ≤) is a complete lattice if every subset
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...
A of L has both a greatest lower bound (the infimum
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...
, also called the meet) and a least upper bound (the supremum
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...
, also called the join) in (L, ≤).
The meet is denoted by
, and the join by .Note that in the special case where A is the empty set
Empty 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...
the meet of A will be 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...
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.
More implications of the above definition are discussed in the article on completeness properties
Completeness (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 . A special use of the term refers to complete partial orders or complete lattices...
in order theory.
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)Completeness (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 . A special use of the term refers to complete partial orders or complete lattices...
). 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.
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 homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
, as will be explained in the below section on morphisms.
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 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. 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 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...
s.
Complete sublattices
A sublattice M of a complete lattice L is called a complete sublattice of L if for every subset A of M the elementsA and A, as defined in L, are actually in M.If the above requirement is lessened to require only non-empty meet and joins to be in L, the sublattice M is called a closed sublattice of M.
Examples
- The power set of a given set, ordered by inclusionSubsetIn 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...
. The supremum is given by the unionUnion (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 :...
and the infimum by the intersectionIntersection (set theory)In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
of subsets. - The unit intervalUnit intervalIn mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...
[0,1] and the extended real number lineExtended real number lineIn mathematics, the affinely extended real number system is obtained from the real number system R by adding two elements: +∞ and −∞ . The projective extended real number system adds a single object, ∞ and makes no distinction between "positive" or "negative" infinity...
, with the familiar total order and the ordinary supremaSupremumIn 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...
and infimaInfimumIn 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...
. Indeed, a totally ordered set (with its order topologyOrder topologyIn mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets...
) is compactCompact spaceIn mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
as a topological spaceTopological spaceTopological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
if it is complete as a lattice. - The non-negative integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s, 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 multipleLeast common multipleIn 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...
and the infimum by the greatest common divisorGreatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
. 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 subgroups of any given group under inclusion. (While the infimumInfimumIn 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...
here is the usual set-theoretic intersection, the supremumSupremumIn 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 set of subgroups is the subgroup generated by the set-theoretic union of the subgroups, not the set-theoretic union itself.) If e is the identity of G, then the trivial group {e} is the minimum subgroup of G, while the maximum subgroup is the group G itself. - The submodules of a moduleModule (mathematics)In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
, ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection. - The idealsIdeal (ring theory)In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....
of a ringRing (mathematics)In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
, ordered by inclusion. The supremum is given by the sum of ideals and the infimum by the intersection. - The open sets of a topological spaceTopological spaceTopological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
, ordered by inclusion. The supremum is given by the union of open sets and the infimum by the interiorInterior (topology)In mathematics, specifically in topology, the interior of a set S of points of a topological space consists of all points of S that do not belong to the boundary of S. A point that is in the interior of S is an interior point of S....
of the intersection. - The convex subsetConvex setIn Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
s of a realReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
or complexComplex numberA complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
vector spaceVector spaceA vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
, ordered by inclusion. The infimum is given by the intersection of convex sets and the supremum by the convex hullConvex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of the union. - The topologiesTopological spaceTopological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
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 relationTransitive relationIn mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
s on a set. - The lattice of all sub-multisets of a multisetMultisetIn mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
. - The lattice of all equivalence relationEquivalence relationIn mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
s on a set; the equivalence relation ~ is considered to be smaller (or "finer") than ≈ if x~y always implies x≈y. - Any finite lattice is trivially a complete lattice.
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-
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 inequivalent conditions. This notion may be considered as a homomorphism of complete meet-semilattices or complete join-semilattices, respectively.
Furthermore, morphisms that preserve all joins are equivalently characterized as the lower adjoint part of a unique Galois connection
Galois 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...
. 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
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...
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).
Free "complete semilattices"
As usual, the construction of free objectFree object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure . It also has a formulation in terms of category theory, although this is in yet more abstract terms....
s 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.
Using the standard definition from universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
, 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
Adjoint functors
In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another, called an adjunction. The relationship of adjunction is ubiquitous in mathematics, as it rigorously reflects the intuitive notions of optimization and efficiency...
to the forgetful functor
Forgetful functor
In mathematics, in the area of category theory, a forgetful functor is a type of functor. The nomenclature is suggestive of such a functor's behaviour: given some object with structure as input, some or all of the object's structure or properties is 'forgotten' in the output...
from complete lattices to their underlying sets.
Free complete lattices in this sense can be constructed very easily: the complete lattice generated by some set S is just the powerset 2S, i.e. the set of all subsets of S, 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...
. The required unit i:S→2S maps any element s of S to the singleton set {s}. Given a mapping f as above, the function f°:2S→M is defined by
- 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
Duality (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...
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
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...
, where we only need to consider finite sets.
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 latticesLattice (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...
, but the collection of all possible words
Word problem (mathematics)
In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set...
(or "terms") in this case would be a proper class, because arbitrary meets and joins comprise operations for argument-sets of every cardinality.
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. Unfortunately, the size limit is very low and we have the following theorem:
- The free complete lattice on three generators does not exist; it is properly a proper class.
A proof of this statement is given by Johnstone; the original argument is attributed to Hales; see also the article on free lattice
Free lattice
In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. As free objects, they have the universal property. The word problem for free lattices is also challenging.-Formal definition:...
s.
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
Dedekind–MacNeille completion
In order-theoretic mathematics, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains the given partial order...
. 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.
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.Another representation is obtained by noting that the image of any closure operator
Closure operator
In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
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
Dedekind cut
In mathematics, a Dedekind cut, named after Richard Dedekind, is a partition of the rationals into two non-empty parts A and B, such that all elements of A are less than all elements of B, and A contains no greatest element....
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.
This in turn is utilized in formal concept analysis
Formal concept analysis
Formal concept analysis is a principled way of automatically deriving an ontology from a collection of objects and their properties. The term was introduced by Rudolf Wille in 1984, and builds on applied lattice and order theory that was developed by Birkhoff and others in the 1930s.-Intuitive...
, where one uses binary relations (called formal contexts) to represent such closure operators.
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 theoremKnaster–Tarski theorem
In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:...
, which states that the set of fixed point
Fixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
s 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.