Bridge to Abstract Mathematics: Mathematical Proof and Structures

246 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7

EXAMPLE 1 Let S be any set and let A = g(S). Let 5, represent the sub-

set relation on A; that is, M I, N if and only if M G N (recall the

relation R,, from Example 6, Article 7.1). Note the interpretations of

the three properties R, AS, T in this example. Reflexive: Every set is a

subset of itself [true by Fact 1(2), Article 1.41. Antisymmetric: for any

sets M and N, if M E N and N E M, then M = N [Fact 1(4), Article 1.41.

Transitive: for any sets L, M, and N, if L E M and M E N, then L E N

[Fact 1(6), Article 1.41.

Hence (P(S), G) is a partially ordered set for any set S. It is often

said that the set Y(S) is ordered by inclusion. Cl

EXAMPLE 2 Let A be the set N u (0) of all nonnegative integers and let

s2 represent the relation divides; that is, given m, n E A, m I, n if and

only if m divides n (also commonly denoted mln; recall Example 5,

Article 7.1, and the paragraph preceding Example 7, Article 5.4). To

show that I, is a partial ordering on A, we note first that every integer

divides itself [Exercise 2(c), Article 6.11. Second, if m 1 n and n lm, then

(since m and n are nonnegative) we may conclude m = n. [Exercise 2(c),

Article 6.11. Third, if m 1 n and n 1 p, then mlp [Exercise 2(a), Article 6.11

for any m, n, p E A, so that 5, is transitive.

Note that the relation <, of Example 2 is a different partial ordering

on N u (0) from the ordinary "less than or equal to" on that set. For

example, 2 5 5, but it is not the case that 2 I, 5 since 2 does not divide 5.

DEFINITION 2

Let (A, 5) be a partially ordered set and let X be a subset of A. We say that an

element L of A is a lower bound for X if and only if L I x for all x E X. X is said

to be bounded below in A if X has a lower bound in A. An element U of A

is said to be an upper bound for X if and only if x I U for all x E X. X is bounded

above in A if and only if X has an upper bound in A. Finally, X is said to be

bounded in A if and only if X is both bounded above and bounded below in A,

and unbounded in A if and only if it is not bounded.

/'
In the poset (R, I), where 2 represents ordinary "less than or equal to,"
the subsets N, Z, and Q are all unbounded subsets, although N & bounded
below. The subset (... , --6, - 3,0,3) is bounded above (by 3, or 15, or
n, e.g.) in R, but not below. The interval (5, GO) is bounded below and not
above, but the interval (- 3,8) is bounded. Boundedness depends on the
poset as well as on the subset. For example, the interval (0, 11 is bounded
below as a subset of (R, I), but not as a subset of (R+, I), where R+ rep-
resents the set of all positive real numbers.
A lower or upper bound for a subset X of a partially ordered set A may
or may not be contained in X. For example, in (R, I), 2 is a lower bound
6
both for [2,3] and for (2,3]. If a lower bound L for X is also an element