9,237 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

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

If you are just looking for What is Equivalence Class

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.

### Subscribe to GO Classes for GATE CSE 2022

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

how is transitivity related to associativity??

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)

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

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

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.

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

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}

 =  = {2,4}

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

Option C

by

option c is right ### 1 comment

Easy and clear way of explanation
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)
{"ft_lang_label":"__label__en","ft_lang_prob":0.9202307,"math_prob":0.99901,"size":569,"snap":"2021-31-2021-39","text_gpt3_token_len":186,"char_repetition_ratio":0.14336284,"word_repetition_ratio":0.0,"special_character_ratio":0.35676625,"punctuation_ratio":0.18705036,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998715,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-27T01:03:25Z\",\"WARC-Record-ID\":\"<urn:uuid:88e70aaa-dab2-4738-9464-c62b24fc6b3f>\",\"Content-Length\":\"153311\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a03e2f1b-ca06-4c82-84bb-6ea2d9ca8bbe>\",\"WARC-Concurrent-To\":\"<urn:uuid:ece4ee4a-aaff-4dfa-8675-524f441bc1f0>\",\"WARC-IP-Address\":\"172.67.206.99\",\"WARC-Target-URI\":\"https://gateoverflow.in/652/gate-cse-2000-question-2-5\",\"WARC-Payload-Digest\":\"sha1:3YI7WEMFNHR74SLSUF34WRK63H2BHAQM\",\"WARC-Block-Digest\":\"sha1:K3XWW45UUOQ6CMXJTL2ZGG5EBJXT5SUJ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780058222.43_warc_CC-MAIN-20210926235727-20210927025727-00461.warc.gz\"}"}