Lattice (order)

See lattice for other meanings of the term, both within and without mathematics.

In mathematics, a lattice is 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 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 partially ordered set (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, on 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:

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

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(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 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 supremum is given by the least common multiple and the infimum by the greatest common divisor.
• 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.

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.

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.

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.