# Proving an equivalence relation on $\mathbb{Z}\times\mathbb{Z}$

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$.

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.

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$.

• 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
• @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

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)$.

• 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

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)