1. ## 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!

2. ## 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.

3. ## Re: Equivalence Relation

Do x and y have to have the same sign?

4. ## Re: Equivalence Relation

Originally Posted by lovesmath
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}.

5. ## Re: Equivalence Relation

Originally Posted by lovesmath
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".

6. ## 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.

7. ## Re: Equivalence Relation

Originally Posted by Deveno
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.

8. ## Re: Equivalence Relation

Originally Posted by HallsofIvy
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.

9. ## 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?

10. ## Re: Equivalence Relation

if there is one element k of Z, for which k~k is false, it's not an equivalence relation.