Lattices

A lattice is an ordered set with the extra property that for every two elements of the lattice, a supremum and an infimum must exist, and these also belong to the lattice.

Upper and lower sets

We start with a set M on which some order ≤ is defined. This order can be arbitrary, but it must satisfy the conditions of an order relation.

Next we take some element a of the set M. We define the upper set of the element a in M as all the x ∈ M that are greater than or equal to a, that is, for which a ≤ x.

If we take the positive integers as our set and the element a = 7, the upper set is the set of numbers {7, 8, 9, …}. On the real numbers we would get the interval [7, ∞).

Now take the set M = 2^ℤ+ – this is a power set, that is, the set of all subsets of the positive integers. So it consists of all the sets we can build from the positive integers. The order will be generated by the subset relation. So, for example, {3, 5} ≤ {3, 4, 5}.

The upper set of the set {1, 2, 3, 4} consists of all the sets that contain the elements 1, 2, 3, 4. For example, the set {1, 2, 3, 4, 5, 6, 9} or {1, 2, 3, 4, 2323, 454645}. The set {1, 2, 3, 4} itself is also in the upper set.

We define the lower set similarly – it contains the elements that are less than or equal to the element a. For a = 7 and M the positive integers, we get the set {1, 2, 3, 4, 5, 6, 7}. These are the positive integers that are less than or equal to seven.

For the set {1, 2, 3, 4} we get all the subsets of this set.

Upper and lower sets of several elements

In the previous section we defined these sets for a single element. But we can also define them for several elements. If we have a set M and elements a, b, then their common upper set contains the elements that are greater than or equal to both a and b at the same time. In other words, we work out the upper sets of both elements and take their intersection. This gives us the elements that are certainly greater than a and at the same time greater than b.

Let’s stay with the positive integers: a = 3, b = 5. All the elements greater than or equal to a form the set {3, 4, 5, 6, …} and those greater than or equal to b form {5, 6, 7, 8, …}. Now we take the intersection, which again gives the set {5, 6, 7, 8, …}. If the set is totally ordered, it is enough to find the greater of the two elements and work out its upper set.

For sets it won’t be so simple. Let’s try to work out the lower set of the sets a = {1, 2, 3} and b = {2, 3, 4}. It consists of all the sets that are subsets of both a and b. Is the set {1, 2, 3} a subset of a? Yes. Is it also a subset of b? No. So this set will not be in the lower set.

Let’s see what the largest set that is a subset of both a and b will be. It is clearly the set {2, 3}, which is the intersection a ∩ b. It is in the lower set, and so are all the subsets of this set. Because if, for example, ∅ ⊆ {2, 3} and at the same time {2, 3} ⊆ a ∧ {2, 3} ⊆ b, then certainly ∅ ⊆ a ∧ ∅ ⊆ b as well. This follows from transitivity.

Finally, let’s define the upper and lower sets for a whole set, not just a pair of elements. Let M be a set and A ⊆ M a set for which we want to work out the upper and lower sets. Then:

$$\begin{array}{rcl}H(A)& =& \{x|\mathrm{\forall }a\in A:x\ge a\}\\ D(A)& =& \{x|\mathrm{\forall }a\in A:x\le a\}\end{array}$$

Supremum and infimum

Using these sets we can easily define the infimum and supremum. If we have a set M and an element a ∈ M, then the supremum and the infimum of the element a are again the same element a.

But if we want to find the supremum of two elements of M, the elements a, b, we need a different approach. The supremum of the elements a, b, written a ∨ b or sup(a, b), is equal to the least element of the upper set of a, b. So we work out all the elements that are greater than or equal to both a and b, and from those we take the least element – not a minimal one, the least. A least element need not exist in general, so a supremum need not exist in general either.

To find the infimum, we first find the lower set of both elements and then find its greatest element.

Example: we already know that the upper set of the numbers 3 and 5 is the set {5, 6, 7, …}. Its least element is five. So sup(3, 5) = 5.

We also know that the lower set of the sets a = {1, 2, 3} and b = {2, 3, 4} is the set of all subsets of the set {2, 3}. These are the sets {2, 3}, {2}, {3} and ∅. The greatest of them is the set {2, 3}. So this set is the infimum of the sets a, b. We write a ∧ b = {2, 3} or inf(a, b) = {2, 3}.

Definition of a lattice

A lattice S is an ordered set in which, for any two elements a, b ∈ S, a supremum and an infimum exist, and this infimum and supremum belong to the set S. So we can say that an ordered set S is a lattice if

$$\mathrm{\forall }a,b\in S:sup(a,b)\in S\text{and}inf(a,b)\in S$$

A simple example of a lattice is the real numbers with the usual order. Here sup(a, b) = max(a, b) and inf(a, b) = min(a, b), which are always real numbers.

A system of sets ordered by the subset relation, as we introduced earlier, is also a lattice. Here sup(a, b) = a ∪ b and inf(a, b) = a ∩ b. These are again sets from the system of sets.

If we take as the system of sets S all the two-element subsets of the positive integers (e.g. {1, 2}, {7, 19}, …), then this set is not a lattice, because, for example, sup({1, 2}, {3, 4}) = {1, 2, 3, 4} and the set {1, 2, 3, 4} is not an element of the set of all two-element subsets of the positive integers.