PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: Very high
lattice (Definition)

A lattice is any non-empty 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. 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\le y \text{\ if and only if\ } x\land y = x $$ Once $\le$ is defined, it is not hard to see that $x\le 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. While many nice lattices, such as face lattices of polytopes, are distributive, there are also important classes of lattices, such as partition lattices, 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:

$\displaystyle \entrymodifiers={[o]} \xymatrix @!=1pt { & & \bullet \ar@{-}[ld] ... ...[ld] \ & \bullet \ar@{-}[rd] & & \bullet \ar@{-}[ld] & \ & & \bullet & & } $
The vertices of a lattice diagram can also be labelled, so the lattice diagram looks like

$\displaystyle \xymatrix @!=1pt { & & a \ar@{-}[ld] \ar@{-}[rd] & & \ & b \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.




"lattice" is owned by mps. [ full author list (5) | owner history (1) ]
(view preamble | get metadata)

View style:

See Also: semilattice, distributive lattice, a semilattice is a commutative band, partition lattice, algebraic category of LMn logic algebras, closed sublattice

Other names:  absorptive
Also defines:  sublattice, absorption

Attachments:
algebraic definition of a lattice (Definition) by CWoo
difference of lattice elements (Definition) by porton
Log in to rate this entry.
(view current ratings)

Cross-references: link, algebraic system, vertices, right, Hasse diagrams, diagrams, polytopes, face, iff, relation, partial order, band, associative, commutative, idempotent, closed under, join, meet, operation, greatest lower bound, least upper bound, elements, poset
There are 122 references to this entry.

This is version 21 of lattice, born on 2002-02-24, modified 2008-10-25.
Object id is 2593, canonical name is Lattice.
Accessed 18504 times total.

Classification:
AMS MSC06B99 (Order, lattices, ordered algebraic structures :: Lattices :: Miscellaneous)
 03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures)

Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)