Complete lattice

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

for D 4 , the dihedral group of the square. This is an example of a 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 and nonempty 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 (CPOs), a more general class of partially ordered sets. More specific complete lattices are complete Boolean algebras and complete Heyting algebras (locales).

for D 4 , the dihedral group of the square. This is an example of a 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 and nonempty 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 (CPOs), a more general class of partially ordered sets. More specific complete lattices are complete Boolean algebras and complete Heyting algebras (locales).

Conditionally complete lattices

A lattice is said to be "conditionally complete" if it satisfies either or both of the following properties: Any nonempty subset bounded above has the least upper bound. Any nonempty subset bounded below has the greatest lower bound. The rational numbers \mathbb{Q} with the usual order ≤ is not a complete lattice. It is a lattice with \bigwedge \{x, y\} = \min\{x, y\} and \bigvee \{x, y\} = \max\{x, y\} . However, \mathbb{Q} itself has no infimum or supremum, nor does \{ x \in \mathbb{Q} | x^2 .

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 \{y \in L ~|~ y \le x\} \,\! is finite for any 1 \ne x \in L . This notation may clash with other notation, as in the case of the lattice (N, |), 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. f\left(\bigwedge A\right) = \bigwedge\{f(a)\mid a\in A\} and f\left(\bigvee A\right) = \bigvee\{f(a)\mid a\in A\} , 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 (giving a category Sup) or all meets (giving a category Inf), which are indeed inequivalent conditions. These notions may also be considered as homomorphisms of complete meet-semilattices or complete join-semilattices, respectively.

The standard definition from universal algebra states that a free complete lattice over a generating set S is a complete lattice L together with a function i: S \rightarrow 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^ \circ from L to M . This means that f(s) = f^\circ(i(s)) for every element s of S , and that f^\circ 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 S is just the powerset 2^S , the set of all subsets of S ordered by subset inclusion. The required unit i: S \rightarrow 2^S maps any element s of S to the singleton set \{s\} .

Given a mapping f as above, the function f^\circ : 2^S \rightarrow M is defined by f^\circ (X) = \bigvee \{ f(s) | s \in X \} . Then f^\circ transforms unions into suprema and thus preserves joins. 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 f^\circ 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.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1351213495 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.