GATE CSE 2000 | Question: 2.5

Question

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

Comments

Detailed Video Solution: https://www.youtube.com/watch?v=vSJee6IieP8&t=5047s

---

For those who are not getting how to find equivalence classes, this is the way to find them:

First of all an equivalence class is of an element from the set which we are considering here it is integer set.

Now equivalence class means that for the given relation how many elements can relate and form the relation with the element whose equivalence class we need to find.

Let's check for our relation:

You can pick any number and find it's equivalence class:

let say i pick:

[-9999999] what elements are related to -9999999?

well we can see that -9999999 + y = even, when any odd number is added to it,

for example: -9999999 + 1 = -9999998, -9999999 + (-99) = -10000098

so we can say that with -9999999 elements like 1, -99 and others are related, and this is all the odd integers.

so we can say for equivalence class [-9999999] we have all the odd numbers.

now you can take any odd number say 1 and can say for equivalence class of [1] we have all odd numbers.

and similarly we can have an equivalence class for evens.

 

therefore there are 2 equivalence classes that are odd and even.

---

For transitivity calculation :

By Using parity concept : Even +/- Even = Even 

x+2y+z = Even ----> x+z = Even - 2y = Even

Answer 1

$R$ is reflexive as $(x+x)$ is even for any integer.

$R$ is symmetric as if $(x + y)$ is even $(y+x)$ is also even.

$R$ is transitive as if $(x + (y +z))$ is even, then $((x+y) + z)$ is also even.

So, $R$ is an equivalence relation.

For set of natural numbers, sum of even numbers always give even, sum of odd numbers always give even and sum of any even and any odd number always give odd. So, $R$ must have two equivalence classes -one for even and one for odd.

$\left\{\dots,-4,-2,0,2,4, \dots \right\}, \left\{\dots, -3,-1,1,3, \dots, \right\}$

Correct Answer: $C$.

Comments

sir can i say that "reflexive relation have  at least N equivalence classes"

if yes then why not N ans ......plz correct me if i am wrong

---

sir in above question it should be how many number of partitions possible bcz equivalence relation is possible for each and every element of equivalence relation.

---

thankyou

Answer 2

For simplicity Let the set S = {1, 2, 3, 4}

Now the equivalence relation R = { (1,1), (1,3), (2,2), (2,4), (3,3), (3,1), (4,4), (4,2)}

so, the relation R is equivalence relation.

Now we've to find equivalence classes.

equivalence class [x] = { y | y belongs to S & (x,y) belongs to R} for all x belongs to S

i.e we find equivalence classes w.r.t every element of the set.

[1] = [3] = {1,3}

[2] = [4] = {2,4}

so there are two equivalence classes or partitions {1,3} & {2,4}

Option C

Comments

no of equiv classes = 4 only. they should have mentioned the word distinct .

---

@sayan chowdhury how you are getting equivalence classes as 4??

---

by mistake

Answer 3

option c is right

Comments

Easy and clear way of explanation

Answer 4

Answer will be (c) x+y = even only when x and y are both even or when x and y are both odd.

reflexive----> odd+odd = even ex : 3 +3 so, (3,3) pair is present similarly (2,2) can also be present. so reflexive

symmetric---> (2,4) and (4,2) or(3,7) and (7,3) are present so symmetric

transitive-----> If (2,4) and (4,8) present then (2,8) should also be present similarly we can do this for odd number pairs...

so it is an equivalence relation..

There are 2 equivalence class i.e., (even,even) and (odd,odd)

Answer 5

The correct option is C 

R is an equivalence relation having 2 equivalence classes

 

A relation R is defined as xRy iff (x+y) is ever over set of integers.
(x+y) is even iff
(i) both x and y are even
(ii) both x and y are odd

Therefore, relation R is equivalence relation because relation is

(i) Reflexive
x+x=2x= even
So (x.x) belongs to R. So relation is reflexive

(ii) Symmetric
If x+y= even then y+x is also even So relation is symmetric.

(iii) Transitive
If x+y= even and y+z= even
Then x+y+y+z= even + even
⇒x+z+2y= even
⇒x+z= even - 2y
⇒x+z= even

∴ Relation R is transitive.

So relation R is an equivalence relation which divides the set of integer into two equivalence classes:

One is of all even and other is of odd integer.