0

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?

Teddy38
  • 3,309
S.Dan
  • 1,115
  • Yes, it's correct. The exercise hints at the construction of the integers from the natural numbers; if you didn't have the integers to begin with, you wouldn't be able to write down "$a-b$", and then you'd have to do a bit more work to verify it's an equivalence relation. If the exercise makes no mention of this (or some similar) caveat, though, then you're probably good with this solution. – Dustan Levenstein Aug 01 '14 at 06:32
  • 3
    Using subtractions to prove that R is an equivalence relation is a bit odd since R is mainly used to build the integer line Z, and in particular, to define subtraction. And it is quite unnecessary, everything works with sums. – Did Aug 01 '14 at 06:32
  • 1
    In fact, if one already knows Z, then R is just the kernel of the natural map N x N -> Z, (a,b) -> a-b. Kernels are always equivalence relations. – Martin Brandenburg Aug 01 '14 at 08:51
  • 1
    @Did: You cannot avoid the rule $a+x=b+x \ \Rightarrow a=b$, which has to be proven from the Peano axioms. – Christian Blatter Aug 01 '14 at 08:54
  • @ChristianBlatter Sure, but only for transitivity, not everywhere as the OP suggests (and even for transitivity, there are ways to avoid it). – Did Aug 01 '14 at 12:48
  • See also: http://math.stackexchange.com/questions/958690/equivalence-relations-for-mathbbn-times-mathbbn-defined-as-m-n-sim – Martin Sleziak Jun 03 '15 at 11:35

4 Answers4

3

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.

creative
  • 3,539
  • As mentioned by Did, using subtraction negates the point of this proof. $;$ –  Aug 01 '14 at 07:06
0

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.

anon
  • 151,657
  • Check the definition of $R,$! (I had originally made the same mistake.) – Christian Blatter Aug 01 '14 at 10:19
  • @ChristianBlatter Haha, oops, you're right. Serendipitously this same answer still applies, only suggesting something other than what I was originally. (This does involve subtraction though.) – anon Aug 01 '14 at 10:21
0

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.

egreg
  • 238,574
  • More relevantly, one can apply the theorem if $X$ is the semigroup of positive integers. $\hspace{1.42 in}$ –  Aug 01 '14 at 09:37
  • @RickyDemer In my opinion, semigroups without identity are just an odd curiosity. ;-) – egreg Aug 01 '14 at 10:02
0

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.

Arun
  • 1