Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Relations Exercises 111 11. On the set consider the relation defined as "xRy if and only if x y is an integer." Prove first that R is an equivalence relation. Then find the equivalence classes of 1, -1.32, and . 12. On the set A = {2, 3, 4, 5, 6,...} consider the relation defined as "xRy if and only if GCD(x, y) > 1." Is this an equivalence relation (explain how you reach your conclusion)? If it is, find [2], [3], and [8] otherwise find some elements that are in relation with 2, some in relation with 3, and some in rela- tion with 8. 13. On the set A = {2, 3, 4, 5, 6,...} consider the relation defined as "xSy if and only if x and y have the same prime factors." Is this an equivalence relation (explain how you reach your conclusion)? If it is, find [2] and [6]; otherwise, find some elements that are in relation with 2 and some in relation with 6. 14. On define the following relation: "aRb if and only if a b is a multiple of 5." Prove first that R is an equivalence relation. Then find the equivalence classes of 0, 1, 2, 3, 4, 5, -1, -2. 15. Consider the set P of all possible subsets of the set A = {1, 2, 3, 4} (there are 16 subsets). On P con- sider the relation "XRY if and only if X and Y have the same number of elements." Prove that R is an equivalence relation. Then find all the distinct equivalence classes. 16. Find the mistake in the "proof" of the following statement. Let A be a nonempty set and R be a rela- tion on A. If R is symmetric and transitive, then R is reflexive. (If this statement held true, every symmetric and transitive relation would automatically be an equivalence relation.) "Proof:" Let x A. The relation is symmetric. Therefore, xRy implies yRx. By the transitive property, xRy and yRx implies xRx. The fact that every x A is in relation with itself proves that the relation R