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 $\displaystyle f$ is defined upon $\displaystyle \mathbb{N}$, the set of integers. So $\displaystyle n$ and $\displaystyle m$ are simply integers!

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.
$\displaystyle f(11)=1$ because we have a remainder of 1 when 11 is divided by 5.
$\displaystyle 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?
$\displaystyle m\mathcal{R}n$ if and only if $\displaystyle 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.

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

So, as Plato has said, you must prove:

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

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
Not quite, because you can add any multiple of $\displaystyle 5$ to $\displaystyle x$ and get an equivalent integer. So you could express it as $\displaystyle [x] = \{x+5n| n\in \mathbb{Z}\}$