*See lattice for other mathematical as well as non-mathematical meanings of the term.* In mathematics, a **lattice** is a poset (i.e. a partially ordered set), in which all nonempty *finite* subsets have both a supremum (**join**) and an infimum (**meet**). On the other hand, lattices can also be characterized as algebraic structures that satisfy certain identities. Since both views can be used interchangeably, lattice theory can draw upon applications and methods both from order theory and from universal algebra. Lattices constitute one of the most prominent representatives of a series of "lattice-like" structures which admit order-theoretic as well as algebraic descriptions, such as semilattices, Heyting algebras, or Boolean algebras. The term "lattice" derives from the shape of the Hasse diagrams that result from depicting these orders. This article treats the most basic definitions of lattice theory, including the case of **bounded lattices**, i.e lattices that have top and bottom elements. ## Formal definition
As mentioned above, lattices can be characterized both as posets and as algebraic structures. Both approaches and their relationship are explained below.
### Lattices as posets Consider a poset (*L*, ≤). *L* is a **lattice** if - for all elements
*x* and *y* of *L*, the set {*x*, *y*} has both a least upper bound (**join**) and a greatest lower bound (**meet**). In this situation, the join and meet of *x* and *y* are denoted by *x**y* and *x**y*, respectively. Clearly, this defines binary operations and on lattices. Also note that the above definition is equivalent to requiring *L* to be both a meet- and a join-semilattice. It will be stated explicitly whenever a lattice is required to have a least or greatest element. If both of these special elements do exist, then the poset is a *bounded lattice*. Using an easy induction argument, one can also conclude the existence of all suprema and infima of non-empty finite subsets of any lattice. Further conclusions may be possible in the presence of other properties. See the article on completeness in order theory for more discussion on this subject. This article also discusses how one may rephrase the above definition in terms of the existence of suitable Galois connections between related posets -- an approach that is of special interest for category theoretic investigations of the concept.
### Lattices as algebraic structures Consider an algebraic structure in the sense of universal algebra, given by (*L*,, ), where and are two binary operations. *L* is a *lattice* if the following identities hold for all elements *a*, *b*, and *c* in *L*: **Idempotent laws:** | | | | **Commutative laws:** | | | | **Associative laws:** | | | | **Absorption laws:** | | | | Note that the laws for idempotency, commutativity, and associativity just state that (*L*,) and (*L*,) constitute two semilattices, while the absorption laws guarantee that both of these structures interact appropriately. Furthermore, it turns out that the idempotency laws can be deduced from absorption and thus need not be stated separately. In order to describe *bounded lattices*, one has to include neutral elements 0 and 1 for the meet and join operations in the above definition. For details compare the article on semilattices.
### Connection between both definitions Obviously, an order theoretic lattice gives rise to two binary operations and . It now can be seen very easily that this operation really makes (*L*, , ) a lattice in the algebraic sense. Maybe more surprisingly, one can also obtain the converse of this result: consider any algebraically defined lattice (*M*, , ). Now one can define a partial order ≤ on *M* by setting *x* ≤ *y* iff *x* = *x**y* or, equivalently, *x* ≤ *y* iff *y* = *x**y* for all elements *x* and *y* in *M*. The above laws for absorption ensure that both definitions are indeed equivalent. One can now check that the relation ≤ introduced in this way defines a partial ordering within which binary meets and joins are given through the original operations and . Conversely, the order induced by the algebraically defined lattice (*L*, , ) that was derived from the order theoretic formulation above coincides with the original ordering of *L*. Hence, the two definitions can be used in an entirely interchangeable way, depending on which of them appears to be more convenient for a particular purpose.
## Examples - For any set
*A*, the collection of all finite subsets of *A* (including the empty set) can be ordered via subset inclusion to obtain a lattice. The lattice operations are intersection (meet) and union (join) of sets, respectively. This lattice has the empty set as least element, but it will only contain a greatest element if *A* itself is finite. So it is not a bounded lattice in general. - The natural numbers in their common order are a lattice, the lattice operations given by the
*min* and *max* operations. The least element of this lattice is 0, but no greatest element exists. - Any complete lattice (also see below) is a (rather specific) bounded lattice. A broad range of practically relevant examples belongs to this class.
- The set of compact elements of an arithmetic complete lattice is a lattice with a least element, where the lattice operations are given by restricting the respective operations of the arithmetic lattice. This is the specific property which distinguishes arithmetic lattices from algebraic lattices, for which the compacts do only form a join-semilattice. Both of these classes of complete lattices are studied in domain theory.
Further examples are given for each of the additional properties that are discussed below.
## Morphisms of lattices The appropriate notion of a morphism between two lattices can easily be derived from the algebraic definition above: given two lattices (*L*, , ) and (*M*, , ), a *homomorphism of lattices* is a function *f* : *L* → *M* with the properties that *f*(*x**y*) = *f*(*x*) *f*(*y*), and *f*(*x**y*) = *f*(*x*) *f*(*y*). Thus *f* is a homomorphism of the two underlying semilattices. If the lattices are furthermore equipped with least elements 0 and greatest elements 1, then *f* should also preserve these special elements: *f*(0) = 0, and *f*(1) = 1. In the order-theoretical formulation, these conditions just state that a homomorphism of lattices is a function that preserves binary meets and joins. For bounded lattices, preservation of least and greatest elements is just preservation of join and meet of the empty set. Note that any homomorphism of lattices is necessarily monotone with respect to the associated ordering relation. For an explanation see the article on preservation of limits. The converse is of course not true: monotonicity does by no means imply the required preservation properties. Using the standard definition of isomorphisms as invertible morphisms, one finds that an isomorphism of lattices is exactly a bijective lattice homomorphism. Lattices and their homomorphisms obviously form a category.
## Properties of lattices The definitions above already introduced the simple condition of being a bounded lattice. A number of other important properties, many of which lead to interesting special classes of lattices, will be introduced below.
### Completeness A highly relevant class of lattices are the **complete lattices**. A lattice is complete if *any* of its subsets has both a join and a meet, which should be contrasted to the above definition of a lattice where one only requires the existence of all (non-empty) finite joins and meets. It turns out that the existence of all joins suffices to conclude the existence of all meets and vice versa. For more details on this basic result and some alternative sufficient conditions for completeness, see the article on completeness properties. Note also that complete lattices are always bounded. Examples of complete lattices include: - The power set of a given set, ordered by inclusion. The supremum is given by the union and the infimum by the intersection of subsets.
- The unit interval [0,1] and the extended real number line, with the familiar total order and the ordinary suprema and infima.
- The non-negative integers, 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 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 a group, ordered by inclusion. The supremum is given by the subgroup generated by the union of the groups and the infimum is given by the intersection.
- The submodules of a module, ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection.
- The ideals of a ring, 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, ordered by inclusion. The supremum is given by the union of open sets and the infimum by the interior of the intersection.
- The convex subsets of a real or complex vector space, ordered by inclusion. The infimum is given by the intersection of convex sets and the supremum by the convex hull of the union.
- The topologies 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 binary relations on a set.
- The lattice of all sub-multisets of a multiset.
- The lattice of all equivalence relations on a set; the equivalence relation ~ is considered to be smaller (or "finer") than ≈ if
*x*~*y* always implies *x*≈*y*. Many theorems of order theory take especially simple forms when stated for complete lattices. For example, the Knaster-Tarski theorem states that the set of fixed points of a monotone function on a complete lattice is again a complete lattice.
### Distributivity Since any lattice comes with two binary operations, it is natural to consider distributivity laws among them. A lattice (*L*, , ) is **distributive**, if the following condition is satisfied for every three elements *x*, *y* and *z* of *L*: Maybe surprisingly, this condition turns to be equivalent to its dual statement: Other characterizations exist and can be found in the article on distributive lattices. For complete lattices one can formulate various stronger properties, giving rise to the classes of frames and completely distributive lattices. An overview of these different notions is given in the article on distributivity in order theory.
### Modularity Often one finds that distributivity is too strong a condition for certain applications. A strictly weaker property is *modularity*: a lattice (*L*, , ) is **modular** if, for all elements *x*, *y*, and *z* of *L*, we have Another equivalent statement of this condition is as follows: if *x* ≤ *z* then for all *y* one has For example, the lattice of submodules of a module and the lattice of normal subgroups of a group have this special property. Furthermore, every distributive lattice is indeed modular.
### Continuity and algebraicity In domain theory, one is often interested in approximating the elements in a partial order by "much simpler" elements. This leads to the class of continuous posets, consisting of posets where any element can be obtained as the supremum of a directed set of elements that are way-below the element. If one can additionally restrict to the compact elements of a poset for obtaining these directed sets, then the poset is even algebraic. Both concepts can be applied to lattices as follows: - A
**continuous lattice** is a complete lattice that is continuous as a poset. - An
**algebraic lattice** is a complete lattice that is algebraic as a poset. Both of these classes have interesting properties. For example, continuous lattices can be characterized as algebraic structures (with infinitary operations) satisfying certain identities. While such a characterization is not known for algebraic lattices, they can be described "syntactically" via Scott information systems.
### Complements and pseudo-complements The concept of complements introduces the idea of "negation" into lattice theory. Consider a bounded lattice with greatest element 1 and least element 0. One says that an element *x* is a **complement** of one element *y* if the following hold: - and
A bounded lattice within which every element has some complement is called a complemented lattice. Note that this complement is neither required to be unique nor to be "special" in any sense among all existing complements. In contrast, a Boolean algebra has a unique complement for each element *x* which can thus be denoted by ¬*x*. In contrast, Heyting algebras are more general kinds of lattices, within which complements usually do not exist. However, each element *x* in a Heyting algebra has a *pseudo-complement* that is usually also denoted by ¬*x*. It is characterized as being greatest among all elements *y* with the property that *x* *y* = 0. If the pseudo-complements of a Heyting algebra are in fact complements, then it is a Boolean algebra.
## Free lattices Using the standard definition of universal algebra, a *free lattice* over a generating set *S* is a lattice *L* together with a function *i*:*S*→*L*, such that any function *f* from *S* to the underlying set of some lattice *M* can be factored uniquely through a lattice homomorphism *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 lattice homomorphism 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 lattices and lattice homomorphisms which is left adjoint to the forgetful functor from lattices to their underlying sets. We treat the case of bounded lattices, i.e. algebraic structures with the two binary operations and and the two constants (nullary operations) 0 and 1. The set of all correct (well-formed) expressions that can be formulated using these operations on elements from a given set of generators *S* will be called **W**(*S*). This set of words contains many expressions that turn out to be equal in any lattice. For example, if *a* is some element of *S*, then *a*1 = 1 and *a*1 =*a*. The *word problem* for lattices is the question, which of these elements have to be identified. The answer to this problem is as follows. Define a relation <~ on **W**(*S*) by setting *w* <~ *v* iff one of the following holds: *w* = *v* (this can be restricted to the case where *w* and *v* are elements of *S*), *w* = 0 or *v* = 1, *w* = *w1* *w2* and both *w1*<~*v* and *w2*<~*v* hold, *w* = *w1* *w2* and either *w1*<~*v* or *w2*<~*v* holds, *v* = *v1* *v2* and either *w*<~*v1* or *w*<~*v2* holds, *v* = *v1* *v2* and both *w*<~*v1* and *w*<~*v2* hold. This defines a preorder <~ on **W**(*S*). The partially ordered set induced by this preorder (i.e. the set obtained by identifying all words *w* and *v* with *w*<~*v* and *v*<~*w*) is the free lattice on *S*. The required embedding *i* is the obvious mapping from a generator *a* to (the set of words equivalent to) the word *a*. One of the consequences of this statement is that the free lattice of a three element set of generators is already infinite. In fact, one can even show that every free lattice on three generators contains a sublattice which is free for a set of four generators. By induction this eventually yields a sublattice free on countably many generators. The case of lattices that are not bounded is treated similarly, using only the two binary operations in the above construction.
## Important lattice-theoretic notions In the following, let *L* be a lattice. We define some order-theoretic notions that are of particular importance in lattice theory. An element *x* of *L* is called **join-irreducible** iff *x* = *a* v *b* implies *x* = *a* or *x* = *b* for any *a*, *b* in *L*, - if
*L* has a *0*, *x* is sometimes required to be different from *0*. When the first condition is generalized to arbitrary joins Va_{i}, *x* is called **completely join-irreducible**. The dual notion is called **meet-irreducability**. Sometimes one also uses the terms v-irreducible and ^-irreducible, respectively. An element *x* of *L* is called **join-prime** iff *x* ≤ *a* v *b* implies *x* ≤ *a* or *x* ≤ *b*, - if
*L* has a *0*, *x* is sometimes required to be different from *0*. Again, this can be generalized to obtain the notion **completely join-prime** and dualized to yield **meet-prime**. Any join-prime element is also join-irreducible, and any meet-prime element is also meet-irreducible. If the lattice is distributive the converse is also true. Other important notions in lattice theory are ideal and its dual notion filter. Both terms describe special subsets of a lattice (or of any partially ordered set in general). Details can be found in the respective articles.
## See also - Lattice theory - wikibook link
## Literature *A very good first introduction is given in the popular textbook of Davey's and Priestley's:* - B. A. Davey, H. A. Priestley:
*Introduction to Lattices and Order*. Cambridge University Press, 2002. (ISBN 0521784514) *A more in depth treatment can be found in Garrett Birkhoff's classic:* - G. Birkhoff:
*Lattice Theory*. Volume 25 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, Rhode Island, 3rd edition, 1967. *The results on free lattices can also be found in the (otherwise not lattice-theoretical) book:* - P. T. Johnstone:
*Stone spaces*. Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, 1982. |