# Math Help - Check this quick proof please[Equivalence relation ]

1. ## Check this quick proof please[Equivalence relation ]

Problem statement :

Let Z = { ..., -2, -1, 0, 1, 2, ...} denote the set of integers. Let Z x Z denote the set of ordered pairs of integers: Z x Z= { (x, y) | x, y in Z} .

Part (I). Define the relation ~ on Z by the rule a ~ b if and only if gcd(a,b) > 1 . Is an equivalence relation? If so, prove it; if not, give a counter example.

Attempt:

It has to satisfy reflexive,symmetric,and transitive property. But I realize that it does not satisfy the reflexive property because of its domain.

Proof :
Let a be an element from Z.

~ is reflexive if a~a

Since a is an element from Z, let a = 1.

a~a implies gcd(a,a) > 1. By definition, gcd(a,a) = a. Since a is 1.
It fails the definition. Thus ~ is not an equivalence relation because a~a does not
necessarily imply gcd(a,a) > 1.

Is the above correct?

2. Originally Posted by Matter_Math
Problem statement :

Let Z = { ..., -2, -1, 0, 1, 2, ...} denote the set of integers. Let Z x Z denote the set of ordered pairs of integers: Z x Z= { (x, y) | x, y in Z} .

Part (I). Define the relation ~ on Z by the rule a ~ b if and only if gcd(a,b) > 1 . Is an equivalence relation? If so, prove it; if not, give a counter example.

Attempt:

It has to satisfy reflexive,symmetric,and transitive property. But I realize that it does not satisfy the reflexive property because of its domain.

Proof :
Let a be an element from Z.

~ is reflexive if a~a

Since a is an element from Z, let a = 1.

a~a implies gcd(a,a) > 1. By definition, gcd(a,a) = a. Since a is 1.
It fails the definition. Thus ~ is not an equivalence relation because a~a does not
necessarily imply gcd(a,a) > 1.

Is the above correct?
Edit: Sorry I didn't read your post well enough. Yes you're right. Safe to ignore my original response. (I gave an alternate counterexample.)

Edit 2: Actually the wording of this is a bit off: "Thus ~ is not an equivalence relation because a~a does not necessarily imply gcd(a,a) > 1." Just say that 1~1 is not true therefore it's not an equivalence relation. Alternatively, say a~a is not true for all a in Z. Alternatively, say that gcd(a,a) > 1 is not true for all a in Z. Note that 1~1 not being true constitutes a counterexample.

----- Original response -----

Since it is not an equivalence relation, we give a counterexample.

gcd(2,6) = 2
gcd(6,15) = 3
gcd(2,15) = 1

3. Sweet. Thanks so much. You are of great help.

4. Originally Posted by Matter_Math
Sweet. Thanks so much. You are of great help.
You're welcome! Make sure to read my Edit #2 above since I didn't see your reply until just now.

5. Yep, I seen your edit.

Now instead of starting a new thread. I have 1 more question. Its part 2, from the question above. Here is the question :

Part (II). Define the relation ~ on Z x Z by the rule (a,b) ~ (a,b) if and only if there is a rational number r, so that a = a * r and b = b * r . Is an equivalence relation? If so, prove it; if not, give a counter example.

It is an equivalence relation. Here is the proof that I am asking you to check please:

~ is reflexive because :
(a,b) ~ (a,b) since a = a * 1, b = b * 1, thus r = 1

~ is symmetric because
if (a,b) ~ (a,b) then a = a*r , b = b*r, for some rational r.
then a = 1/r * a , b = 1/r * b.
thus if (a,b) ~ (a,b) for some r
then (a,b) ~ (a,b) for some 1/r

~ is transitive because :
[a] if (a,b) ~ (a1,b1) iff a = a1 * r1, b = b1 * r1, for some rational r1
[b] if (b,c) ~ (b2,c1) iff b = b2 * r2, c = c1 * r2, for some rational r2

[c] the (a,c) ~ (a1,c1) iff a = a1 * r3, c = c1 * r3, for some rational r3

since :
a = a1 * r1 //From [a]
a1 = 1/r1 * a

a = a1 * r3 //From [b]
a = (1/r1)*a * r3
r1*a = r3*a
r1 = r3

c = c1 * r2 //From [b]
c1 = 1/r2 * c

c = c1 * r3 //From [c]
c = (1/r2) * c * r3
r2*c = r3*c
r2 = r3

Since r1 = r3, and r2 = r3, thus r1 = r2.

Thus (a,b) ~ (a1,c1) for some rational r2.

Is the above correct? I wasn't sure how to close the proof. Thank you again.

6. Originally Posted by Matter_Math

Now instead of starting a new thread. I have 1 more question. Its part 2, from the question above. Here is the question :

Part (II). Define the relation ~ on Z x Z by the rule (a,b) ~ (a,b) if and only if there is a rational number r, so that a = a * r and b = b * r . Is an equivalence relation? If so, prove it; if not, give a counter example.

It is an equivalence relation. Here is the proof that I am asking you to check please:

~ is reflexive because :
(a,b) ~ (a,b) since a = a * 1, b = b * 1, thus r = 1

~ is symmetric because
if (a,b) ~ (a,b) then a = a*r , b = b*r, for some rational r.
then a = 1/r * a , b = 1/r * b.
thus if (a,b) ~ (a,b) for some r
then (a,b) ~ (a,b) for some 1/r

~ is transitive because :
[a] if (a,b) ~ (a1,b1) iff a = a1 * r1, b = b1 * r1, for some rational r1
[b] if (b,c) ~ (b2,c1) iff b = b2 * r2, c = c1 * r2, for some rational r2

[c] the (a,c) ~ (a1,c1) iff a = a1 * r3, c = c1 * r3, for some rational r3

since :
a = a1 * r1 //From [a]
a1 = 1/r1 * a

a = a1 * r3 //From [b]
a = (1/r1)*a * r3
r1*a = r3*a
r1 = r3

c = c1 * r2 //From [b]
c1 = 1/r2 * c

c = c1 * r3 //From [c]
c = (1/r2) * c * r3
r2*c = r3*c
r2 = r3

Since r1 = r3, and r2 = r3, thus r1 = r2.

Thus (a,b) ~ (a1,c1) for some rational r2.

Is the above correct? I wasn't sure how to close the proof. Thank you again.
Hmm I think all your reasoning is quite good except for one pesky fact: 1/r is undefined when r = 0. Thus we get a counterexample on symmetric property,

true that (0,0) ~ (1,1) using r = 0

but not true that (1,1) ~ (0,0).

7. Oh dang. In my work on paper, I had stated that "for rational r != 0". I wonder if the teacher meant for this to happen. I will ask him tomorrow.

8. Oh thanks undefined. That was a typo. I told my professor and he corrected it. Now everyone in class has to prove this and can't take the easy way out.

9. Originally Posted by Matter_Math
Oh thanks undefined. That was a typo. I told my professor and he corrected it. Now everyone in class has to prove this and can't take the easy way out.
You're welcome, always happy to prevent people from taking the easy way out.