350
Relations, Functions, and Matrices
32. For Exercise 31, name any least elements, minimal elements, greatest elements, and maximal elements.
33. Let (S, d) be a partially ordered set, and let A # S. Prove that the restriction of d to A is a partial
ordering on A.
34. a. Draw the Hasse diagram for the partial ordering “x divides y” on the set 52, 3, 5, 7, 21, 42, 105, 2106.
Name any least elements, minimal elements, greatest elements, and maximal elements. Name a totally
ordered subset with four elements.
b. Draw the Hasse diagram for the partial ordering “x divides y” on the set 53, 6, 9, 18, 54, 72, 108, 1626.
Name any least elements, minimal elements, greatest elements, and maximal elements. Name any
unrelated elements.
35. Draw the Hasse diagram for each of the two partially ordered sets.
a. S = 51, 2, 3, 5, 6, 10, 15, 306
b. S = `(51, 2, 36)
x r y 4 x divides y
A r B 4 A # B
What do you notice about the structure of these two diagrams?
36. For each Hasse diagram of a partial ordering in the accompanying figure, list the ordered pairs that belong
to the relation.
d
a
e
b
f
c
5
1
4
3
2
2
1
3
4
5
37. Let (S, r) and (T, s) be two partially ordered sets. A relation m on S × T is defined by
(s 1 , t 1 ) m (s 2 , t 2 ) 4 s 1 r s 2 and t 1 s t 2 . Show that m is a partial ordering on S × T .
38. Let r be a binary relation on a set S. Then a binary relation called the inverse of r, denoted by r
−1
, is
defined by x r
−1
y 4 y r x.
a. For r = 5(1, 2), (2, 3), (5, 3), (4, 5)6 on the set N, what is r
−1
?
b. Prove that if r is a reflexive relation on a set S, then r
−1
is reflexive.
c. Prove that if r is a symmetric relation on a set S, then r
−1
is symmetric.
d. Prove that if r is an antisymmetric relation on a set S, then r
−1
is antisymmetric.
e. Prove that if r is a transitive relation on a set S, then r
−1
is transitive.
f. Prove that if r is an irreflexive relation on a set S (see Exercise 26), then r
−1
is irreflexive.
g. Prove that if r is an asymmetric relation on a set S (see Exercise 26), then r
−1
is asymmetric.
39. Prove that if a binary relation r on a set S is reflexive and transitive, then the relation r d r
−1
is an
equivalence relation (see Exercise 38 for the definition of r
−1
).
40. a. Let (S, r) be a partially ordered set. Then r
−1
can be defined as in Exercise 38. Show that (S, r
−1
) is a
partially ordered set, called the dual of (S, r).
a.
b.
c.
Relations, Functions, and Matrices
32. For Exercise 31, name any least elements, minimal elements, greatest elements, and maximal elements.
33. Let (S, d) be a partially ordered set, and let A # S. Prove that the restriction of d to A is a partial
ordering on A.
34. a. Draw the Hasse diagram for the partial ordering “x divides y” on the set 52, 3, 5, 7, 21, 42, 105, 2106.
Name any least elements, minimal elements, greatest elements, and maximal elements. Name a totally
ordered subset with four elements.
b. Draw the Hasse diagram for the partial ordering “x divides y” on the set 53, 6, 9, 18, 54, 72, 108, 1626.
Name any least elements, minimal elements, greatest elements, and maximal elements. Name any
unrelated elements.
35. Draw the Hasse diagram for each of the two partially ordered sets.
a. S = 51, 2, 3, 5, 6, 10, 15, 306
b. S = `(51, 2, 36)
x r y 4 x divides y
A r B 4 A # B
What do you notice about the structure of these two diagrams?
36. For each Hasse diagram of a partial ordering in the accompanying figure, list the ordered pairs that belong
to the relation.
d
a
e
b
f
c
5
1
4
3
2
2
1
3
4
5
37. Let (S, r) and (T, s) be two partially ordered sets. A relation m on S × T is defined by
(s 1 , t 1 ) m (s 2 , t 2 ) 4 s 1 r s 2 and t 1 s t 2 . Show that m is a partial ordering on S × T .
38. Let r be a binary relation on a set S. Then a binary relation called the inverse of r, denoted by r
−1
, is
defined by x r
−1
y 4 y r x.
a. For r = 5(1, 2), (2, 3), (5, 3), (4, 5)6 on the set N, what is r
−1
?
b. Prove that if r is a reflexive relation on a set S, then r
−1
is reflexive.
c. Prove that if r is a symmetric relation on a set S, then r
−1
is symmetric.
d. Prove that if r is an antisymmetric relation on a set S, then r
−1
is antisymmetric.
e. Prove that if r is a transitive relation on a set S, then r
−1
is transitive.
f. Prove that if r is an irreflexive relation on a set S (see Exercise 26), then r
−1
is irreflexive.
g. Prove that if r is an asymmetric relation on a set S (see Exercise 26), then r
−1
is asymmetric.
39. Prove that if a binary relation r on a set S is reflexive and transitive, then the relation r d r
−1
is an
equivalence relation (see Exercise 38 for the definition of r
−1
).
40. a. Let (S, r) be a partially ordered set. Then r
−1
can be defined as in Exercise 38. Show that (S, r
−1
) is a
partially ordered set, called the dual of (S, r).
a.
b.
c.