Section 16.2 Extreme values
We will close by discussing various “extreme” features a partial order can have. These are elements that are the “smallest” and “largest” among a specified subset, or among the entire partially ordered set.
First, a definition that might seem silly at first, but it is important to be specific and transparent about what we mean:
Definition 16.2.1.
Let \(X\) be a partially ordered set. We say that \(x\) is less than \(y\) (in the partial order) if \(x \preceq y\text{,}\) and then \(y\) is greater than \(x\text{.}\)
(Again, “less than” means “less than or equal to”).
Definition 16.2.2.
An element \(x\) in a partially ordered set \(X\) is minimal if it is not greater than any other element. Likewise an element is maximal if it is not less than any other element. If the minimal or maximal element is unique, it is called the minimum or maximum.
It is key to note that “minimal” does not mean “less than everything”, it means “greater than nothing.” This is the reason a partial order can have multiple minimal elements.
Example 16.2.3.
Consider the order \(\{(w,w), (w,y), (x,x),\) \((x,y), (x,z), (y,y), (z,z)\}\text{,}\) diagrammed below:
The partial order diagram has \(w\) and \(x\) at the bottom and \(z\) and \(y\) at the top. The element \(x\) is related to both \(y\) and \(z\) but \(w\) is only related to \(y\text{.}\)
This partial order has two minimal elements, \(w\) and \(x\text{,}\) even though \(w\) is not less \(z\text{.}\) Likewise, it has two maximal elements, \(z\) and \(y\text{,}\) although \(z\) is not greater than \(w\text{.}\)
Definition 16.2.5.
Fix a subset \(A\) of the partially ordered set \(X\text{.}\) A lower bound of \(A\) is any element of \(X\) that is less than every element in \(A\text{.}\) Likewise, an upper bound of \(A\) is any element of \(X\) that is greater than every element in \(A\text{.}\)
Notice that the lower and upper bounds of a set may, but need not be, contained in the set.
Definition 16.2.6.
Let \(X\) be a partially ordered set and let \(A \subseteq X\text{.}\) The least upper bound, sometimes called the infemum and denoted \(\text{lub }A\) or \(\text{inf }A\text{,}\) of \(A\) is the unique minimum element of the set of upper bounds of \(A\text{.}\)
The greatest lower bound, also called the supremum and denoted \(\text{glb }A\) or \(\text{sup }A\), of \(A\) is the unique maximum element of the set of lower bounds of \(A\text{.}\)
Example 16.2.7.
Consider the order
and the subset \(A=\{b,c,d\}\) of the ordered set.
The partial order diagram has a minimal element \(a\) related to \(b\text{,}\) which is related to \(c\) and \(d\text{,}\) each of which is related to \(e\) and \(f\text{.}\) A second minimal element, \(g\text{,}\) is also related to \(d\text{.}\)
The lower bounds of \(A\) are \(a\) and \(b\text{.}\) Since partial orders are reflexive, \(b\) is “less than” (remember, really “less than or equal to”) itself. Because \(g\) is only less than \(d\text{,}\) it is not a lower bound of \(A\text{.}\) Since \(a \preceq b\text{,}\) \(b\) is the greatest lower bound.
The upper bounds of \(A\) are the elements \(e\) and \(f\text{,}\) because both are greater than every element in \(A\text{.}\) However, since \(e\) and \(f\) are incomparable, neither is the least upper bound.
Next, consider the set \(B=\{a,b,d,g\}\text{.}\) The upper bounds of \(B\) are \(d\text{,}\) \(e\text{,}\) and \(f\text{.}\) The least of these elements is \(d\text{,}\) so it is the least upper bound. There are no lower bounds, and hence no greatest lower bound, because there is no element that is less than both \(a\) and \(g\text{.}\)
We have discussed the idea of a “tightest” lower or upper bound before, when we discussed the growth rates of sequences. For instance, though \(n^2 +5n + 1\) is big-O of things like \(n^3\text{,}\) \(2^n\text{,}\) and \(n!\text{,}\) the class of functions that are big-O of \(n^2\) are the least upper bound on the growth rate of \(n^2+5n+1\text{.}\)
You may have noticed that some diagrams tend to sprawl out in various directions, while others have some regularity to their shapes. Our final definition will formalize that idea.
Definition 16.2.9.
A partially ordered set is a lattice if any pair of elements has both a least upper bound and a greatest lower bound.
Example 16.2.10.
Consider again the partial order diagrammed below:
The partial order diagram has a minimal element \(a\) related to \(b\text{,}\) which is related to \(c\) and \(d\text{,}\) each of which is related to \(e\) and \(f\text{.}\) A second minimal element, \(g\text{,}\) is also related to \(d\text{.}\)
This partial order is not a lattice, because for instance, the pair \(\{a,g\}\) fails to have a greatest lower bound.
Example 16.2.12.
The partial order diagrammed below is a lattice:
The partial order diagram has a minimum element \(x_0\) related to \(x_1\text{,}\) which is related to \(x_2\) and \(x_3\text{.}\) The element \(x_2\) is related to \(x_4\) and \(x_3\) is related to \(x_5\text{.}\) Both \(x_4\) and \(x_5\) are related to \(x_6\text{.}\) The element \(x_5\) also branches off to \(x_7\text{,}\) but both \(x_6\) and \(x_7\) are related to the maximum element, \(x_8\text{.}\)
Pick any pair of elements in the lattice and you can see that they have a least upper bound and a greatest lower bound. If two elements are comparable, then the least upper bound is the larger one and the greatest lower bound is the smaller one. Otherwise:
If the two incomparable elements are between \(x_1\) and \(x_6\text{,}\) then the least upper bound is \(x_6\) and the greatest lower bound is \(x_1\text{.}\)
If the two incomparable elements are between \(x_5\) and \(x_8\text{,}\) then the least upper bound is \(x_8\) and the greatest lower bound is \(x_5\text{.}\)
Example 16.2.14.
A linear order doesn't strike us as a lattice in the common sense of the word (like diagonally arranged planks of wood on the side of a building), but it is. Take any pair \(\{x,y\}\) in a totally ordered set and assume without loss of generality that \(x \preceq y\text{.}\) (Otherwise simply flip the labels.) Then, \(\text{lub }\{x,y\} = y\) and \(\text{glb }\{x,y\} = x\text{.}\)
Example 16.2.15.
A Boolean algebra can be regarded as a lattice by defining the partial order as follows: \(a \preceq b\) if and only if \(a \vee b = b\) (equivalently, \(a \wedge b = a\)). This applies to structures like bit strings, Boolean matrices, a power set, and certain families of statements.
On the other hand, something called a complemented distributive lattice (a lattice where elements have complements and there is a certain idea of distributivity) will yield a Boolean algebra by defining \(a \vee b = \text{lub }\{a,b\}\) and \(a \wedge b = \text{glb }\{a,b\}\text{.}\)