CHAP. 2] RELATIONS 41
(d) IfRandSare reflexive thenR∪Sis reflexive.
(e) IfRandSare transitive thenR∪Sis transitive.
(f) IfRandSare antisymmetric thenR∪Sis antisymmetric.
(g) IfRis antisymmetric, thenR−^1 is antisymmetric.
(h) IfRis reflexive thenR∩R−^1 is not empty.
(i) IfRis symmetric thenR∩R−^1 is not empty.2.29. SupposeRandSare relations on a setA, andRis antisymmetric. Prove thatR∩Sis antisymmetric.EQUIVALENCE RELATIONS
2.30. Prove that ifRis an equivalence relation on a setA, thanR−^1 is also an equivalence relation onA.
2.31. LetS={ 1 , 2 , 3 ,..., 18 , 19 }. LetRbe the relation onSdefined by “xyis a square,” (a) ProveRis an equivalence
relation. (b) Find the equivalence class [1]. (c) List all equivalence classes with more than one element.
2.32. LetS={ 1 , 2 , 3 ,..., 14 , 15 }. LetRbe the equivalence relation onSdefined byx≡y(mod 5), that is,x−yis
divisible by 5. Find the partition ofSinduced byR, i.e. the quotient setS/R.
2.33. LetS={ 1 , 2 , 3 ,..., 9 }, and let∼be the relation onA×Adefined by(a, b)∼(c, d) whenever a+d=b+c.(a) Prove that∼is an equivalence relation.
(b) Find[( 2 , 5 )], that is, the equivalence class of( 2 , 5 ).Answers to Supplementary Problems
2.20. {(a,b,a), (a,b,d), (a,c,a), (a,c,d),
(a,d,a), (a,d,d), (b,b,a), (b,b,d),
(b,c,a),(b,c,d), (b,d,a), (b,d,d),
(c,b,a), (c,b,d), (c,c,a), (c,c,d),
(c,d,a), (c,d,d)}
2.21. (a)x=3,y=−2; (b)x=2,y=3.
2.23. (a) MR=[ 0 , 0 , 1 , 1 ; 0 , 0 , 0 , 0 ;
0 , 1 , 1 , 1 ; 0 , 0 , 0 , 0 ];
(b) Domain={ 1 , 3 }, range={ 2 , 3 , 4 };
(c) R−^1 ={( 3 , 1 ), ( 4 , 1 ), ( 2 , 3 ), ( 3 , 3 ),
( 4 , 3 )};(d) See Fig. 2-8(a);
(e) RoR={( 1 , 2 ), ( 1 , 3 ), ( 1 , 4 ), ( 3 , 2 ),
( 3 , 3 ), ( 3 , 4 )}.
2.24. (a) See Fig. 2-8(b);
(b)R=[ 0 , 1 , 0 ; 0 , 0 , 0 ; 1 , 1 , 0 ; 0 , 0 , 1 ],
S=[ 0 , 1 , 1 ; 0 , 0 , 0 ; 1 , 0 , 0 ],
R◦S=[ 0 , 0 , 0 ; 0 , 0 , 0 ; 0 , 1 , 1 ; 1 , 0 , 0 ];
(c){(b, 1 ), (a, 3 ), (b, 3 ), (c, 4 )},{( 3 ,y),
( 3 , z), ( 4 ,x)}.
2.25. (a)R◦S={(a, c), (a, d), (c, a), (d, a)}
(b)S◦R={(b, a), (b, c), (c, b), (c, d),
(d, a), (d, c)}
(c)R◦R={(a, a), (a, b), (a, c), (a, d), (c, b)}
(d)S◦S={(c, c), (c, a), (c, d)}Fig. 2-8