Results 1 to 3 of 3

Thread: [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 $\displaystyle Z$ (the integers) by $\displaystyle nRm$ if $\displaystyle 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
    $\displaystyle 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
    21,782
    Thanks
    2824
    Awards
    1
    Quote Originally Posted by Nivagator View Post
    Define a relation R on $\displaystyle Z$ (the integers) by $\displaystyle nRm$ if $\displaystyle 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 $\displaystyle m - n$ is a multiple of 5 then surely $\displaystyle 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 $\displaystyle Z$ (the integers) by $\displaystyle nRm$ if $\displaystyle 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
    $\displaystyle 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 $\displaystyle nRm$ where $\displaystyle (n,m) belongs to R$
    then we know that 5 | $\displaystyle (n-m)$ i.e $\displaystyle (n-m)$ is divisible by 5 .
    then it simply implies 5 | $\displaystyle -(m-n)$ then ,
    $\displaystyle (m,n) belongs to R$

    then take
    $\displaystyle pRq , qRr$ where $\displaystyle (p,q),(q,r) belongs to R$
    => 5 | $\displaystyle (p-q)$ and 5 | $\displaystyle (q-r)$
    => 5 | $\displaystyle {(p-q)+(q-r)}$
    => 5 | $\displaystyle (p-r)$
    => $\displaystyle (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: Sep 19th 2011, 01:09 PM
  2. Replies: 10
    Last Post: Jan 14th 2010, 12:28 PM
  3. Help with equivalence relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 3rd 2009, 06:39 AM
  4. equivalence relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 3rd 2008, 03:15 AM
  5. [SOLVED] Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Oct 22nd 2008, 08:28 PM

Search Tags


/mathhelpforum @mathhelpforum