248 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7By Theorem 1, a lub or glb, if it exists, is unique. But a subset of a poset
may fail to have a lub and/or a glb. For one thing, the subset may not be
bounded above, in which case its set of all upper bounds is empty and so
has no least element. Another possibility is that the subset might be bounded
above, but its set of all upper bounds may fail to have a least element. This
situation is illustrated in the following two examples.EXAMPLE 4 Consider the poset (Q, S) and let X = {r E Q (r2 S 2). X is
clearly bounded above in Q (by 2, e.g.), but it can be proved that X has
no least upper bound in Q (see Example 3, Article 9.3, for the details of
a closely related example). Note that the least upper bound of X, con-
sidered as a subset of the poset (R, <), is &, an irrational number.EXAMPLE 5 Let A be the collection of all subsets of N that are either finite
or whose complement is finite, ordered by inclusion. Let X be the subset
((21, {4), (61,.. .) of A. Then X is bounded above in A, for example,
(2, 3,4, 5,.. .}, {2,4, 5,6, 7,.. .) and A itself are all upper bounds for
X. But it can be shown that the collections of all upper bounds of X in A
has no least element, so that X has no lub in A.The definition of lub X may be rephrased in accordance with the follow-
ing two-part formulation. Under the assumptions in Definition 3, we say
u = lub X if and only if:(i) x < u for all x E X (i.e., u is an upper bound for X), and
(ii) for each y E A, if x 5 y for all x E X, then u y (i.e., u is "less than or
equal to" any other upper bound of X).A similar reformulation of the definition of glb is left to you.
When working in the abstract setting of an arbitrary partially ordered
set, we can err by relying too closely on properties of the most familiar
partial ordering, "less than or equal to, on R." For example, when working
with this poset, we never write an expression such as "x $ y." The reason
is that we may write instead y x, and indeed the stronger statement y < x,
to convey this idea. We do not have this luxury in every poset, however.
In (9(N), E), letting X =- { 1,2,3) and Y = {2,3,4), we note that neither
X c Y nor Y E X is true. Note then that the statement X $ Y cannot be
translated into Y r X. The same is true of the example (N u (01, s2) of
Example 2. The falsity of 5 5, 2 does not translate into 2 l2 5. In fact,
neither of the two integers 2 and 5 divides the other. The issue involved
in these examples is the focus of the following definition.
DEFINITION 4
The partially ordered set (A, I) is said to be totally ordered (or linearly ordered
or a chain) if and only if, for any elements x, y E A, either x I y or y I x.