Results 1 to 7 of 7

Math Help - Equivalence Classes

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    191

    Equivalence Classes

    Let S={-8,-4,-2,0,1,2,5,7} be a subset of Z(integers), and let ~ be a relation defined on S by x~y if 7 | (6x+7).

    Find all distinct equivalence classes.


    Attempt:
    Here's my problem: when I want to find one of the equivalence classes, for instance [0], I'm not sure how do it.
    In 7 | (6x+7) do I need to set x=0 or y=0???

    I checked the solution and the correct answer for this particular problem is setting x to zero:

    [0]={ x \in S : 7|6.0+y = y}

    I'm confused because in many other problems which are very similar we set y=0. I don't see how we can determine this...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by Roam View Post
    Let S={-8,-4,-2,0,1,2,5,7} be a subset of Z(integers), and let ~ be a relation defined on S by x~y if 7 | (6x+7).
    Are you sure that it isn't meant to read:

    x ~ y iff 7 | (6x+ y ) ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    191
    Quote Originally Posted by pomp View Post
    Are you sure that it isn't meant to read:

    x ~ y iff 7 | (6x+ y ) ?
    Well, there's another problem given to us which is very similar to the one I posted above:

    Let S={-5,-3,-2,0,1,6,7,9,13} be a subset of Z, and let ~ be a relation defined on S by x~y if 6|(x+5y).

    Find the equivalence class [1] = T_1 containing 1.

    And this is how it has been solved:

    [1]={ x \in S : 6|x+5.1 = x+5}={-5,1,7,13}

    Why did they set y=0 here but set x=0 in the problem above?
    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 Roam

    The first thing you need to verify is that these are equivalence relations. If they are, then since an equivalence relation is symmetric (i.e. x \sim y \iff y \sim x) it doesn't matter whether you give a particular value to x or to y: the result will be the same, since they are interchangeable.

    So, looking at the first relation: x\sim y \iff 7|(6x+y) (for that is surely what the question means), ask three questions: is it reflexive? is it symmetric? is it transitive?

    Do you understand modular arithmetic notation?

    Well, if you do, 7|(6x+y) can be written 6x + y \equiv 0 \mod 7

    \Rightarrow 7x+y \equiv x \mod 7

    \Rightarrow y \equiv x \mod 7

    In other words, x and y (which represent any two elements of an equivalence class) leave the same remainder when divided by 7.

    So, yes, it is an equivalence relation. And all you need to do to find the equivalence classes is to look for elements of the original set that leave the same remainder when divided by 7.

    Here's a start: [-8]=\{-8\}, [-4]=\{-4\}, [-2]=\{-2, 5\}, ...

    Grandad
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    Posts
    191
    Hi Grandad

    Could you PLEASE show me in more detail what's happening here because I'm still SO confused on how to find equivalence classes.

    Quote Originally Posted by Grandad View Post
    Hello Roam

    The first thing you need to verify is that these are equivalence relations. If they are, then since an equivalence relation is symmetric (i.e. x \sim y \iff y \sim x) it doesn't matter whether you give a particular value to x or to y: the result will be the same, since they are interchangeable.
    This is the solution they gave us for this problem:



    They've done it by setting x=0. Yes I checked and proved that it's an equivalence relation (reflexive, symmetric and transitive). But it's impossible to obtain the same results by setting y=0:

    [0]={ x \in S: 7| 6x+0 = 6x}

    Now the only time when 6x is divisible by 7 is when x=7

    \Rightarrow {7}  \neq {1,7}

    Since 7 \notdivides 6.1

    See, it does matters if I assign a particular value to x or to y!


    Do you understand modular arithmetic notation?

    Well, if you do, 7|(6x+y) can be written 6x + y \equiv 0 \mod 7

    \Rightarrow 7x+y \equiv x \mod 7

    \Rightarrow y \equiv x \mod 7


    Yes I had learned a little bit about the modular arithmetic notation. This relation is a congruence modulo 7, like you mentioned.
    Last edited by Roam; September 2nd 2009 at 10:53 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello Roam
    Quote Originally Posted by Roam View Post
    Hi Grandad

    Could you PLEASE show me in more detail what's happening here because I'm still SO confused on how to find equivalence classes.



    This is the solution they gave us for this problem:


    This solution is not correct, in at least two different ways. First, does not make sense to write:

    [0]=\{x\in S:7|6\cdot0+y=y\}=\{0,7\}

    This is incorrect use of set notation. It should read:

    [0]=\{y\in S:7|6\cdot0+y=y\}=\{0,7\}

    In general, you can define a set A like this:

    A =\{x:x\text{ satisfies a certain condition}\}

    So it doesn't make sense to write A =\{x:y\text{ satisfies a certain condition}\}

    Secondly, the solution [1]=\{-8, 1\} simply isn't correct: 6\times (-8) + 1 = -47 which is not divisible by 7.

    Now, as to your next point:
    They've done it by setting x=0. Yes I checked and proved that it's an equivalence relation (reflexive, symmetric and transitive). But it's impossible to obtain the same results by setting y=0:

    [0]={ x \in S: 7| 6x+0 = 6x}

    Now the only time when 6x is divisible by 7 is when x=7
    Not true, I'm afraid. x=0 also works, because 6\times0=0, which is divisible by 7. So [7] = \{0, 7\} is correct.

    Your statement
    \Rightarrow {7}  \neq {1,7}
    is true, but that's not the same thing.

    As to your main problem: Do I give a particular value to x or to y? I repeat my previous answer: because it's an equivalence relation it doesn't matter! For instance, if we want to find the equivalence class containing the element 5, we can assign this value to x, and say:

    [5]=\{y\in S:7|30+y\}=\{-2,5\}

    or we can assign the value 5 to y, and say:

    [5]=\{x\in S:7|6x+5\}=\{-2,5\}

    Do you see? The statements 7|30+y and 7|6x+5 are equivalent, simply because they're both satisfied by the same set of values of x and y: namely those values which leave a remainder 5 when divided by 7.

    I hope that helps to clear things up.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2008
    Posts
    191
    It was the solutions which was confuseing me. I appreciate your explanation very much Grandad, and thanks for clearing it up.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence classes of P(N)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 13th 2010, 09:26 AM
  2. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  4. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM
  5. Equivalence classes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 31st 2008, 12:04 AM

Search Tags


/mathhelpforum @mathhelpforum