Lattice (order)

: For other uses, see Lattice. 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 identity. 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, and Boolean algebras.

This article treats the most basic definitions of lattice theory, including the case of bounded lattices, i.e., lattices that have unique 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, or supremum ) and a greatest lower bound (meet, or infimun ).

In this situation, the join and meet of x and y are denoted by x vee y and x wedge y, respectively. Because joins and meets are assumed to exist in a lattice, wedge and vee are binary operations. Also note that the above definition is equivalent to requiring L to be both a meet-semilattice and a join-semilattice.

It will be stated explicitly whenever a lattice is required to have a least element or greatest element. If both of these special elements do exist, then the poset is a bounded lattice.

Using an easy mathematical induction argument, one can deduce the existence of suprema ( joins ) and infima ( meets ) of all non-empty finite subsets of any lattice. Further conclusions may be possible in the presence of other properties. See the article on completeness (order theory) for more discussion of this subject. That 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 theory investigations of the concept.

== Lattices as algebraic structures ==

Consider an algebraic structure ( L ,vee, wedge), where L is a set with two binary operations, vee and wedge. L is a lattice if the following identity hold for all elements a , b , and c in L :

The following identity follows from the above:

Note that the laws for idempotency, commutativity, and associativity just state that ( L ,vee) and ( L ,wedge) constitute two semilattices, while the absorption laws guarantee that both of these semilattices interact appropriately.

Lattices in this algebraic interpretation have an essential role in universal algebra.

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 the two definitions ==

Obviously, an order-theoretic lattice gives rise to two binary operations vee and wedge. It is easy to see that these operations make ( L , vee, wedge) into a lattice in the algebraic sense. The converse is true also: Consider an algebraically defined lattice ( M , vee, wedge). Now define a partial order ≤ on M by setting

: x ≤ y iff x = x wedge y

or, equivalently,

: x ≤ y iff y = x vee y

for elements x and y in M . The laws of 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 vee and wedge. Conversely, the order induced by the algebraically defined lattice ( L , vee, wedge) 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 subsets of A (called the power set of A ) can be ordered via subset to obtain a bounded lattice. The lattice operations are intersection (set theory) (meet) and union (set theory) (join) of sets, respectively. This lattice has the empty set as least element, and A as greatest element.

For any set A , the collection of all finite subsets of A , ordered by inclusion, is also a lattice, and will be bounded if and only if A is finite.

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.

The non-zero natural numbers also form a lattice under the greatest common divisor and least common multiple operations, with the order relation representing divisibility. The least element of this lattice is 1, and again there is no greatest element.

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 lattice 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 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 , vee, wedge) and ( M , cup, cap), a homomorphism of lattices is a function f : L → M with the properties that

: f ( x vee y ) = f ( x ) cup f ( y ), and : f ( x wedge y ) = f ( x ) cap 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 limit preserving function (order theory) 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 function with respect to the associated ordering relation. For an explanation see the article on limit preserving function (order theory). 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 theory.

= 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 , vee, wedge) is distributive, if the following condition is satisfied for every three elements x , y and z of L :

: x vee (y wedge z) = (x vee y) wedge (x vee z)

Maybe surprisingly, this condition turns to be equivalent to its duality (order theory) statement:

: x wedge (y vee z) = (x wedge y) vee (x wedge z)

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 complete Heyting algebra and completely distributive lattices. An overview of these different notions is given in the article on distributivity (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 , vee, wedge) is modular lattice if, for all elements x , y , and z of L , we have

: x vee (y wedge (x vee z)) = (x vee y) wedge (x vee z)

Another equivalent statement of this condition is as follows: if x ≤ z then for all y one has

: x vee (y wedge z) = (x vee y) wedge z

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 relation 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 poset. 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:

: x vee y = 1 and x wedge y = 0

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 wedge 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 from lattices to their underlying sets.

We treat the case of bounded lattices, i.e. algebraic structures with the two binary operations vee and wedge 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 vee1 = 1 and a wedge1 = 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