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 ˆ, a

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?