Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on some discrete mathematics problems, and have run into an issue involving proving an equivalence relation.

The relation I'm tasked with proving is the relation $R$ defined on $\mathbb{Z}\times \mathbb{Z}$ by: $$(a,b)R(c,d)\;\;\text{ if and only if}\;\;\; a+d = b+c.$$

I understand the basic key components needed, like what's needed to prove reflexivity, symmetry, and transitivity, but I don't know how to plug the above information into these rules.

For instance, starting with proving reflexivity, I know that we must show that $(a,b)\in R$, but don't know how to do this with the constraints of $(a,b)R(c,d)$ if and only if $a+d = b+c$.

share|improve this question
add comment

4 Answers

Using your relation: $(a,b)R(c,d)$ if and only if $a+d = b+c$, you need to determine:

Reflexivity: is $(a, b) R (a, b)$ for all $(a, b) \in \mathbb{Z} \times \mathbb{Z}$?

I.e., for all $a, b \in \mathbb{Z},\;\;$is $a + b = a + b$? Here $(a, b)$ is standing in for $(c, d)$.
Since for all $a, b \in \mathbb{Z},\;\;(a + b) = (a + b),\;\;$ $R$ is reflexive.

Symmetry: if $(a b) R (c, d)$, is $(c, d) R (a, b)$ for all $(a, b), (c, d) \in \mathbb{Z} \times \mathbb{Z}$?

That is, for any $a, b, c, d \in \mathbb{Z}$: if $(a + d) = (b + c),\;$ does $\;(c + b) = (d + a)$?
If so, then $R$ is symmetric.

Transitivity:
If $\;\;(a, b) R (c, d)$ and $(c, d) R (e, f),\;\;$ is $\;\;(a, b) R (e, f)$ for all $(a, b), (c, d), (e, f) \in \mathbb{Z} \times \mathbb{Z}\;$?

That is, for any $a, b, c, d, e, f \in \mathbb{Z}$, if $(a+d) = (b + c)$ and $(c + f) = (d + e)$, does it follow then that $(a + f) = (b+ e)\;$?
If so, then $R$ is transitive.


If $R$ proves to satisfy all the above properties, then as you know, $R$ is an equivalence relation.

share|improve this answer
add comment

Hint

$$a+d=b+c \Leftrightarrow a-b=c-d \,.$$

Now, proving that

$$(a,b)R(c,d) \Leftrightarrow a-b=c-d$$

is an equivalence relation is much easier.

P.S. If you know a little group Theory.

The equivalence relation is exactly the standard one defined by the subgroup $N=\{ (x,x)|x \in \mathbb Z \}$ of $\mathbb Z \times \mathbb Z$.

share|improve this answer
    
Completely tangential, but the map $f: \mathbb{Z}^2 \to \mathbb{Z}$ with $(a,b) \mapsto a-b$ has some cute properties. Just something to think about. –  000 Dec 7 '12 at 12:15
2  
@Limitless Actually is not tangential... If $f:X \to Y$ is any function, then $xRy \Leftrightarrow f(x)=f(y)$ is an equivalence relation. The converse is also true, if we have an equivalence relation on $X$, then there exists some $Y$ and some $f:X \to Y$ so the equivalence is exactly the one above. –  N. S. Dec 7 '12 at 16:00
    
That is so awesome! :-) I thought it was just interesting to me, but I now see that there is a general theorem here that is quite intriguing. Thanks for sharing it with me. –  000 Dec 8 '12 at 0:42
add comment

Reflexivity: For any $(a,b)\in\mathbb Z\times\mathbb Z$, we have $a+b=b+a$, so $(a,b)R(a,b)$.

Symmetry: For any $(a,b),(c,d)\in\mathbb Z\times\mathbb Z$, if $(a,b)R(c,d)$ then $a+d=b+c$, so $c+b=d+a$, so $(c,d)R(a,b)$.

Transitivity: For any $(a,b),(c,d),(e,f)\in\mathbb Z\times\mathbb Z$, if $(a,b)R(c,d)$ and $(c,d)R(e,f)$ then $a+d=b+c$ and $c+f=d+e$, so $a+f=(a+d)+(c+f)-d-c=(b+c)+(d+e)-d-c=b+e$, so $(a,b)R(e,f)$.

share|improve this answer
    
For the first bit, why does having a + b = b + a necessarily lead to the conclusion that (a,b)R(a,b)? –  Jony Thrive Dec 6 '12 at 5:22
add comment

For reflexivity, you need to show that for the case of (a,b)R(a,b), the result a+b = b+a is necessarily true, which it is if the + is commutative.

For symmetry, show that (c,d)R(a,b) must hold whenever (a,b)R(c,d) holds:

(c,d)R(a,b) iff c+b = d+a

(a,b)R(c,d) iff a+d = b+c

Assuming that you are allowed to rely on the symmetry of the = and commutativity of + in their common usage, you can show that those two statements necessarily imply each other.

For transitivity, show that the two statements

(a,b)R(c,d) iff a+d = b+c

(c,d)R(e,f) iff c+f = e+d

imply that

a+f = b+e

therefore (a,b)R(e,f)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.