Results 1 to 3 of 3

Math Help - [SOLVED] Help with equivalence relations

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    [SOLVED] Help with equivalence relations

    Hello, noob on here. Having trouble proving an equivalence relation...

    Given:
    Define a relation R on Z (the integers) by nRm if m - n is a multiple of 5.

    a. Show that R is an equivalence Relation

    b. How many equivalence classes are there for R?


    a. I know that in order to prove an equivalence relation, you must show that a relation is reflexive, symmetric and transitive.

    Reflexive, nRn
    Let x be an element of n
    x-x=0
    0 is a multiple of 5
    therefore, nRn
    therefore, R is reflexive.

    I have no idea how to go about proving Symmetric and Transitive without using actual numerical values.

    b. I do not know how to determine the number of equivalence classes exist for R.

    Thanks in advance, sorry I don't have more to offer.

    Gavin
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Nivagator View Post
    Define a relation R on Z (the integers) by nRm if m - n is a multiple of 5.
    a. Show that R is an equivalence Relation
    b. How many equivalence classes are there for R?
    I have no idea how to go about proving Symmetric and Transitive without using actual numerical values.
    b. I do not know how to determine the number of equivalence classes exist for R.
    If m - n is a multiple of 5 then surely n - m=-(m - n) is a multiple of 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    44

    Thumbs up My answer

    Quote Originally Posted by Nivagator View Post
    Hello, noob on here. Having trouble proving an equivalence relation...

    Given:
    Define a relation R on Z (the integers) by nRm if m - n is a multiple of 5.

    a. Show that R is an equivalence Relation

    b. How many equivalence classes are there for R?


    a. I know that in order to prove an equivalence relation, you must show that a relation is reflexive, symmetric and transitive.

    Reflexive, nRn
    Let x be an element of n
    x-x=0
    0 is a multiple of 5
    therefore, nRn
    therefore, R is reflexive.

    I have no idea how to go about proving Symmetric and Transitive without using actual numerical values.

    b. I do not know how to determine the number of equivalence classes exist for R.

    Thanks in advance, sorry I don't have more to offer.

    Gavin
    take nRm where (n,m) belongs to R
    then we know that 5 | (n-m) i.e (n-m) is divisible by 5 .
    then it simply implies 5 | -(m-n) then ,
    (m,n) belongs to R

    then take
    pRq , qRr where (p,q),(q,r) belongs to R
    => 5 | (p-q) and 5 | (q-r)
    => 5 | {(p-q)+(q-r)}
    => 5 | (p-r)
    => (p,r) belongs to R

    So R is an equivalence relation

    simply You can see there are 5 equivalence classes which are
    [0] ,[1] ,[2] ,[3] ,[4]
    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. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  3. Help with equivalence relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 3rd 2009, 07:39 AM
  4. equivalence relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2008, 04:15 AM
  5. [SOLVED] Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 22nd 2008, 09:28 PM

Search Tags


/mathhelpforum @mathhelpforum