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
    Thanks
    1
    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,924
    Thanks
    1762
    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,924
    Thanks
    1762
    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 04: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
    Thanks
    1

    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
    Thanks
    1
    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, 02:09 PM
  2. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: April 29th 2010, 05:30 PM
  3. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: October 1st 2009, 04:03 PM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 16th 2008, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum