# Thread: Equivalence Relations

1. ## Equivalence Relations

Hi, I need help on this question.

f: N => N

f(n) = r if r is the remainder when number n is divided by 5.

R={(n,m) | f(n) = f(m)}

So f(5) = 0 etc

I need help proving this is an equivalence relation.
So can someone help me check if its reflexsive, symmetric and transitive?

Cheers.

2. Originally Posted by kurac
Hi, I need help on this question.

f: N => N

f(n) = r if r is the remainder when number n is divided by 5.

R={(n,m) | f(n) = f(m)}

So f(5) = 0 etc

I need help proving this is an equivalence relation.
So can someone help me check if its reflexsive, symmetric and transitive?

Cheers.
you need only answer three questions:

does f(n) = f(n) for all n?

does f(n) = f(m) imply f(m) = f(n), for all m and n?

does f(n) = f(m) and f(m) = f(p) imply f(n) = f(p), for all n,m and p?

3. I dont know how to do it. I know how to determine if its a equivalence relation when we are given say a Set A which contains all positive integers for example. But this is a function. What are my n and m?

4. Hello kurac
Originally Posted by kurac
I dont know how to do it. I know how to determine if its a equivalence relation when we are given say a Set A which contains all positive integers for example. But this is a function. What are my n and m?
You are told
f: N => N
so $f$ is defined upon $\mathbb{N}$, the set of integers. So $n$ and $m$ are simply integers!

Grandad

5. i know how to check the 3 statements for equivalence relation. But i dont understand this function. Can someone please give me example of how to solve these problems which involve functions?

6. Originally Posted by kurac
But i dont understand this function. Can someone please give me example of how to solve these problems which involve functions?
It is simply the 'mod 5' function.
$f(11)=1$ because we have a remainder of 1 when 11 is divided by 5.
$f(17)=2,~f(29)=4,~f(35)=0$

7. what do i use that test if its reflexsive, symmetric and transitive?

8. Originally Posted by kurac
what do i use that test if its reflexsive, symmetric and transitive?
$m\mathcal{R}n$ if and only if $f(m)=f(n)$.

9. Thanks, And so are my n and m the remainders? r will never be more than 4 though?

What is my set of numbers i get n and m from to do that check?

10. ## Modulo arithmetic

Hello Kurac -

This is really a very trivial question, because any relation involving the phrase 'the same as' or 'equals' is almost always obviously an equivalence.

$f(m) = f(n)$ means that $m$ and $n$ leave the same remainder when they are divided by $5$.

So, as Plato has said, you must prove:

• Reflexivity: in other words, $\forall n,\, n$ leaves the same remainder as $n$. Which is obviously true
• Symmetry: in other words, $\forall n, m$, if $n$ leaves the same remainder as $m$, then $m$ leaves the same remainder as $n$. Which is also obviously true.
• Transitivity: in other words, $\forall m,n,p$, if $m$ leaves the same remainder as $n$, and $n$ leaves the same remainder as $p$, then $m$ leaves the same remainder as $p$. Obviously true.

Grandad

11. Thanks Grandad! That was really helpfull.
So your saying if:
n = 5 and m = 10
The r is 0 for both of them hence f(n) = f(m). Is that correct?
Same as if n = 16 and m = 21, then r is 1 for both, hence f(n) = f(m).

So the equivalence classes of that equivalence relation would be
in general [x] = {x, x+5}. Is that correct, if not please correct me?

Thanks for the great help.

12. Hello kurac
Originally Posted by kurac
Thanks Grandad! That was really helpfull.
So your saying if:
n = 5 and m = 10
The r is 0 for both of them hence f(n) = f(m). Is that correct?
Same as if n = 16 and m = 21, then r is 1 for both, hence f(n) = f(m).
Correct!
So the equivalence classes of that equivalence relation would be
in general [x] = {x, x+5}. Is that correct, if not please correct me?

Thanks for the great help.
Not quite, because you can add any multiple of $5$ to $x$ and get an equivalent integer. So you could express it as $[x] = \{x+5n| n\in \mathbb{Z}\}$

Grandad