Discrete Mathematics for Computer Science

Exercises 189

2. Determine which of the following five relations defined on Z are equivalence relations:

(a) {(a,b) E Z x Z: (a > 0andb >0) or(a <0andb <0)}

(b) {(a,b) E Z Z X : (a> 0andb > 0)or(a <0andb <0)}

(c) {(a,b) E Zx 2: Ia -bI < 101

(d) {(a,b) EZ x Z: (a < 0andb >0) or(a <0 andb <0))

(e) {(a,b) E Z x Z: (a> 0andb >0) or(a <0 andb <0)1

3. Find the elements in the relation "have the same remainder when divided by 8" if the
   relation is defined on {1, 2, 3 .... 24, 25}. Also, find the distinct equivalence classes
   of this equivalence relation.


4. Let POPULATION be the set of all people. Let R be the binary relation on POPU-
   LATION such that (x, y) E R if x is an older brother of y or x = y. Is R reflexive?
   Symmetric? Antisymmetric? Transitive? An equivalence relation?


5. Define a binary relation R on IR as {(x, y) E IR x R : x and y are both positive, both
   negative, or both 0}. Prove that R is an equivalence relation. What are its equivalence
   classes?

6. Define a binary relation R on IR as {(x, y) E R x R : sin(x) = sin(y)}. Prove that R

is an equivalence relation. What are its equivalence classes?

7. Let A = {a, b, c, d}. For each of the following partitions of A, list all the pairs of
   elements that form the corresponding equivalence relations:
   (a) {{a, b, c}, {d}}
   (b) {{a}, {b), {c}, {d}}
   (c) (c) {{a, b, c, d}}


8. Let A = {a, b, c, d}. For each of the following partitions of A, determine the elements
   of the corresponding equivalence relation:
   (a) P 1 = {{a, c}, {b, dJJ
   (b) P 2 = {{a}, {b, c}, {d}}
   (c) P 3 = {{a, b}, {c, d)}
   (d) P 4 = {{a, b, c}, {d}}
   Do any of these partitions refine any of the others?


9. Prove Theorem 1.


10. In the example 52Cards, find a simple description for each of the following:

(a) SameSuit n SameValue

(b) (SameSuit U SameValue)*

11. (a) Draw a Venn diagram showing the equivalence classes over N of =- (mod 5),
    (mod 10), and =- (mod 15). Which of these equivalence relations refine another
    one of these equivalence relations?
    (b) Let k, m e N. We say k is a factor ofm ifm =j k for some j such that j E N
    and 0 < j < m. What is the relationship between whether -(mod k) refines -
    (mod m) and whether k is a factor of m or m is a factor of k? Prove your answer.


12. Let R and S be equivalence relations on a set X.

(a) Show that R n S is an equivalence relation.

(b) Show by example that R U S need not be an equivalence relation.

(c) Show that (R U S)*, the reflexive and transitive closure of R U S, is the smallest

equivalence relation containing both R and S.