28 2. Background and d, and it is the least upper bound: any element that is greater than or equal to both c and d is also greater than or equal to f. The elements f and g are upper bounds for the pair a and b, but not the least upper bound that is d. A lower bound for a pair of elements is defined symmetrically: an element that is less than or equal to both of the given elements. The greatest lower bound is a lower bound x such that any other lower bound is less than or equal to x. Note that even when lower and upper bounds exist, there need not be greatest lower or least upper bounds. This can happen in two ways: two incomparable bounds (think of a V, where the lower point is below both upper points, but the upper points are incomparable), or an infinite ascending or descending sequence of elements that limits to an element not in the poset (such as an open interval in the rational numbers with irrational endpoints). Example 2.3.22. P(N) ordered by subset inclusion is a partially ordered set. It is easy to check the relation is reflexive, transitive, and an- tisymmetric. Not every pair of elements is comparable: for example, neither {1, 2, 3} nor {4, 5, 6} is a subset of the other. This poset actu- ally has some very nice properties that not every poset has: it has a top element (N) and a bottom element (∅), and every pair of elements has both a least upper bound (here, the union) and a greatest lower bound (the intersection). If we were to graph this, it would look like an infinitely-faceted diamond with points at the top and bottom. Example 2.3.23. Along the same lines as Example 2.3.22, we can consider the power set of a finite set, and then we can graph the poset that results. Let A = {a, b, c}. Denote the set {a} by a and the set {b, c} by ˆ, and likewise for the other three elements. The graph is the transitive closure of the graph shown in Figure 2.1. Exercise 2.3.24. Prove that every pair of elements in a poset has at most one greatest lower bound and at most one least upper bound. Exercise 2.3.25. How many partial orders are possible on a set of two elements? Three elements?
Previous Page Next Page