If R is $(a,b)R(c,d) \iff a+d =b+c$ show that $R$ is an equivalence relation.

Question

The relation $R$ is defined n all positive integers such that, $(a,b)R(c,d) \iff a+d =b+c$ . Show that $R$ is an equivalence relation.

In order to be an equivalence relation, $R$ has to be reflexive, symmetric and transitive. I tried it as follows -

$(a,b)R(c,d) \iff a+d =b+c \equiv (a,b)R(c,d) \iff a-b =c-d$

$$(a,b)R(a,b) \iff a-b = a-b $$

It is true, therefore $R$ is reflexive. $$(c,d)R(a,b) \iff c-d=a-b $$ It is true, therefore R is symmetric. \begin{align*}(a,b)R(x,y) &\iff a-b = x-y \tag 1 \\ (x,y)R(c,d) &\iff x-y=c-d \tag 2 \\ \therefore (a,b)R(x,y) \land (x,y)R(c,d) &\iff a-b = x-y=c-d \implies a-b =c-d \end{align*} It is true, therefore $R$ is transitive. Is the above method correct?

Answer 1

Its not a good idea to use subtraction, for by default that relation is not symmetric. However you are correct. But I would suggest the following : $(a,b)R(c,d) \iff a+d =b+c \equiv (a,b)R(a,b) \iff a+b =a+b$

therefore R is trivially reflexive. $$(c,d)R(a,b) \iff c+b=d+a $$*and so a+d=b+c, which means (a,b)R(c,d)*. Therefore R is symmetric. \begin{align*}(a,b)R(x,y) &\iff a+y = b+x \tag 1 \\ (x,y)R(c,d) &\iff x+d=y+c \tag 2 \\ \therefore (a,b)R(x,y) \land (x,y)R(c,d) &\iff a+(x+d-c) = b+x \implies a+d =b+c \end{align*} Hence R is transitive. I hope you realized the difference. + is more convenient to work with.

Answer 2

More generally, for any function $f:X\to Y$, the relation $\sim$ on $X$ given by $a\sim b\Leftrightarrow f(a)= f(b)$ is an equivalence relation, whose equivalence classes are the fibers of $f$ (preimages of singletons). Try to first prove this and second see how it applies to this situation.

Answer 3

One can “avoid” subtraction by using a slightly different relation, that can be given in any (additive) commutative monoid. Let $X,{+}$ be an (additive) commutative monoid, with neutral element $0$, and define the relation $R$ on $X\times X$ by stipulating that $(a,b)\mathrel{R}(c,d)$ stands for $$ \text{there exists $x\in X$ such that $a+d+x=b+c+x$} $$ Reflexivity is obvious, taking $x=0$; also symmetry is obvious. Suppose now $(a,b)\mathrel{R}(c,d)$ and $(c,d)\mathrel{R}(e,f)$. Then we can write \begin{gather} a+d+x=b+c+x\\ c+f+y=d+e+y \end{gather} for some $x,y\in X$. Then, summing the two equalities, we get, applying commutativity and associativity, $$ a+f+(c+d+x+y)=b+e+(c+d+x+y) $$ which ends the proof.

If $X$ is the monoid of natural numbers with respect to addition, then we can apply the theorem according to which $$ a+x=b+x\qquad\text{implies}\qquad a=b $$ (which follows by induction from the axiom about uniqueness of predecessors) and conclude that the relation $R$ is exactly the one you were given.

Of course, subtraction is somewhat unavoidable: the fact that $R$ is an equivalence relation allows to define the integers, where subtraction is possible.

Answer 4

Let (a,b)=x, (b,c)=y and (c,d)=z; Now to prove that R on A is equivalence. We'll have prove that it is also reflexive(xRx), symmetric[(xRy)=(yRx)] and transitive[(xRy) and (yRz) implies (xRz)]. And the condition is: (a,b)R(c,d) implies a+d=b+c

1. xRx=(a,b)R(a,b) implies a+b=b+a which is true; therefore it is reflexive.

2. xRy=(a,b)R(b,c) implies a+c=b+b….1 & yRx=(b,c)R(a,b) implies b+b=c+a…2 here 1 and 2 are equal therefore R is symmetric.

3. xRy=a+c=b+b…1 & yRz=(b,c)R(c,d) implies b+d=2c…..2 implies that xRz=(a,b)R(c,d) implies a+d=b+c……3 Now Adding 1 and 2 we get: a+c+b+d=2b+2c implies a+d=b+c which is to be proved for transitivity.