Answer to Question #127926 in Discrete Mathematics for jaya

Question

4. (a) Let R be the relation on Z × Z such that ((a,b), (c,d)) ∈ R ↔ a + d = b + c. Show that R is an equivalence relation.

(b) If R is an equivalence relation on a finite non empty set A, then the equivalence classes of R all have the same number of elements?

(c) Prove that intersection of two equivalence relations on a non empty set A is an equivalence relation.

Answer 1

a)R is reflexive: Suppose (a, b) is an ordered pair in Z × Z. [We must show that (a, b) R (a, b).] We have a + b = a + b. Thus, by definition of R, (a, b) R (a, b). R is symmetric: Suppose (a, b) and (c, d) are two ordered pairs in Z × Z and (a, b) R (c, d). [We must show that (c, d) R (a, b).] Since (a, b) R (c, d), a + d = b + c. But this implies that b + c = a + d, and so, by definition of R, (c, d) R (a, b). R is transitive: Suppose (a, b),(c, d), and (e, f) are elements of Z × Z, (a, b) R (c, d), and (c, d) R (e, f). [We must show that (a, b) R (e, f).] Since (a, b) R (c, d), a + d = b + c, which means a − b = c − d, and since (c, d) R (e, f)C, c + f = d + e, which means c − d = e − f. Thus a − b = e − f, which means a + f = b + e, and so, by definition of R, (a, b) R (e, f)

b) This is false. For example, if A = {1, 2, 3} and R = {(1, 1),(1, 2),(2, 1),(2, 2),(3, 3)} then [1] = {1, 2} has more elements than [3] = {3}.

c) This is true. Note that if R1 and R2 are equivalence relations on a set A, and if we let R = R1 ∩ R2, then we have that xRy iff xR1y and xR2y. We now need to check the three properties: reflexivity,symmetry,transitivity