A relation R is defined on the set of integers as xRy iff (x + y) is even. Which of the following statements is true? A. R is not an equivalence relation B. R is an equivalence relation having 1 equivalence class C. R is an equivalence relation having 2 equivalence classes D. R is an equivalence relation having 3 equivalence classes

GATE 2000 · Discrete Mathematics · Relations · medium

Answer: R is an equivalence relation with exactly 2 equivalence classes: the set of all even integers and the set of all odd integers.

1. Verify R is an equivalence relation: Reflexive: x+x = 2x, always even. Symmetric: x+y even implies y+x even (commutativity). Transitive: x+y even and y+z even => x,y same parity and y,z same parity => x,z same parity => x+z even. All three hold.
2. Count equivalence classes: x+y is even iff both x,y are even or both are odd. So [0] = {...,-4,-2,0,2,4,...} (all even integers) and [1] = {...,-3,-1,1,3,...} (all odd integers). These are exactly 2 distinct equivalence classes.