The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.4k 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
asked in Set Theory & Algebra by Veteran (59.4k points)
edited by | 1.4k views
+3

This one ...

+3

This one also ...

1 Answer

+26 votes
Best answer
$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.
answered by Loyal (5.8k points)
selected by
+1
please explain
0
how is transitivity related to associativity??
+1

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..
+1
What is equivalace class and how can we divide something into equilalence classes ?
+11

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.

More info

0
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 pairs (X,Y) such that X+Y is odd.

EVEN equivalence class would contain those pairs which contain pairs (X,Y) such that X+Y is even. And this equivalence class would represent out relation.

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.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,770 questions
41,730 answers
118,876 comments
41,381 users