# lattice

A lattice is any poset $L$ in which any two elements $x$ and $y$ have a least upper bound, $x\lor y$, and a greatest lower bound, $x\land y$. The operation $\land$ is called meet, and the operation $\lor$ 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 $\land$ and $\lor$ as defined in $L$.

The operations of meet and join are idempotent, commutative, associative, and absorptive:

 $x\land(y\lor x)=x\mbox{ and }x\lor(y\land x)=x.$

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

 $x\leq y\text{\ if and only if\ }x\land y=x.$

Once $\leq$ is defined, it is not hard to see that $x\leq y$ iff $x\lor y=y$ as well (one direction goes like: $x\lor y=(x\land y)\lor y=y\lor(x\land y)=y\lor(y\land x)=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 partition 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{&&\bullet\ar@{-}[ld]\ar@{-}[rd]&&\\ &\bullet\ar@{-}[ld]\ar@{-}[rd]&&\bullet\ar@{-}[ld]\ar@{-}[rd]&\\ \bullet\ar@{-}[rd]&&\bullet\ar@{-}[ld]\ar@{-}[rd]&&\bullet\ar@{-}[ld]\\ &\bullet\ar@{-}[rd]&&\bullet\ar@{-}[ld]&\\ &&\bullet&&}\hskip 56.905512pt\entrymodifiers={[o]}\xymatrix@!=1pt{&&\bullet% \ar@{-}[ld]\ar@{-}[rd]&&\\ &\bullet\ar@{-}[ld]\ar@{-}[rd]\ar@{-}[d]&&\bullet\ar@{-}[ld]\ar@{-}[rd]\ar@{-}% [d]&\\ \bullet\ar@{-}[rd]&\ar@{-}[d]&\ar@{-}[ld]\ar@{-}[rd]&\ar@{-}[d]&\bullet\ar@{-}% [ld]\\ &\bullet\ar@{-}[rd]&&\bullet\ar@{-}[ld]&\\ &&\bullet&&}$

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