Complete lattice

Last updated

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). A lattice that satisfies at least one of these properties is known as a conditionally complete lattice. 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.

Contents

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

Formal definition

A partially ordered set (L, ≤) is a complete lattice if every subset A of L has both the greatest lower bound (the infimum, also called the meet) and the least upper bound (the supremum, also called the join) in (L, ≤).

The meet is denoted by , and the join by .

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 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. [1]

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 are another way to refer to complete lattices since arbitrary meets can be expressed in terms of arbitrary joins and vice versa (for details, see completeness).

Another usage of "complete meet-semilattice" refers to a meet-semillatice 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 (in fact, only the top element may be missing).

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: [2]

Examples

Locally finite complete lattices

A complete lattice L is said to be locally finite if the supremum of any infinite subset is equal to 1, or equivalently, the set is finite for any . The lattice (N, |) is locally finite. In this lattice, the element generally denoted "0" is actually 1 and vice versa.

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

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 joins (giving a category Sup) or all meets (giving a category Inf), which are indeed inequivalent conditions. This notion may be considered as a homomorphism 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 P and Q, these are given by pairs of monotone functions f and g such that

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

A particularly important special case is for lattices of subsets P(X) and P(Y) and a function from X to Y. In this case, the direct image and inverse image maps between the power sets are upper and lower adjoints to each other, respectively.

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.

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:SL, 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°:2SM is defined by

.

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

Free complete lattices

The situation for complete lattices with complete homomorphisms obviously 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 (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 a proper class.

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.

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

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

Already G. Birkhoff's Lattice Theory book [5] [ page needed ] contains a very useful representation method. It associates a complete lattice to any binary relation between two sets by constructing a Galois connection from the relation, which then leads to two dually isomorphic closure systems. Closure systems are intersection-closed families of sets. When ordered by the subset relation , they are complete lattices.

A special instance of Birkhoff's construction starts from an arbitrary poset (P,) and constructs the Galois connection from the order relation between P and itself. The resulting complete lattice is the Dedekind-MacNeille completion. When this completion is applied to a poset that already is a complete lattice, then the result is isomorphic to the original one. 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.

Another representation is obtained as follows: A subset of a complete lattice is itself a complete lattice (when ordered with the induced order) if and only if it is the image of an increasing and idempotent (but not necessarily extensive) self-map. The identity mapping has these two properties. Thus all complete lattices occur.

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 increasing and idempotent functions, since these are instances of the theorem.

Related Research Articles

In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

Order theory is a branch of mathematics that investigates the 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 provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation theorem for Boolean algebras. These concepts are named in honor of Marshall Stone. Stone-type dualities also provide the foundation for pointless topology and are exploited in theoretical computer science for the study of formal semantics.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets

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 which a function satisfies this property, it may preserve finite, directed, non-empty, or just arbitrary suprema or infima. Each of these requirements appears naturally and frequently in many areas of order theory and there are various important relationships among these concepts and other notions such as monotonicity. If the implication of limit preservation is inverted, such that the existence of limits in the range of a function implies the existence of limits in the domain, then one obtains functions that are limit-reflecting.

In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist.

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

In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra that 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. Although these three categories contain the same objects, they differ in their morphisms, and thus get distinct names. Only the morphisms of CHey are homomorphisms of complete Heyting algebras.

In the Mathematical area of Order theory, the compact elements or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element. This notion of compactness simultaneously generalizes the notions of finite sets in set theory, compact sets in topology, and finitely generated modules in algebra.

In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded-complete and directed-complete partial order (dcpo). They are named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory. Scott domains are very closely related to algebraic lattices, being different only in possibly lacking a greatest element. They are also closely related to Scott information systems, which constitute a "syntactic" representation of Scott domains.

In mathematics, a join-semilattice is a partially ordered set that 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. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

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. Every Boolean algebra A has an essentially unique completion, which is a complete Boolean algebra containing A such that every element is the supremum of some subset of A. As a partially ordered set, this completion of A is the Dedekind–MacNeille completion.

<span class="mw-page-title-main">Join and meet</span> Concept in order theory

In mathematics, specifically order theory, the join of a subset of a partially ordered set is the supremum of denoted and similarly, the meet of is the infimum, denoted In general, the join and meet of a subset of a partially ordered set need not exist. Join and meet are dual to one another with respect to order inversion.

In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets.

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a 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.

In the mathematics of matroids and lattices, a geometric lattice is a finite atomistic semimodular lattice, and a matroid lattice is an atomistic semimodular lattice without the assumption of finiteness. Geometric lattices and matroid lattices, respectively, form the lattices of flats of finite, or finite and infinite, matroids, and every geometric or matroid lattice comes from a matroid in this way.

References

  1. Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN   3-540-90578-2 (A monograph available free online).
  2. Baker, Kirby (2010). "Complete Lattices" (PDF). UCLA Department of Mathematics. Retrieved 8 June 2022.
  3. P. T. Johnstone, Stone Spaces, Cambridge University Press, 1982; (see paragraph 4.7)
  4. A. W. Hales, On the non-existence of free complete Boolean algebras, Fundamenta Mathematicae 54: pp.45-66.
  5. Garrett Birkhoff, Lattice Theory, AMS Colloquium Publications Vol. 25, ISBN   978-0821810255