2.6k views

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

1. $R$ is not an equivalence relation
2. $R$ is an equivalence relation having 1 equivalence class
3. $R$ is an equivalence relation having 2 equivalence classes
4. $R$ is an equivalence relation having 3 equivalence classes
edited | 2.6k views
0
My question is how do we find the number of equivalence class it is having after finding out it is an equivalence relation?

Can someone explain this part??

$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\}$

C choice.
selected by
+1
+1
how is transitivity related to associativity??
+3

transitive: if x+y = 2k =even and y+z =2m =even

adding both: x + z = 2(k+m-y) = even

so transitive

and 1. sum of any two odd will be even & 2. any two even will be even too => two different non intersecting (disjoint) equivalence sets defined on integers . so, 2 classes option (c)

+1

"sum of odd numbers always give odd " how ? 3 + 5 = 8

0
that should be a typo- corrected now..
+2
What is equivalace class and how can we divide something into equilalence classes ?
+17

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.

+1
XRY iff X+Y is even

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.
0
plz edit your answer in last two line you write x+y is even in both of them odd equivalence class would contain those pair such that x+y is odd.
0
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
+1 vote

option c is right 0
Easy and clear way of explanation