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

4,031

Solution 1

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.

Solution 2

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

Solution 3

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:
4,031
Jony Thrive
Author by

Jony Thrive

Updated on April 06, 2020

Comments

  • Jony Thrive
    Jony Thrive over 3 years

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

  • Jony Thrive
    Jony Thrive almost 11 years
    For the first bit, why does having a + b = b + a necessarily lead to the conclusion that (a,b)R(a,b)?
  • 000
    000 almost 11 years
    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.
  • N. S.
    N. S. almost 11 years
    @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.
  • 000
    000 almost 11 years
    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.