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.
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.
means that and leave the same remainder when they are divided by .
So, as Plato has said, you must prove:
- Reflexivity: in other words, leaves the same remainder as . Which is obviously true
- Symmetry: in other words, , if leaves the same remainder as , then leaves the same remainder as . Which is also obviously true.
- Transitivity: in other words, , if leaves the same remainder as , and leaves the same remainder as , then leaves the same remainder as . Obviously true.
Grandad
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.
Hello kuracCorrect!
Not quite, because you can add any multiple of to and get an equivalent integer. So you could express it asSo 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.
Grandad