lattice


A latticeMathworldPlanetmathPlanetmath is any poset L in which any two elements x and y have a least upper bound, xy, and a greatest lower boundMathworldPlanetmath, xy. The operationMathworldPlanetmath is called meet, and the operation is called join. In some literature, L is required to be non-empty.

A sublattice of L is a subposet of L which is a lattice, that is, which is closed under the operations and as defined in L.

The operations of meet and join are idempotentPlanetmathPlanetmath, commutativePlanetmathPlanetmathPlanetmath, associative, and absorptive:

x(yx)=x and x(yx)=x.

Thus a lattice is a commutative band with either operation. The partial orderMathworldPlanetmath relationMathworldPlanetmathPlanetmath can be recovered from meet and join by defining

xy if and only if xy=x.

Once is defined, it is not hard to see that xy iff xy=y as well (one direction goes like: xy=(xy)y=y(xy)=y(yx)=y, while the other direction is the dual of the first).

Conspicuously absent from the above list of properties is distributivity (http://planetmath.org/DistributiveLattice). While many nice lattices, such as face lattices of polytopes, are distributive, there are also important classes of lattices, such as partitionPlanetmathPlanetmath lattices (http://planetmath.org/PartitionLattice), that are usually not distributive.

Lattices, like posets, can be visualized by diagrams called Hasse diagrams. Below are two diagrams, both posets. The one on the left is a lattice, while the one on the right is not:

\entrymodifiers=[o]\xymatrix@!=1pt&&\ar@-[ld]\ar@-[rd]&&&\ar@-[ld]\ar@-[rd]&&\ar@-[ld]\ar@-[rd]&\ar@-[rd]&&\ar@-[ld]\ar@-[rd]&&\ar@-[ld]&\ar@-[rd]&&\ar@-[ld]&&&&&       \entrymodifiers=[o]\xymatrix@!=1pt&&\ar@-[ld]\ar@-[rd]&&&\ar@-[ld]\ar@-[rd]\ar@-[d]&&\ar@-[ld]\ar@-[rd]\ar@-[d]&\ar@-[rd]&\ar@-[d]&\ar@-[ld]\ar@-[rd]&\ar@-[d]&\ar@-[ld]&\ar@-[rd]&&\ar@-[ld]&&&&&

The vertices of a lattice diagram can also be labelled, so the lattice diagram looks like

\xymatrix@!=1pt&&a\ar@-[ld]\ar@-[rd]&&&b\ar@-[ld]\ar@-[rd]&&c\ar@-[ld]\ar@-[rd]&d\ar@-[rd]&&e\ar@-[ld]\ar@-[rd]&&f\ar@-[ld]&g\ar@-[rd]&&h\ar@-[ld]&&&i&&

Remark. Alternatively, a lattice can be defined as an algebraic system. Please see the link below for details.

Title lattice
\metatable