Discrete Mathematics for Computer Science

Special Types of Relations 167

(a) LeN o LeN

(b) Le.'

(c) LtDRo LtR

(d) Challenge: LtN o LtN

(e) Challenge: LtD o GtN

(f) Let NeN = {(x, y) : x, y e N and x y. What is Ne.

(^1)?

9. Prove Theorem 2(c).


10. (a) Prove for any set X that Idx = IdX^1.
    (b) Find two binary relations R and S on N where R IdMN and S / IdN such that
    R - R-^1 and S = S-1.
    (c) Suppose that R is a binary relation on a set X and, for every binary relation S on
    X, R o S = S. Prove that R = Idx.


11. Let A = {1, 2, 3 ... , 10}. Let R = {(1, 2), (1, 4), (1, 6), (1, 8), (1, 10), (3, 5), (3, 7),
    (4, 6), (6, 8), (7, 10)) be a relation on A. Let S = {(2, 4), (3, 6), (5, 7), (7, 9), (8, 10),
    (8, 9), (8, 8), (9, 9), (3, 8), (4, 9)} be a second relation on A. Find:
    (a) R o S
    (b) S o R


12. Show that composition of relations is an associative operation. That is, show that if
    R, S, and T are binary relations on a set X, then

R o (S o T) = (R o S) o T

13. Let R, S, and T be binary relations on a set X.
    (a) Prove that R C S if and only if R-1 C S-1.
    (b) Prove that ifR C S, thenRoT C SoTandToR C ToS.
    (c) If R o T C S o T and T o R C T o S for some relation T, does it follow that
    R C S?


14. Let X = {0, 1). Let B = 'P(X x X) be the set of all binary relations on X.
    (a) List all the elements of B.
    (b) Since elements of B are themselves relations, it makes sense to ask whether two
    of those relations are inverses of each other. Let

IsInverseOf = {(R, S) : R e B and S r B and R = S-1}

List all elements of IsInverseOf

(c) Since IsInverseOf is a binary relation, it has an inverse. What is IslnverseOf-^1?

(d) What is IsInverseOf o IsInverseOf?

rnSpecial Types of Relations

Some very common binary relations have important special properties. Three of these spe-

cial properties, the reflexive, symmetric, and transitive properties, occur in relations such

as Id, Lt, Le, and both the SubsetOf (C) and StrictSubsetOf (C) relations. Not all of these

relations have all three of these properties, however. The properties that identify and dif-

ferentiate these relations are introduced in this section.