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 and give it two operations: meet (written ) and join (written ). These satisfy the requirements that

• and .
• If and then .
• and .
• If and then .

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:

• and .
• and .
• and .

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: if and only if . 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 , or equivalently . In this case we call it “distributive”. A bit weaker is to require that if then for all . 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 and a least element . In this case we can define “complements”: and are complements if and . If the lattice is distributive, then the complement of is unique if it exists. A distributive lattice where every element has a complement is called “Boolean”.

Advertisements