Results 1 to 8 of 8

Math Help - equivalence relation

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    equivalence relation

    Hey guys, question... Let A = {1,2,3,4,5,6,7,8,9,10}. Define a relation R on A by writing (x,y) \epsilon R iff 3|(x-y).

    a) show that R is an equivalence relation on A.

    My answer:
    Is it reflexive? Yes! since x-x = 0 and 0 is divisible by 3. (Eg x = 6)
    Is it symmetric? Yes! since if x-y is divisible by 3, then y-x is divisible by 3. (Eg, x=8, y=2)
    Is it transitive? Yes! since if 3|(x-y) and 3|(y-z), then 3|(x-z). (Eg. x=10, y=1 and z=4).

    Is this correct? thanks..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Any help anyone? thank you
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    You're correct. But leave out the examples. They're irrelevant to the proof, in the sense that just because something holds for example x,y,z in A doesn't entail that it holds for all x,y,z in A.

    Here's how I would write it:

    x-x = 0, and 3*0 = 0, so 3|x-x. So we have reflexivity.

    Suppose 3|x-y. So let 3*z = x-y. So 3*-z = y-x. So 3|y-x. So we have symmetry.

    Suppose 3|x-y and 3|y-z. So let 3*v = x-y and 3*w = y-z.
    But x-z = (x-y)+(y-z) = (3*v)+(3*w) = 3(v+w). So 3|x-z. So we have transitivity.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by jvignacio View Post
    Hey guys, question... Let A = {1,2,3,4,5,6,7,8,9,10}. Define a relation R on A by writing (x,y) \epsilon R iff 3|(x-y).

    a) show that R is an equivalence relation on A.

    My answer:
    Is it reflexive? Yes! since x-x = 0 and 0 is divisible by 3. (Eg x = 6)
    Is it symmetric? Yes! since if x-y is divisible by 3, then y-x is divisible by 3. (Eg, x=8, y=2)
    Is it transitive? Yes! since if 3|(x-y) and 3|(y-z), then 3|(x-z). (Eg. x=10, y=1 and z=4).

    Is this correct? thanks..
    Incidentally, this equivalence relation is just congruence (mod 3).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by undefined View Post
    Incidentally, this equivalence relation is just congruence (mod 3).
    Good point. We could prove this for any n for congruence(mod n).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Thanks for the replys! What about finding the equivalent classes on R???? Thank you!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by jvignacio View Post
    Thanks for the replys! What about finding the equivalent classes on R???? Thank you!
    I don't know what you mean.

    It is possible to partition A into subsets by equivalence class, as follows

    {1,4,7,10}
    {2,5,8}
    {3,6,9}

    The same can be done for the set of integers.

    Or you can talk about the set of all equivalence classes, which is often expressed in terms of common residues, like this

    \{\bar0,\bar1,\bar2\}

    or this

    {0,1,2}

    Is that what you had in mind?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    thank you, i ment the first solution..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  2. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  3. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  4. equivalence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 12th 2009, 05:33 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum