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 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 , and its infimum is the maximum of .
The requirement that a lattice has a minimum and a maximum is not universally followed, and lattices with this additional property are sometimes called bounded.
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 , partially ordered by divisibility. This is a lattice, with minimum and maximum . The infimum of a nonempty set is the greatest common divisor of the elements of , and its supremum is their least common multiple.
Given a set , its power set is a lattice under containment, In fact, in this case any nonempty subcollection of (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 , let denote the collection of finite subsets of , partially ordered under containment. If is infinite, is not a lattice (it lacks a maximum), but is.
The partition lattice has as elements the partitions of where, as usual, a partition of a set is a collection of pairwise disjoint nonempty subsets of whose union is . The set is ordered by refinement: If are partitions in , we say that iff every set in is a subset of a set in .
A lattice is complete iff any nonempty subset of has a supremum and an infimum.
With the same convention as above, we could as well say that any subset of admits a supremum and an infimum.
By the completeness of the real line, any compact interval is a complete lattice under the usual order.
is actually a complete lattice. The supremum of any infinite set is .
The collection of convex subsets of is a complete lattice under containment. The infimum of a nonempty family of convex sets is just their intersection. Its supremum is their convex hull, that is, the intersection of all the convex subsets of that contain all sets in .
Given a group , the collection of subgroups of , partially ordered by containment, is a complete lattice.
If is a linearly ordered set with a supremum and an infimum, then 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 : A cut of is a pair of subsets of such that is the collection of upper bounds of , and is the collection of lower bounds of . Note that this notion makes sense even if is just a partially ordered set. Given a cut in , we say that it admits a supremum iff exists.
Given any partially ordered set , there is always a complete lattice that contains , for example, the collection of downward closed subsets of , under containment, where is identified with .
Exercise 5 (MacNeille).
In fact, any poset admits a minimal completion , in the sense that is a complete lattice containing , and embeds (as a poset) into any complete lattice that contains (with the embedding fixing pointwise).
As with the rationals and the reals, a natural way of defining this minimal completion of is simply to take as the collection of all cuts in , partially ordered by saying that iff . 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 .
Suppose that is a cut of . Show that either and are disjoint, or else they meet at exactly one point.
Suppose that , , and . Let be the downward closure of , and let be the set of upper bounds of . Show that is a cut but is not. This is slightly different from the situation with and its completion , where commonly we require the two sets in a cut to have no elements in common. Does the Dedekind-MacNeille completion of actually coincide with ?
Exercise 6 (Birkhoff).
Say that a lattice is distributive iff for any , where denotes the meet of and , and denotes their join.
For example, 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.