Complete lattice


In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum. A conditionally complete lattice satisfies at least one of these properties for bounded subsets. For comparison, in a general lattice, only pairs of elements need to have a supremum and an infimum. Every non-empty finite lattice is complete, but infinite lattices may be incomplete.
Complete lattices appear in many applications in mathematics and computer science. Both order theory and universal algebra study them as a special class of lattices.
Complete lattices must not be confused with complete partial orders, a more general class of partially ordered sets. More specific complete lattices are complete Boolean algebras and complete Heyting algebras.

Formal definition

A complete lattice is a partially ordered set such that every subset A of L has both a greatest lower bound and a least upper bound in.
The meet is denoted by, and the join by.
In the special case where A is the empty set, the meet of A is the greatest element of L. Likewise, the join of the empty set is the least element of L. Then, complete lattices form a special class of bounded lattices.

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 elements and, 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 M, the sublattice M is called a closed sublattice of L.

Complete semilattices

The terms complete meet-semilattice or complete join-semilattice is another way to refer to complete lattices since arbitrary meets can be expressed in terms of arbitrary joins and vice versa.
Another usage of "complete meet-semilattice" refers to a meet-semilattice that is bounded complete and a complete partial order. This concept is arguably the "most complete" notion of a meet-semilattice that is not yet a lattice.
See semilattices for further discussion between both definitions.

Conditionally Complete Lattices

A lattice is said to be "conditionally complete" if it satisfies either or both of the following properties:
  • Any subset bounded above has the least upper bound.
  • Any subset bounded below has the greatest lower bound.

    Examples

  • Any non-empty finite lattice is trivially complete.
  • The power set of a given set when ordered by inclusion. The supremum is given by the union and the infimum by the intersection of subsets.
  • The non-negative integers ordered by divisibility. The least element of this lattice is the number 1 since it divides any other number. Perhaps 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 subgroups of any given group under inclusion. If e is the identity of G, then the trivial group is the minimum subgroup of G, while the maximum subgroup is the group G itself.
  • The ideals of a ring, when 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, when ordered by inclusion. The supremum is given by the union of open sets and the infimum by the interior of the intersection.
  • Bounded subsets of the real numbers with their usual order ≤ form a complete lattice.
  • Real numbers with their usual order ≤ do not form a complete lattice, for sequences might get arbitrarily large or small. However, a complete lattice is formed by appending and, forming the extended real number line.

    Non-examples

  • The empty set is not a complete lattice. If it were a complete lattice, then in particular the empty set would have an infimum and supremum in the empty set, a contradiction.
  • The rational numbers with the usual order ≤ is not a complete lattice. It is a lattice with and. However, itself has no infimum or supremum, nor does.

    Locally finite complete lattices

A complete lattice L is said to be locally finite if the supremum of any infinite subset is equal to the supremal element. Denoting this supremal element "1", the condition is equivalently that the set is finite for any. This notation may clash with other notation, as in the case of the lattice, i.e., the non-negative integers ordered by divisibility. In this locally finite lattice, the infimal element denoted "0" for the lattice theory is the number 1 in the set N and the supremal element denoted "1" for the lattice theory is the number 0 in the set N.

Morphisms of complete lattices

The traditional morphisms between complete lattices, taking the complete lattices as the objects of a category, are the complete 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, such as those that are only required to preserve all joins or all meets, which are indeed inequivalent conditions. These notions may also be considered as homomorphisms of complete meet-semilattices or complete join-semilattices, respectively.

Galois connections and adjoints

Furthermore, morphisms that preserve all joins are equivalently characterized as the lower adjoint part of a unique Galois connection. For any pair of preorders X and Y, a Galois connection is given by a pair of monotone functions f and g from X to Y such that for each pair of elements x of X and y of Y
where f is called the lower adjoint and g is called the upper adjoint. By the adjoint functor theorem, a monotone map between any pair of preorders preserves all joins if and only if it is a lower adjoint and preserves all meets if and only if it is an upper adjoint.
As such, each join-preserving morphism 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 one's lattice morphisms. This also yields the insight that three classes of morphisms discussed above basically describe just two different categories of complete lattices: one with complete homomorphisms and one with Galois connections that captures both the meet-preserving functions and their dual join-preserving mappings.
A particularly important class of special cases arises between lattices of subsets of X and Y, i.e., the power sets and, given a function from X to Y. In these cases, the direct image and inverse image maps induced by between the power sets are upper and lower adjoints to each other, respectively.

Free construction and completion

Free "complete semilattices"

The construction of free objects depends on the chosen class of morphisms. Functions that preserve all joins are called free complete join-semilattices.
The standard definition from universal algebra states that a free complete lattice over a generating set is a complete lattice together with a function, such that any function from to the underlying set of some complete lattice can be factored uniquely through a morphism from to. This means that for every element of, and that is the only morphism with this property. Hence, 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 can thus be constructed such that the complete lattice generated by some set ' is just the powerset, the set of all subsets of ' ordered by subset inclusion. The required unit maps any element of to the singleton set. Given a mapping as above, the function is defined by
Then transforms unions into suprema and thus preserves joins.
These considerations also yield a free construction for morphisms that preserve meets instead of joins. The above can be dualized: free objects are given as powersets ordered by reverse inclusion, such that set union provides the meet operation, and the function is defined in terms of meets instead of joins. The result of this construction is known as a free complete meet-semilattice. It can be noted that these free constructions extend those that are used to obtain free semilattices, where finite sets need to be considered.

Free complete lattices

The situation for complete lattices with complete homomorphisms is more intricate. In fact, free complete lattices generally do 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 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 the proper classes 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 Alfred W. Hales; see also the article on free lattices.