Lattice
1. In one 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). The term "lattice" comes from the shape of the Hasse diagrams of such orders (see partially ordered set).
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 a | a ^ 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) = a | a ^ (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 lattice of all subsets of a given set.
- The lattice of all sub-multisets of a multiset.
- The lattice of all partitions of a set.
- The unit interval [0,1] and the extended real number line.
- The lattice of all open sets of a topological space.
- The lattice of all convex subsets of a real or complex vector space.
- The lattice of all subgroups of a group.
- The lattice of all ideals of a ring.
- The lattice of all topologies on a set.
- The lattice of all transitive binary relations on a set.
- The lattice of all submodules of a module.
The lattice of submodules of a module has the special property that (x ^ y) v (x ^ z) = x ^ (y v (x ^ z)) for all x, y and z in the lattice. A lattice with this property is called a modular lattice. The lattice of normal subgroups of a group is also modular.
A lattice is called distributive if ^ distributes over v, that is, (x ^ y) v (x ^ z) = x ^ (y v z). Equivalently, v distributes over ^. All distributive lattices are modular. Two important types of distributive lattices are totally ordered sets and Boolean algebras. Distributive lattices are also used to formulate pointless topology.
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 the two involved lattices are called isomorphic.
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.
4. In digital signal processing, lattice filters are filters with a special recursive structure.