Lattice

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

1. In some mathematical usage, a lattice is a discrete subgroup of Rn or Cn. Every lattice can be generated from a basis for the underlying vector space by considering all linear combinations with integral coefficients.

A simple example of a lattice in Rn is the subgroup Zn. A more complicated example is the Leech lattice, which is a subgroup of R24.

See also Minkowski's theorem.


2. In other mathematical usage, a lattice is a partially ordered set in which all nonempty finite subsets have a least upper bound and a greatest lower bound (also called supremum and infimum, respectively). If L is the set and <= is the partial order then the least upper bound and greatest lower bound of a subset V of L are defined as follows:

  • A least upper bound of V is an element u in L such that
    • x <= u for all x in V, and
    • for any y in L such that x <= y for all x in V it holds that u <= y.
  • A greatest lower bound of V is an element l in L such that
    • l <= x for all x in V, and
    • for any y in L such that y <= x for all x in V it holds that y <= l.

It can easily be shown that the least upper bound and greatest lower bound of any set are always unique: if x and y are both a least upper bound of V then it follows that x <= y and y <= x, and since <= is antisymmetric it follows that x = y.

A lattice can also be algebraically defined as a set L, together with two binary operations ^ and v (pronounced meet and join, respectively), such that for any a, b, c in L,

a v a = a a ^ a = a (idempotency laws)
a v b = b v aa ^ b = b ^ a(commutativity laws)
a v (b v c) = (a v b) v c a ^ (b ^ c) = (a ^ b) ^ c(associativity laws)
a v (a ^ b) = aa ^ (a v b) = a(absorption laws)

If the two operations satisfy these algebraic rules then they define a partial order <= on L by the following rule:

a <= b if, and only if a v b = b.

Note that a v b = b is equivalent with a ^ b = a, so that the latter can also be used as the definition of the partial order. L, together with the partial order <= so defined, will then be a lattice in the above order theoretic sense.

Conversely, if a lattice (L, <=) is given, and we write a v b for the least upper bound of {a, b} and a ^ b for the greatest lower bound of {a, b}, then (L, v, ^) satisfies all the axioms of an algebraically defined lattice.

A lattice is said to be bounded if it has a greatest element and a least element. The greatest element is often denoted by 1 and the least element by 0. If x is an element of a bounded lattice then any element y of the lattice satisfying x ^ y = 0 and x v y = 1 is called a complement of x. A bounded lattice in which every element has a (not necessarily unique) complement is called a complemented lattice.

A lattice in which every subset (including infinite ones) has a supremum and an infimum is called a complete lattice. Complete lattices are always bounded. Many of the most important lattices are complete. Examples include:

The class of all lattices forms a category if we define a homomorphism between two lattices (L, ^, v) and (N, ^, v) to be a function f : L -> N such that

f(a ^ b) = f(a) ^ f(b)
f(a v b) = f(a) v f(b)

for all a, b in L. A bijective homomorphism whose inverse is also a homomorphism is called an isomorphism of lattices, and two involved lattices are called isomorphic.

Two important types of lattices are totally ordered sets and Boolean algebras. Lattices are also used to formulate pointless topology.


3. In materials science a lattice is a 3-dimensional array of regularly spaced points coinciding with the atom or molecule positions in a crystal. This is a special case of the first meaning given above.


/Talk