Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

38 RELATIONS [CHAP. 2

(b) LetT=∩(S|Sis aP-relation andR⊆S). SincePisR-closable,Tis nonempty by (1) andTis aP-relation

by (2). Since each relationScontainsR, the intersectionTcontainsR. Thus,Tis aP-relation containingR.By

definition,P(R) is the smallestP-relation containingR; henceP(R)⊆T. On the other hand,P(R)is one of the

setsSdefiningT, that is,P(R)is aP-relation and ifR⊆P(R). Therefore,T⊆P(R). Accordingly,P(R)=T.

2.13. Consider the relationR={(a, a), (a, b), (b, c), (c, c)}on the setA={a, b, c}. Find: (a) reflexive(R);
(b) symmetric(R); (c) transitive(R).
(a) The reflexive closure onRis obtained by adding all diagonal pairs ofA×AtoRwhich are not currently inR.
Hence,
reflexive(R)=R∪{(b, b)}={(a, a), (a, b), (b, b), (b, c), (c, c)}
(b) The symmetric closure onRis obtained by adding all the pairs inR−^1 toRwhich are not currently inR. Hence,

symmetric(R)=R∪{(b, a), (c, b)}={(a, a), (a, b), (b, a), (b, c), (c, b), (c, c)}

(c) The transitive closure onR, sinceAhas three elements, is obtained by taking the union ofRwithR^2 =R◦Rand

R^3 =R◦R◦R. Note that

R^2 =R◦R={(a, a), (a, b), (a, c), (b, c), (c, c)}

R^3 =R◦R◦R={(a, a), (a, b), (a, c), (b, c), (c, c)}

Hence

transitive(R)=R∪R^2 ∪R^3 ={(a, a), (a, b), (a, c), (b, c), (c, c)}

EQUIVALENCE RELATIONS AND PARTITIONS

2.14. Consider theZof integers and an integerm> 1. We say thatxis congruent toymodulom, written

x≡y(modm)

ifx−yis divisible bym. Show that this defines an equivalence relation onZ.

We must show that the relation is reflexive, symmetric, and transitive.

(i) For anyxinZwe havex≡x(modm)becausex−x=0 is divisible bym. Hence the relation is reflexive.

(ii) Supposex≡y(modm),sox−yis divisible bym.Then−(x−y)=y−xis also divisible bym,soy≡x(modm).

Thus the relation is symmetric.

(iii) Now supposex≡y(modm)andy≡z(modm),sox−yandy−zare each divisible bym. Then the sum

(x−y)+(y−z)=x−z

is also divisible bym; hencex≡z(modm). Thus the relation is transitive.

Accordingly, the relation of congruence modulomonZis an equivalence relation.

2.15. LetAbe a set of nonzero integers and let≈be the relation onA×Adefined by

(a, b)≈(c, d) whenever ad=bc

Prove that≈is an equivalence relation.

We must show that≈is reflexive, symmetric, and transitive.

(i) Reflexivity: We have(a, b)≈(a, b)sinceab=ba. Hence≈is reflexive.

(ii) Symmetry: Suppose(a, b)≈(c, d). Thenad=bc. Accordingly,cb=daand hence(c, d)=(a, b). Thus,≈is

symmetric.

(iii) Transitivity: Suppose(a, b)≈(c, d)and(c, d)≈(e, f ). Thenad=bcandcf=de. Multiplying corresponding

terms of the equations gives(ad)(cf )=(bc)(de). Cancelingc=0 andd=0 from both sides of the equation

yieldsaf=be, and hence(a, b)≈(e, f ). Thus≈is transitive. Accordingly,≈is an equivalence relation.