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.


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

403 – HW 1 – Recurrence relations

February 3, 2014

This set is due Tuesday, February 18, at the beginning of lecture.

TeX source.

Pdf file.