InterviewSolution
| 1. |
Let R = {(a, b) : a, b ∈ Z and (a - b) is divisible by 5}. Show that R is an equivalence relation on Z. |
|
Answer» In order to show R is an equivalence relation, we need to show R is Reflexive, Symmetric and Transitive. Given that, ∀ a, b ∈Z, aRb if and only if a – b is divisible by 5. Now, R is Reflexive if (a,a) ∈ R ∀ a ∈ Z aRa ⇒ (a-a) is divisible by 5. a-a = 0 = 0 × 5 [since 0 is multiple of 5 it is divisible by 5] ⇒ a-a is divisible by 5 ⇒ (a,a) ∈ R Thus, R is reflexive on Z. R is Symmetric if (a,b) ∈ R ⇒ (b,a) ∈ R ∀ a,b ∈ Z (a,b) ∈ R ⇒ (a-b) is divisible by 5 ⇒ (a-b) = 5z for some z ∈ Z ⇒ -(b-a) = 5z ⇒ b-a = 5(-z) [∵ z ∈ Z ⇒ -z ∈ Z ] ⇒ (b-a) is divisible by 5 ⇒ (b,a) ∈ R Thus, R is symmetric on Z. R is Transitive if (a,b) ∈ R and (b,c) ∈ R ⇒ (a,c) ∈ R ∀ a,b,c ∈ Z (a,b) ∈ R ⇒ (a-b) is divisible by 5 ⇒ a-b = 5z1 for some z1∈ Z (b,c) ∈ R ⇒ (b-c) is divisible by 5 ⇒ b-c = 5z2 for some z2∈ Z Now, a-b = 5z1 and b-c = 5z2 ⇒ (a-b) + (b-c) = 5z1 + 5z2 ⇒ a-c = 5(z1 + z2 ) = 5z3 where z1 + z2 = z3 ⇒ a-c = 5z3 [∵ z1,z2 ∈ Z ⇒ z3∈ Z] ⇒ (a-c) is divisible by 5. ⇒ (a, c) ∈ R Thus, R is transitive on Z. Since R is reflexive, symmetric and transitive it is an equivalence relation on Z. |
|