# The Unapologetic Mathematician

## Lattices

A poset which has both least upper bounds and greatest lower bounds is called a lattice. In more detail, let’s say we have a poset $(P,\preceq)$ and give it two operations: meet (written $\wedge$) and join (written $\vee$). These satisfy the requirements that

• $x\preceq x\vee y$ and $y\preceq x\vee y$.
• If $x\preceq z$ and $y\preceq z$ then $x\wedge y\preceq z$.
• $x\wedge y\preceq x$ and $x\wedge y\preceq y$.
• If $z\preceq x$ and $z\preceq y$ then $z\preceq x\wedge y$.

Not every poset has a meet and a join operation, but if these operations do exist they are uniquely specified by these requirements. In fact, we can see this sort of like how we saw that direct products of groups are unique up to isomorphism: if we have two least upper bounds for a pair of elements then they must each be below or equal to the other, so they must be the same.

We can derive the following properties of the operations:

• $a\vee(b\vee c)=(a\vee b)\vee c$ and $a\wedge(b\wedge c)=(a\wedge b)\wedge c$.
• $a\vee b=b\vee a$ and $a\wedge b=b\wedge a$.
• $a\vee(a\wedge b)=a$ and $a\wedge(a\vee b)=a$.

from these we see that there’s a sort of duality between the two operations. In fact, we can see that these provide two commutative semigroup structures that happen to interact in a certain nice way.

Actually, it gets even better. If we have two operations on any set satisfying these properties then we can define a partial order: $x\preceq y$ if and only if $x=x\wedge y$. So we can define a lattice either by the order property and get the algebraic properties, or we can define it by the algebraic properties and get the order property from them.

In many cases, a lattice also satisfies $x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z)$, or equivalently $x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)$. In this case we call it “distributive”. A bit weaker is to require that if $x\preceq z$ then $x\vee(y\wedge z)=(x\vee y)\wedge z$ for all $y$. In this case we call the lattice “modular”.

A lattice may have elements above everything else or below everything else. We call a greatest element of a lattice $1$ and a least element ${0}$. In this case we can define “complements”: $x$ and $y$ are complements if $x\vee y=1$ and $x\wedge y=0$. If the lattice is distributive, then the complement of $x$ is unique if it exists. A distributive lattice where every element has a complement is called “Boolean”.

May 14, 2007 - Posted by | Algebra, Lattices, Orders

1. Ooooooooh, I know this from my Master’s thesis! Yay!

Comment by Mikael Johansson | May 15, 2007 | Reply

2. […] it turns out that, like the power set, this poset is actually a lattice. The meet is the intersection of subspaces, but the join isn’t their union. Indeed, the union […]

Pingback by The Sum of Subspaces « The Unapologetic Mathematician | July 21, 2008 | Reply

3. […] and the Lattice of Subspaces We know that the poset of subspaces of a vector space is a lattice. Now we can define complementary subspaces in a way that doesn’t depend on any choice of […]

Pingback by Orthogonal Complements and the Lattice of Subspaces « The Unapologetic Mathematician | May 7, 2009 | Reply

4. […] I want to prove two equations that hold in any orthocomplemented lattice. They are the famous DeMorgan’s […]

Pingback by DeMorgan’s Laws « The Unapologetic Mathematician | May 8, 2009 | Reply

5. […] can define two operations on such idempotent functions to make them into a lattice. The easier to define is the meet. Given idempotents and we define the meet to be their […]

Pingback by Characteristic Functions as Idempotents « The Unapologetic Mathematician | December 23, 2009 | Reply

6. […] combinations of these basis vectors form the lattice . Here, I do not mean “lattice” in the order-theory sense. I mean that this is a discrete collection of points in the vector space that is closed under […]

Pingback by Construction of Root Systems (setup) « The Unapologetic Mathematician | March 1, 2010 | Reply

7. […] before that the power set — the set of all the subsets of — is an orthocomplemented lattice. That is, we can take meets (intersections) , joins (unions) and complements of subsets of , and […]

Pingback by Algebras of Sets « The Unapologetic Mathematician | March 15, 2010 | Reply

8. […] we can then define orders in the usual manner: […]

Pingback by Boolean Rings « The Unapologetic Mathematician | August 4, 2010 | Reply

9. Could you draw a picture of a non-distributive lattice?

Comment by isomorphismes | January 9, 2015 | Reply

10. Consider a lattice with five elements: $\left\{0,1,a,b,c\right\}$. The top and bottom elements are $1$ and $0$, respectively; each of $a$, $b$, and $c$ live in the middle of those two, but none of them are comparable to each other. Now let’s calculate

\displaystyle\begin{aligned}a\vee(b\wedge c)&=a\vee0=a\\(a\vee b)\wedge(a\vee c)&=1\wedge1=1\end{aligned}

So this fails to be distributive.

Comment by John Armstrong | January 9, 2015 | Reply