Bridge to Abstract Mathematics: Mathematical Proof and Structures

7.4 PARTIAL ORDERINGS 249

Two elements x and y of a poset (A, I;) are said to be comparable if and

only if either x I y or y I x. The integers 2 and 5 are not comparable in

the poset (N u {0), I,), whereas 6 and 18 are comparable in this poset.

The sets {I, 2) and {1,2,4) are comparable in (9(N), G), whereas 153)

and {3,4) are not. We may rephrase Definition 4 by noting that a poset

is a chain if and only if every two elements in it are comparable. Observe

then that (A, I), where A is any subset of R and I; is ordinary "less than

or equal to," is a totally ordered set, whereas both (9(S), E), S any set,

and (N u (01, I,) are not totally ordered.

If x and y are elements of a poset (A, I), we denote by x v y the element

lub {x, y), if it exists, while glb {x, y), when it exists, is denoted by x A y.

These are called, respectively, the join and the meet of x and y. This situation

is not very interesting if A is totally ordered; in that case x v y is simply

the "larger," whereas x A y is the "smaller" of x and y. But, in general, x v y

and x A y may be elements of A other than either x or y. In several of the

exercises you should pursue these ideas further, and in particular, calculate

certain meets and joins for the posets discussed earlier in the article.

Exercises

1. Consider the poset (N u {0), I,), where I, is the relation divides of Exam-
   ple 2.
   (a) Find the greatest and least elements of this poset, if they exist.
   (b) Find upper and lower bounds for the set (4,8, 16).
   *(c) Find upper and lower bounds for the set (4,6, 10).
   (d) Find upper and lower bounds for the set (3,5,7).
   (e) Find the greatest and least elements, when they exist, for the sets in (b), (c),
   and (d).
   (f) Give an example of an unbounded subset of this poset, if any exists.
   (g) Give a general description of m v n and m A n, where m and n are any non-
   negative integers.


2. Answer (a) through (g) of Exercise 1 for the poset (N u (01, I), where I is
   ordinary "less than or equal to."


3. Consider the poset (X, R) where X = {1,2,3,... ,9, 10) and R = {(x, x)lx E X) u
   ((1, x)lx E X) u {(x, WIX E X) U {(1,3), (1, 51, (1,7), (1991, (3951, (3,7), (3,9), (5,7),
   (5,9), (7,9)). Determine (when they exist):
   (a) lub (1,395) (b) lub {2,4,6)
   (c) glb {2,4,6) (d) the least element of {2,4,6)
   (e) an upper bound for the set {3,4, 5,6,8)


4. Let A be a poset. Let M and N be subsets of A such that lub M and Iub N both
   exist. Prove that if M E N, then lub M I lub N and glb M 2 glb N.


5. (a) Let M and N be subsets of an arbitrary set S. Clearly M r M u N and
   N r M u N. Prove that if X is any subset of S such that M E X and N c X,
   then M u N c X.