Need help with proving equivalence relation on Z x Z

987 Views Asked by At

I need help with a problem from my discrete math course. I'm sure this problem is rather simple but I just can't figure out how to start it. I know I need to prove it is reflexive, symmetric, and transitive but I don't have any similar examples.

Let $\operatorname R$ be a relation on $\mathbb Z \times\mathbb Z$ such that $(a,b)\operatorname R(c,d) \iff a+b^3=c+d^3$.

Prove that $\operatorname R$ is an equivalence relation.

2

There are 2 best solutions below

1
On

Reflexivity: $\forall (a,b)\in\Bbb Z\times\Bbb Z : (a,b)\operatorname R(a,b)$ which means:

$$\forall (a,b)\in\Bbb Z\times\Bbb Z : a+b^3=a+b^3$$

Q: Does $a+b^3=a+b^3$ for every possible pair? Are there any possible exceptions?

A: Yes and no (resp.). So relation $\operatorname R$ is reflexive.


Symmetry: provide your definition.   Does this hold for all two pairs? Are there any exceptions?


Transitivity: repeat the drill.

0
On

To prove R is an equivalence relation by definition is to prove it is reflexive, symmetric, and transitive

-Reflexivity: $(a,b)R(a,b) \iff a+b^3=a+b^3$ this one is trivial.

-Symmetry: $(a,b)R(c,d) \implies (c,d)R(a,b)$ this one is also trivial since it's the same equality.

-Transitivity: $(a,b)R(c,d) \land (c,d)R(e,f) \implies (a,b)R(e,f)$

$$\begin{align}(a,b)R(c,d)\land(c,d)R(e,f) &\iff (a+b^3=c+d^3) \land (c+d^3=e+f^3) \\&\iff a+b^3=e+f^3 \implies (a,b)R(e,f)\end{align}$$