The Lattice (order) reference article from the English Wikipedia on 24-Jul-2004
(provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Lattice (order)

Watch child sponsorship videos
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.

Table of contents
1 Formal definition
2 Morphisms of lattices
3 Properties of lattices
4 Examples
5 Free lattices
6 Important lattice-theoretic notions
7 Literature

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, 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

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

xy iff x = xy

or, equivalently,

xy iff y = xy

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 : LM with the properties that

f(xy) = f(x) f(y), and
f(xy) = 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:

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 xz 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:

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

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:SL, such that any function f from S to the underlying set of some lattice M can be factored uniquely through a lattice homomorphism from L to M. Stated differently, for every element s of S we find that f(s) = (i(s)) and that 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:

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

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

When the first condition is generalized to arbitrary joins Vai, 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

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:

A more in depth treatment can be found in Garrett Birkhoff's classic:

The results on free lattices can also be found in the (otherwise not lattice-theoretical) book: