Lattice (order)
- See lattice for other meanings of the term, both within and without mathematics.
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
Lattices as posets
Consider a partially ordered set (L, ≤). L is a lattice if
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:
Idempotency laws: | ||
Commutativity laws: | ||
Associativity 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
or, equivalently,
- x ≤ y iff y = xy
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.
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 homomorphisms of lattices is a function f : L → M with the properties that
- f(xy) = f(x) f(y), and
- f(xy) = f(x) f(y).
- f(0) = 0, and
- f(1) = 1.
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
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 subsets 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.
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:
Modularity
Another equivalent statement of this condition is as follows: if x ≤ z then for all y one has
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.
Complements and Pseudo-complements
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.
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 natural numbers in their common order are a lattice.
- None of the above lattices is bounded. However, any complete lattice especially is a bounded lattice.
- The set of compact elements of an arithmetic (complete) lattice is a lattice with a least element.
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 a1 = 1 and a1 =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.
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 eventuall 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
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.
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.
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.
Literature
A very good first introduction is given in the popular textbook of Davey's and Priestley's:
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.
- P. T. Johnstone: Stone spaces. Cambridge Studies in Advancd Mathematics 3, Cambridge University Press, 1982.