Bridge to Abstract Mathematics: Mathematical Proof and Structures

7.4 PARTIAL ORDERINGS 247

of X, we say that L is a least element of X. Analogously, an upper bound
U of a subset X of a poset (A, S) is said to be a greatest element of X if
U E X. By definition, a greatest element is an upper bound and a least
element is a lower bound. However, a subset of a poset that is bounded
above may or may not have a greatest element. In (R, I), (-a, 71 and
(... , -9, -6, -3,0,3,6} both have a greatest element (7 and 6, respec-
tively), but [4,7) and ( 1 - (l/n) 1 n E N} do not, even though the latter two
sets are both bounded above in R.
It is clear from a number of the preceding examples that upper and
lower bounds of subsets of posets are not unique. Uniqueness does occur,
however, in the situation covered by the next theorem.

THEOREM 1

Let (A, I) be a poset and X E A. If X has a greatest (respectively, least) element,

then that element is unique.

Proof To prove uniqueness, we proceed, as in Article 6.3, by letting u,

and u, be greatest elements of X. We claim that u, = u,. Since u, is

an upper bound for X and u, E X, then u, 5 u,. Reversing the roles of

u, and u,, we deduce u, 5 u,. By antisymmetry, we conclude u, = u,,

as desired. The proof of uniqueness for least elements is analogous. CI

EXAMPLE 3 Let S be any infinite set and let A = 9(S), the collection of

all subsets of S. Order A by inclusion, as in Example 1. Let X be the

collection of all finite subsets of S; clearly X is a subset of A. Note first

that X is bounded above in A, namely, S itself is "greater than or equal

to" every finite subset of S. But X has no greatest element, since there

is no single finite subset of S that is a superset of each finite subset of S.

On the other hand, X is bounded below in A and has a least element,

namely, 0.

The poset (N u (01, I,) of Example 2 has both a greatest and a least

element. You should use Exercise 2 ((d), (e)), Article 6.1, to determine these.

DEFINITION 3

Let (A, 5) be a partially ordeced set, and let X be a subset of A. An element U of

A is said to be the least upper bound of X, denoted U = lub X or U = sup X, if

U is the least element of the set of all upper bounds of X in A. An element L E A

is said to be the greatest lower bound of X, denoted L = glb X or L = inf X, if

L is the greatest element of the set of all lower bounds of X.

The expressions sup and inf are abbreviations for the Latin supremum

and injimum, respectively. The subset X = (0, 1) of the poset (R, 5) has

[I, m) as its set of upper bounds. Since 1 is clearly the least element of

[I, a), then 1 = lub X. The set Y = (0, 11 also has [I, m) as its set of

upper bounds, so that 1 = lub Y, also. Note that, in the first case, lub X $ X,

whereas lub YE Y in the second case.