Lattice (order)
|
|
- For other uses, see Lattice.
Lattice_of_partitions_of_an_order_4_set.png
In mathematics, a lattice is a partially ordered set (or poset), in which all nonempty finite subsets have both a supremum (join) and an infimum (meet). 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.
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.
| Contents |
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<math>\vee<math>y and x<math>\wedge<math>y, respectively. Clearly, this defines binary operations <math>\wedge<math> and <math>\vee<math> 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,<math>\vee<math>, <math>\wedge<math>), where <math>\vee<math> and <math>\wedge<math> are two binary operations. L is a lattice if the following identities hold for all elements a, b, and c in L:
| Idempotent laws: | <math> a \vee a = a <math> | <math> a \wedge a = a <math> | ||
| Commutative laws: | <math> a \vee b = b \vee a <math> | <math> a \wedge b = b \wedge a <math> | ||
| Associative laws: | <math> a \vee (b \vee c) = (a \vee b) \vee c <math> | <math> a \wedge (b \wedge c) = (a \wedge b) \wedge c <math> | ||
| Absorption laws: | <math> a \vee (a \wedge b) = a <math> | <math> a \wedge (a \vee b) = a <math> |
Note that the laws for idempotency, commutativity, and associativity just state that (L,<math>\vee<math>) and (L,<math>\wedge<math>) 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 <math>\vee<math> and <math>\wedge<math>. It now can be seen very easily that this operation really makes (L, <math>\vee<math>, <math>\wedge<math>) a lattice in the algebraic sense. Maybe more surprisingly, one can also obtain the converse of this result: consider any algebraically defined lattice (M, <math>\vee<math>, <math>\wedge<math>). Now one can define a partial order ≤ on M by setting
- x ≤ y iff x = x<math>\wedge<math>y
or, equivalently,
- x ≤ y iff y = x<math>\vee<math>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 <math>\vee<math> and <math>\wedge<math>. Conversely, the order induced by the algebraically defined lattice (L, <math>\vee<math>, <math>\wedge<math>) 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, <math>\vee<math>, <math>\wedge<math>) and (M, <math>\cup<math>, <math>\cap<math>), a homomorphism of lattices is a function f : L → M with the properties that
- f(x<math>\vee<math>y) = f(x) <math>\cup<math> f(y), and
- f(x<math>\wedge<math>y) = f(x) <math>\cap<math> 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. Details can be found within the respective article.
Distributivity
Since any lattice comes with two binary operations, it is natural to consider distributivity laws among them. A lattice (L, <math>\vee<math>, <math>\wedge<math>) is distributive, if the following condition is satisfied for every three elements x, y and z of L:
- <math>x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)<math>
Maybe surprisingly, this condition turns to be equivalent to its dual statement:
- <math>x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)<math>
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, <math>\vee<math>, <math>\wedge<math>) is modular if, for all elements x, y, and z of L, we have
- <math>x \vee (y \wedge (x \vee z)) = (x \vee y) \wedge (x \vee z)<math>
Another equivalent statement of this condition is as follows: if x ≤ z then for all y one has
- <math>x \vee (y \wedge z) = (x \vee y) \wedge z<math>
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. In a bounded lattice with greatest element 1 and least element 0, one says that two elements x,y are complements of each other if the following hold:
- <math>x \vee y = 1<math> and <math>x \wedge y = 0<math>
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 <math>\wedge<math> y = 0. If the pseudo-complements of all elements 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 <math>\vee<math> and <math>\wedge<math> 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<math>\vee<math>1 = 1 and a<math>\wedge<math>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 <math>\vee<math> w2 and both w1<~v and w2<~v hold,
- w = w1 <math>\wedge<math> w2 and either w1<~v or w2<~v holds,
- v = v1 <math>\vee<math> v2 and either w<~v1 or w<~v2 holds,
- v = v1 <math>\wedge<math> 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 Vai, x is called completely join-irreducible. The dual notion is called meet-irreducibility. 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
References
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.de:Verband (Mathematik)
es:Reticulado (orden) et:Võre (matemaatika) fr:Treillis (ensemble ordonné) it:Reticolo_(matematica) pl:Krata (porządek) zh:格 (数学) ja:束論