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.

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.



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

  • $\begingroup$ 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. $\endgroup$
    – 000
    Dec 7 '12 at 12:15
  • 2
    $\begingroup$ @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. $\endgroup$
    – N. S.
    Dec 7 '12 at 16:00
  • $\begingroup$ 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. $\endgroup$
    – 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)$.

  • $\begingroup$ For the first bit, why does having a + b = b + a necessarily lead to the conclusion that (a,b)R(a,b)? $\endgroup$ 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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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