Complete lattice

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet).

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.

Both order theory and universal algebra study them as a special class of lattices.

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.

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

Furthermore, morphisms that preserve all joins are equivalently characterized as the lower adjoint part of a unique Galois connection.

As such, each join-preserving morphism determines a unique upper adjoint in the inverse direction that preserves all meets.

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 (upper adjoints) and their dual join-preserving mappings (lower adjoints).

A particularly important class of special cases arises between lattices of subsets of X and Y, i.e., the power sets ⁠

The construction of free objects depends on the chosen class of morphisms.

Functions that preserve all joins (i.e. lower adjoints of Galois connections) are called free complete join-semilattices.

The standard definition from universal algebra states that a free complete lattice over a generating set

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.

These considerations also yield a free construction for morphisms that preserve meets instead of joins (i.e. upper adjoints of Galois connections).

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

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.

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.

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.

[3] The original argument is attributed to Alfred W. Hales;[4] see also the article on free lattices.

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

This is easily seen by considering posets with a discrete order, where every element only relates to itself.

Thus, we immediately find that every complete lattice is represented by Birkhoff's method, up to isomorphism.

The construction is utilized in formal concept analysis, where one represents real-word data by binary relations (called formal contexts) and uses the associated complete lattices (called concept lattices) for data analysis.

The mathematics behind formal concept analysis therefore is the theory of complete lattices.

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.

This is easily seen to be a generalization of the above observation about the images of increasing and idempotent functions.