## Posets and Lattices

February 4, 2014

Definition 1.
A lattice is a nonempty poset with a maximum and a minimum, and such that any nonempty finite subset has a supremum (or join) and an infimum (or meet).

One could just as well simply say that a lattice is a poset $\mathcal L$ where any finite subset has a supremum and an infimum, using the (natural) convention that the supremum of the empty set is the minimum of $\mathcal L$, and its infimum is the maximum of $\mathcal L$.

The requirement that a lattice $\mathcal L$ has a minimum and a maximum is not universally followed, and lattices with this additional property are sometimes called bounded.

Examples 2.
Any linearly ordered set with a minimum and a maximum is a lattice. In this case, all infima and suprema of nonempty finite sets are just minima and maxima.

For a more interesting example, consider $\mathbb N$, partially ordered by divisibility. This is a lattice, with minimum $1$ and maximum $0$. The infimum of a nonempty set $X\ne\{0\}$ is the greatest common divisor of the elements of $X$, and its supremum is their least common multiple.

Given a set $X$, its power set $\mathcal P(X)$ is a lattice under containment, $\subseteq.$ In fact, in this case any nonempty subcollection of $\mathcal P(X)$ (whether finite or not) has an infinimum (its intersection) and a supremum (its union). This is an example of a complete lattice, as in Definition 3.

Given a set $X$, let $\mathrm{Fin}(X)$ denote the collection of finite subsets of $X$, partially ordered under containment. If $X$ is infinite, $\mathrm{Fin}(X)$ is not a lattice (it lacks a maximum), but $\{X\}\cup\mathrm{Fin}(X)$ is.

The partition lattice $\Pi_n$ has as elements the partitions of $\{1,\dots,n\}$ where, as usual, a partition of a set $A$ is a collection $\mathcal A$ of pairwise disjoint nonempty subsets of $A$ whose union is $A$. The set $\Pi_n$ is ordered by refinement: If $x,y$ are partitions in $\Pi_n$, we say that $x\le y$ iff every set in $x$ is a subset of a set in $y$.

Definition 3.
A lattice $\mathbb P=(P,\le)$ is complete iff any nonempty subset of $P$ has a supremum and an infimum.

With the same convention as above, we could as well say that any subset of $P$ admits a supremum and an infimum.

Examples 4.
By the completeness of the real line, any compact interval ${}[a,b]\subseteq\mathbb R$ is a complete lattice under the usual order.

$(\mathbb N,|)$ is actually a complete lattice. The supremum of any infinite set is $0$.

The collection of convex subsets of $\mathbb R^2$ is a complete lattice under containment. The infimum  of a nonempty family $\mathcal F$ of convex sets is just their intersection. Its supremum is their convex hull, that is, the intersection of all the convex subsets of $\mathbb R^2$ that contain all sets in $\mathcal F$.

Given a group $G$, the collection $\mathrm{Sub}(G)$ of subgroups of $G$, partially ordered by containment, is a complete lattice.

If $X$ is a linearly ordered set with a supremum and an infimum, then $X$ is a complete lattice iff it is Dedekind complete, meaning that any cut admits a supremum. Cuts are defined as a natural generalization of the usual concept for $\mathbb Q$: A cut of $X$ is a pair $(A,B)$ of subsets of $X$ such that $B$ is the collection of upper bounds of $A$, and $A$ is the collection of lower bounds of $B$. Note that this notion makes sense even if $X$ is just a partially ordered set. Given a cut $(A,B)$ in $X$, we say that it admits a supremum iff $\sup(A)$ exists.

Given any partially ordered set $P$, there is always a complete lattice that contains $P$, for example, the collection of downward closed subsets of $P$, under containment, where $p\in P$ is identified with $\{x\in P\mid x\le p\}$.

Exercise 5 (MacNeille).
In fact, any poset $\mathbb P=(P,\le)$ admits a minimal completion $\mathcal L$, in the sense that $\mathcal L$ is a complete lattice containing $\mathbb P$, and $\mathcal L$ embeds (as a poset) into any complete lattice that contains $\mathbb P$ (with the embedding fixing $P$ pointwise).

As with the rationals and the reals, a natural way of defining this minimal completion $\mathcal L$ of $\mathbb P$ is simply to take as $\mathcal L$ the collection of all cuts in $\mathbb P$, partially ordered by saying that $(A,B)\le(C,D)$ iff $A\subseteq C$. This construction is called the Dedekind-MacNeille (or normal) completion, first introduced in MacNeille [Mac37]. Verify that it indeed results in the minimal completion of $\mathbb P$.

Suppose that $(A,B)$ is a cut of $\mathbb P$. Show that either $A$ and $B$ are disjoint, or else they meet at exactly one point.

Suppose that $a\in P$, $A\subseteq\mathbb P$, and $a=\max(A)=\sup(A\setminus\{a\})$. Let $\hat A$ be the downward closure of $A$, and let $B$ be the set of upper bounds of $A$. Show that $(\hat A,B)$ is a cut but $(\hat A\setminus\{a\},B)$ is not. This is slightly different from the situation with $\mathbb Q$ and its completion $\mathbb R$, where commonly we require the two sets in a cut to have no elements in common. Does the Dedekind-MacNeille completion of $\mathbb Q$ actually coincide with $\mathbb R$?

Exercise 6 (Birkhoff).
Say that a lattice $\mathcal L$ is distributive iff $p \land (q \lor r) = (p \land q) \lor (p \land r)$ for any $p,q,r\in\mathcal L$, where $a \land b$ denotes the meet of $a$ and $b$, and $a\lor b$ denotes their join.

For example, $\mathcal P(X)$ is a distributive lattice. Give an example of a lattice that is not distributive.

Prove Birkhoff’s representation theorem, also called the fundamental theorem for finite distributive lattices, stating that any such lattice is isomorphic to a lattice of finite sets, where the lattice operations are just given by union and intersection.

References

[Mac37]
Holbrook M. MacNeille.
Partially ordered sets.
Trans. Amer. Math. Soc. 42 (3), (1937), 416–460.
MR1501929.