Thread: [SOLVED] Help with equivalence relations

1. [SOLVED] Help with equivalence relations

Hello, noob on here. Having trouble proving an equivalence relation...

Given:
Define a relation R on $\displaystyle Z$ (the integers) by $\displaystyle nRm$ if $\displaystyle m - n$ is a multiple of 5.

a. Show that R is an equivalence Relation

b. How many equivalence classes are there for R?

a. I know that in order to prove an equivalence relation, you must show that a relation is reflexive, symmetric and transitive.

Reflexive, nRn
Let x be an element of n
$\displaystyle x-x=0$
0 is a multiple of 5
therefore, nRn
therefore, R is reflexive.

I have no idea how to go about proving Symmetric and Transitive without using actual numerical values.

b. I do not know how to determine the number of equivalence classes exist for R.

Thanks in advance, sorry I don't have more to offer.

Gavin

2. Originally Posted by Nivagator
Define a relation R on $\displaystyle Z$ (the integers) by $\displaystyle nRm$ if $\displaystyle m - n$ is a multiple of 5.
a. Show that R is an equivalence Relation
b. How many equivalence classes are there for R?
I have no idea how to go about proving Symmetric and Transitive without using actual numerical values.
b. I do not know how to determine the number of equivalence classes exist for R.
If $\displaystyle m - n$ is a multiple of 5 then surely $\displaystyle n - m=-(m - n)$ is a multiple of 5.

3. My answer

Originally Posted by Nivagator
Hello, noob on here. Having trouble proving an equivalence relation...

Given:
Define a relation R on $\displaystyle Z$ (the integers) by $\displaystyle nRm$ if $\displaystyle m - n$ is a multiple of 5.

a. Show that R is an equivalence Relation

b. How many equivalence classes are there for R?

a. I know that in order to prove an equivalence relation, you must show that a relation is reflexive, symmetric and transitive.

Reflexive, nRn
Let x be an element of n
$\displaystyle x-x=0$
0 is a multiple of 5
therefore, nRn
therefore, R is reflexive.

I have no idea how to go about proving Symmetric and Transitive without using actual numerical values.

b. I do not know how to determine the number of equivalence classes exist for R.

Thanks in advance, sorry I don't have more to offer.

Gavin
take $\displaystyle nRm$ where $\displaystyle (n,m) belongs to R$
then we know that 5 | $\displaystyle (n-m)$ i.e $\displaystyle (n-m)$ is divisible by 5 .
then it simply implies 5 | $\displaystyle -(m-n)$ then ,
$\displaystyle (m,n) belongs to R$

then take
$\displaystyle pRq , qRr$ where $\displaystyle (p,q),(q,r) belongs to R$
=> 5 | $\displaystyle (p-q)$ and 5 | $\displaystyle (q-r)$
=> 5 | $\displaystyle {(p-q)+(q-r)}$
=> 5 | $\displaystyle (p-r)$
=> $\displaystyle (p,r) belongs to R$

So R is an equivalence relation

simply You can see there are 5 equivalence classes which are
[0] ,[1] ,[2] ,[3] ,[4]