Can someone explain this part??

A relation $R$ is defined on the set of integers as $xRy$ iff $(x + y)$ is even. Which of the following statements is true?

- $R$ is not an equivalence relation
- $R$ is an equivalence relation having $1$ equivalence class
- $R$ is an equivalence relation having $2$ equivalence classes
- $R$ is an equivalence relation having $3$ equivalence classes

### 2 Comments

Can someone explain this part??

**If you are just looking for What is Equivalence Class**

(Answer provided by Ayush Upadhaya below in comments of main answer, )

Now, talking about equivalence classes, this can be thought of something like myhill nerode theorem where the states in the minimum DFA of the language represents number of equivalence classes in which the input is partitioned by the DFA.

Here only two equivalence classes would be there

ODD and EVEN.

ODD equivalence class would contain those pairs which would contain odd pairs (X,Y) such that X+Y is even (I think he meant ODD, though he wrote EVEN)

EVEN equivalence class would contain those pairs which contain even pairs (X,Y) such that X+Y is even.

This is just similar to a DFA which accepts all strings with even length which has 2 states and these 2 states represent 2 different equivalence classes.

## 4 Answers

$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$.

### 11 Comments

We have a set on which we define the equivalence relation. Here it is $Z$ which is the set of integer numbers. Now, we divide the elements of $Z$ into different partitions (no common elements) such that each partition is an equivalence class- that is every element of the partition must be related to each other obeying reflexivity, symmetry and transitivity. Here, we got 2 partitions as per the given $R$, and no remaining elements.

For this constraint to be satisfied remember

odd+odd=even

even+even=even

So only pairs of the form

(even,even) and (odd,odd) would be there in the relation.

Now

(1)Reflexivity- Yes this relations is reflexive as Odd+odd=even and even+even=even.

(2)Symmetric- If(X,Y) is present then surely (Y,X) will also be present in the relation because anyhow X+Y=Y+X will still remain even(Additon is commutative).

(3)Transitive-Since, the only pairs in the relation allowed are (odd,odd) and (even,even), by transitivity new pairs so formed will also be of the form (even,even) or (odd,odd) which would still be defined in the relation.

Hence, this relation is Equivalence relation.

Now, talking about equivalence classes, this can be thought of something like myhill nerode theorem where the states in the minimum DFA of the language represents number of equivalence classes in which the input is partitioned by the DFA.

Here only two equivalence classes would be there

ODD and EVEN.

ODD equivalence class would contain those pairs which would contain odd pairs (X,Y) such that X+Y is even.

EVEN equivalence class would contain those pairs which contain even pairs (X,Y) such that X+Y is even.

This is just similar to a DFA which accepts all strings with even length which has 2 states and these 2 states represent 2 different equivalence classes.

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**

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)