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?
Previous Page Next Page