|
Contents
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 another 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, or, equivalently, a ^ b = a.
L, together with the partial order <= so defined, will then be a lattice in the above order-theoretic sense.
Conversely, if an order-theoretic 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 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 submodules 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 partitions of a set.
The Knaster-Tarski theorem states that the set of fixed points of a monotone function on a complete lattice is again a complete lattice.
The lattice of submodules of a module and the lattice of normal subgroups of a group have the special property that
x v (y ^ (x v z)) = (x v y) ^ (x v z)
for all x, y and z in the lattice.
A lattice with this property is called a modular lattice.
The condition of modularity can also be stated as follows: If x <= z then then for all y we have the identity x v (y ^ z) = (x v y) ^ z.
A lattice is called distributive if v distributes over ^, that is,
x v (y ^ z) = (x v y) ^ (x v z).
Equivalently, ^ distributes over v. All distributive lattices are modular.
Two important types of distributive lattices are totally ordered sets and Boolean algebras (like the lattice of all subsets of a given set). The lattice of natural numbers, ordered by divisibility, is also distributive.
Distributive lattices are 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.
| Elsewhere |  | |
Search engine
Web directory
|
CONTENTS:
|
