Results 1 to 12 of 12

Math Help - Equivalence Relations

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    44

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by kurac View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2009
    Posts
    44
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello kurac
    Quote Originally Posted by kurac View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2009
    Posts
    44
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1480
    Awards
    1
    Quote Originally Posted by kurac View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2009
    Posts
    44
    what do i use that test if its reflexsive, symmetric and transitive?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1480
    Awards
    1
    Quote Originally Posted by kurac View Post
    what do i use that test if its reflexsive, symmetric and transitive?
    m\mathcal{R}n if and only if f(m)=f(n).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Mar 2009
    Posts
    44
    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?
    Last edited by kurac; April 30th 2009 at 03:45 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Mar 2009
    Posts
    44
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello kurac
    Quote Originally Posted by kurac View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  2. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: April 29th 2010, 04:30 PM
  3. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: October 1st 2009, 03:03 PM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 16th 2008, 01:08 PM

Search Tags


/mathhelpforum @mathhelpforum