Results 1 to 10 of 10

Math Help - Equivalence Relation

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    80

    Equivalence Relation

    Let S=Z\{0}. Define a relation ~ on S by a~b if ab>0. Is ~ an equivalence relation? If so, describe the equivalence classes. My solution: For reflexive, we want to show that a~a. If a s a negative integer, then aa>0. If a is a positive integer, then aa>0. So, a~a. For symmetric, we want to show that a~b implies b~a. Since multiplication over the integers is commutative, ba>0 since neither a nor b can be 0. I am stuck on the transitive property. Is what I have correct so far, and will you help with the last property? I think overall ~ is an equivalence relation, but I am also not sure how to get the equivalence classes. Thanks!
    Last edited by lovesmath; January 17th 2013 at 11:54 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Equivalence Relation

    For transitivity, suppose that ab > 0 and bc > 0. Note that ac = (ab)(bc) / bē.

    Alternatively, it is easy to find a function f from S to {0, 1} such that

    x ~ y iff f(x) = f(y) (*)

    (hint: the name of f starts with s and ends with n). The property (*) says, "x and y are related if they have the same ... ." Every relation ~ that satisfies (*) for some function f is an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    80

    Re: Equivalence Relation

    Do x and y have to have the same sign?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Equivalence Relation

    Quote Originally Posted by lovesmath View Post
    Do x and y have to have the same sign?
    Yes. It may be better to make the range of f to be {-1, 1}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Equivalence Relation

    Quote Originally Posted by lovesmath View Post
    Do x and y have to have the same sign?
    What, exactly, are you referring to? For any x and y in Z\ {0}, no, they do not have to have the same sign. If you mean x and y such that x~ y, then, yes, the condition that xy> 0 means that x and y are either both positive or both negative.

    Added: Oh, I see. Yes, emakarov's 'hint: the name of f starts with s and ends with n). The property (*) says, "x and y are related if they have the same ... ." ' refers to "having the same sign".
    Last edited by HallsofIvy; January 17th 2013 at 02:37 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Equivalence Relation

    in simple english, the proof of transitivity is:

    if x and y have the same sign, and y and z have the same sign, then x and z have the same sign (which is whatever sign y happens to have).

    the equivalence class of 1 is called "positive", the equivalence class of -1 is called "negative".

    the function emakarov is thinking of is called the "sign function":

    sgn(x) = x/|x|. (*)

    this is actually a HOMOMORPHISM from the monoid of non-zero integers to the monoid {-1,1} that is, it preserves multiplication:

    sgn(xy) = sgn(x)sgn(y)

    and the identity:

    sgn(1) = 1.

    which is to say the equivalence relation x~y <=> xy > 0 forms a congruence on Z* = Z - {0}:

    if x~y and z~w, then xy~zw

    (this is another way of saying: [xy] = [x][y]).

    while all this may seem "abstract" you probably learned this long ago in the form:

    positive times positive is positive
    positive times negative is negative
    negative times positive is negative
    negative times negative is positive

    which is EXACTLY the same thing (replace "positive" by "the equivalence class of 1" and "negative" by "the equivalence class of -1").

    you probably use these rules EVERY DAY, and didn't even know the elegant and sophisticated structure underlying them. now you do. knowledge is POWRRRRRR.....

    ******************

    EDIT (*): sometimes it is more convenient to deal with another function (also called "sign")

    sgn(n) = 0, if n > 0
    sgn(n) = 1, if n < 0 suppose i call these sgn1 and sgn2. the relationship between them is this:

    sgn1(x) = (-1)sgn2(x)

    this means sums of sgn2 get turned into products of sgn1. this process is reversible, leading to "the arithmetic of parity" (evens and odds):

    even plus even is even
    odd plus even is odd
    even plus odd is odd
    odd plus odd is even

    note the similarity with the list above of positive/negative and multiplication. this is no accident.
    Last edited by Deveno; January 17th 2013 at 02:57 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    Re: Equivalence Relation

    Quote Originally Posted by Deveno View Post
    in simple english, the proof of transitivity is:

    if x and y have the same sign, and y and z have the same sign, then x and z have the same sign (which is whatever sign y happens to have).
    Note that emakarov had already said, in post #2, that "For transitivity, suppose that ab > 0 and bc > 0. Note that ac = (ab)(bc) / bē."
    If ab> 0 and bc> 0 then (ab)(bc) is the product of two positive numbers and so positive. And, of course, since b\ne 0, b^2> 0 so ac= (ab)(bc)/c^2 is positive.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Equivalence Relation

    Quote Originally Posted by HallsofIvy View Post
    Note that emakarov had already said, in post #2, that "For transitivity, suppose that ab > 0 and bc > 0. Note that ac = (ab)(bc) / bē."
    If ab> 0 and bc> 0 then (ab)(bc) is the product of two positive numbers and so positive. And, of course, since b\ne 0, b^2> 0 so ac= (ab)(bc)/c^2 is positive.
    there is nothing wrong with emakarov's proof. the whole point of what i'm trying to express is that equivalence classes don't just arise so that professors can give their students exercises. we use them for stuff...like simple rules that aid in making calculations easier.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jul 2011
    Posts
    80

    Re: Equivalence Relation

    Thank you!

    Similarly, I need to define a relation ~ on the integers, Z, by a~b if ab>0 and determine whether ~ is an equivalence relation. Again, describe the equivalence classes if necessary. I am fairly confident that ~ is an equivalence relation, but in proving it, do you have to consider the a=0 case? It works if a,b,c are positive/negative but not if one of them is 0 because the inequality cannot equal 0. Suggestions?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Equivalence Relation

    if there is one element k of Z, for which k~k is false, it's not an equivalence relation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relation on equivalence classes of other relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 7th 2013, 02:15 PM
  2. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  4. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  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