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”.
Ooooooooh, I know this from my Master’s thesis! Yay!
[…] 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 |
[…] 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 |
[…] 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 |
[…] 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 |
[…] 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 |
[…] 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 |
[…] we can then define orders in the usual manner: […]
Pingback by Boolean Rings « The Unapologetic Mathematician | August 4, 2010 |
Could you draw a picture of a non-distributive lattice?
Consider a lattice with five elements:
. The top and bottom elements are
and
, respectively; each of
,
, and
live in the middle of those two, but none of them are comparable to each other. Now let’s calculate
So this fails to be distributive.