Exercises 1-10, determine whether the given relation is an uivalence relation on (1, 2, 3, 4, 5). If the relation is an equiv- ence relation, list the equivalence classes. (In Exercises 5-10, y = [1,2,3,4,5).) . {(1, 1), (2, 2), (3, 3), (4,4), (5,5), (1, 3), (3, 1)) 2. {(1, 1), (2, 2), (3, 3), (4,4), (5,5), (1, 3), (3, 1), (3, 4), (4,3)} 5. ((1, 1), (2, 2), (3, 3), (4,4)) 1. {(1, 1), (2, 2), (3, 3), (4,4), (5, 5), (1, 5), (5, 1), (3, 5). (5.3). (1,3), (3, 1)) . ((x, y) | 1 ≤x≤ 5 and 1 ≤ y ≤5) . ((x, y) | 4 divides.x - y) . {(x, y) | 3 divides x+y} . {(x, y) |x and y are both even} . {(x, y) Ix and y are both even or x and y are both odd} Exercises 11-16, determine whether the given relation is an uivalence relation on the set of all people. 8. [(x, y) |x divides 2 - y) .((x, y) |x and y are the same height) 2. {(x, y) |x and y have, at some time, lived in the same country) . {(x, y) |x and y have the same first name) . ((x, y) |x is taller than y) . ((x, y) [x and y have the same parents) . ((x, y) [x and y have the same color hair) Exercises 17-22, list the members of the equivalence relation (1, 2, 3, 4) defined (as in Theorem 3.4.1) by the given partition. so, find the equivalence classes [1], [2], [3], and [4]. . ((1.2), (3, 4)) . (1), (2), (3), (4)) . {{1,2,3,4}} 18. (1), (2), (3,4)) 20. {{1,2,3), (4}} 22. ((1), (2,4), (3}} Exercises 23-25, let X=(1, 2, 3, 4, 5), Y=(3, 4), and C= .3). Define the relation R on P(X), the set of all subsets of X, ARB if AUY=BUY. . Show that R is an equivalence relation. 1. List the elements of [C], the equivalence class containing C. 25. How many distinct equivalence classes are there? 26. Let X = (San Francisco, Pittsburgh, Chicago, San Die Philadelphia, Los Angeles). Define a relation R on X as x Ry if x and y are in the sam (a) Show that R is an equivalence relation. (b) List the equivalence classes of X. 27. If an equivalence relation has only one equivalence clas must the relation look like? 28. If R is an equivalence relation on a finite set X and X what must the relation look like? 29. By listing ordered pairs, give an example of an equi relation on (1, 2, 3, 4, 5, 6) having exactly four equi classes. 30. How many equivalence relations are there on the set (1 31. Let R be a reflexive relation on X satisfying: for all x, y if x Ry and y Rz, then z R.x. Prove that R is an equivale lation. 32. Define a relation R on RR, the set of functions from by fRg if f(0) = g(0). Prove that R is an equivalence on RR. Let f(x) = x for all x € R. Describe [J]. 33. Define a relation R on RR, the set of functions from R fRg if there exist a, b R such that f(x) = g(x + for all x R. Prove that R is an equivalence rela RR. What property do all functions in an equivalend share? 34. Let X = (1,2,..., 10). Define a relation R on X (a, b) R (c,d) if a +d=b+c. (a) Show that R is an equivalence relation on X X X. (b) List one member of each equivalence class of Xx 35. Let X = (1.,2..... 10). Define a relation R on X (a, b) R (c,d) if ad=bc. (a) Show that R is an equivalence relation on X x X. (b) List one member of each equivalence class of Xx (c) Describe the relation R in familiar terms. 36. Let R be a reflexive and transitive relation on X. She ROR-ic on aquivalence ralation on Y