algebraic definition of a lattice

The parent entry (http://planetmath.org/Lattice) defines a lattice as a relational structure (a poset) satisfying the condition that every pair of elements has a supremum and an infimum. Alternatively and equivalently, a lattice $L$ can be a defined directly as an algebraic structure with two binary operations called meet $\wedge$ and join $\vee$ satisfying the following conditions:

• (idempotency of $\vee$ and $\wedge$): for each $a\in L$, $a\vee a=a\wedge a=a$;

• (commutativity of $\vee$ and $\wedge$): for every $a,b\in L$, $a\vee b=b\vee a$ and $a\wedge b=b\wedge a$;

• (associativity of $\vee$ and $\wedge$): for every $a,b,c\in L$, $a\vee(b\vee c)=(a\vee b)\vee c$ and $a\wedge(b\wedge c)=(a\wedge b)\wedge c$; and

• (absorption): for every $a,b\in L$, $a\wedge(a\vee b)=a$ and $a\vee(a\wedge b)=a$.

It is easy to see that this definition is equivalent to the one given in the parent, as follows: define a binary relation $\leq$ on $L$ such that

 $a\leq b\quad\mbox{ iff }\quad a\vee b=b.$

Then $\leq$ is reflexive by the idempotency of $\vee$. Next, if $a\leq b$ and $b\leq a$, then $a=a\vee b=b$, so $\leq$ is anti-symmetric. Finally, if $a\leq b$ and $b\leq c$, then $a\vee c=a\vee(b\vee c)=(a\vee b)\vee c=b\vee c=c$, and therefore $a\leq c$. So $\leq$ is transitive. This shows that $\leq$ is a partial order on $L$. For any $a,b\in L$, $a\vee(a\vee b)=(a\vee a)\vee b=a\vee b$ so that $a\leq a\vee b$. Similarly, $b\leq a\vee b$. If $a\leq c$ and $b\leq c$, then $(a\vee b)\vee c=a\vee(b\vee c)=a\vee c=c$. This shows that $a\vee b$ is the supremum of $a$ and $b$. Similarly, $a\wedge b$ is the infimum of $a$ and $b$.

Conversely, if $(L,\leq)$ is defined as in the parent entry, then by defining

 $a\vee b=\sup\{a,b\}\quad\mbox{ and }\quad a\wedge b=\inf\{a,b\},$

the four conditions above are satisfied. For example, let us show one of the absorption laws: $a\vee(a\wedge b)=a$. Let $c=\inf\{a,b\}\leq a=a\wedge b$. Then $c\leq a$ so that $\sup\{a,c\}=a$, which precisely translates to $a=a\vee c=a\vee(a\wedge b)$. The remainder of the proof is left for the reader to try.

Title algebraic definition of a lattice AlgebraicDefinitionOfALattice 2013-03-22 17:39:29 2013-03-22 17:39:29 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 03G10 msc 06B99