The Unapologetic Mathematician

Mathematics for the interested outsider

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 | 8 Comments

   

Follow

Get every new post delivered to your Inbox.

Join 389 other followers