250 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7(b) Let M and N be subsets of an arbitrary set S. Clearly M n N r M and
M n N E N. Prove that if X is any subset of S such that X E M and X c N,
then X r M n N.- (a) Let A = 9(S), S any set, and order A by inclusion. Let M and N be any
elements of A (i.e., M and N are subsets of S)
(i) Describe M v N, the join of M and N in the poset (A, c).
(ii) Describe M A N, the meet of M and N in A.
(Recall M v N = lub {M, N) and M AN = glb {M, N).)
(b) Assume S is infinite and let C = {M,, M,,.. .) be an infinite collection of
subsets of S, indexed by N. Note that C is a subset of A = S). Order the
latter by inclusion, as in (a). Describe lub C and glb C in the poset (A, G). - (a) Let A = 9(N) be ordered by inclusion. Find lub C and glb C for each of
the following subsets C of A:
(0 Cl = {{I}, {3), {5}, .I
(ii) c2 = {{I}, {I, 3}, {I, 3,519 .}
*(iii) C3 = {{I, 3, 5, 7,.. .), {3, 5,7,9,.. .), {5, 7,9, 11,.. .I,.. .)
(b) Thesubset C = {{2), (41, (61,.. .) oftheposetin(a)haslub C = {2,4,6,.. .).
Explain why {2,4,6,.. .) is not the lub of C in the poset of Example 5. Explain
informally why C has no lub in that poset. - (a) Let S be any finite set and let A = 9(S). Define a relation R on A by the
rule (M, N) E R if and only if n(M) I n(N), for any subsets M and N of S. Is R
a partial ordering on A?
(b) Recall the equivalence relation R17 on A = 9(S) (Example 6, Article 7.1) that
identifies any two subsets of S having the same number of elements. Let X =
AIR,,, noting that the elements of X are equivalence classes [MI of subsets of S,
where two subsets M and N of S are in the same equivalence class if and only
if n(M) = n(N). Define a relation I on X by the rule [MI I [N] if and only if
n(M) I n(N).
*(i) Prove that this relation is well defined; that is, verify that if [MI] = [M,]
and [N = [N 2], then [M I [N - [M2] I [N,].
(ii) Prove that I is a partial ordering on X.
/ (iii) Prove that I is a total ordering on X.
/
- Let (X, I) be a poset. An element m E X is said to be a maximal element of X
if and only if, for any y E X, if m I y, then m = y.
(a) Formulate an analogous definition of minimal element of a poset.
(b) Prove that if a poset (X, I) has a greatest element u, then u is the unique
maximal element of X. State the analogous result for minimal elements.
(c) Let S = {1,2,... , 10) and let X = P(S) - (0, S); that is, X consists of all
nonempty proper subsets of S. Order X by inclusion; that is, consider the poset
(X, E). Find five maximal elements and five minimal elements of this poset.
(d) Consider the set X = N - (1). Order this set by "divisibility" (cf., Example 5,
Article 7.1). How many minimal elements are contained in this poset? maximal
elements? Answer the same question if X = N u (0).
(e) Prove that if a poset (X, 2) is totally ordered, then any maximal element is the
greatest element of X, whereas every minimal element is the least element.