# Equivalence Relation On A Set Of Ordered-Pairs

The question is, "Let R be the relation on the set of ordered pairs of positive integers such that $((a, b), (c, d)) ∈ R$ and only if $a+d=b+c$. Show that R is an equivalence relation."

There are two ways to prove this, but I only understand the second one.

The first way to proof: "By algebra, the given conditions is the same as the condition that $f((a,b))=f((c,d))$, where $f((x,y))=x-y$. Therefore, this is an equivalence relation."

I am not remotely sure of what they are doing...

-

You are given

$$a + d = b + c$$

as being equivalent to $(a, b) R (c, d)$ (i.e. $((a, b), (c, d))\in R$).

Then, you can do

$$a + d - b = c$$ (subtract b from both sides) $$a - b = c - d$$ (subtract d from both sides)

So then define $f((x, y)) = x - y$, and now you have the given statement. Now, it's easy to see the given relation is an equivalence relation, being that it now follows directly from the properties of equality.

-
+1 mike4ty4. Nice answer. Just a side note: Opening with "It's really simple..." can strike some users as demeaning. I don't think the OP would have posted the question if s/he found it simple. I doubt you meant to be demeaning. I suspect you meant to be encouraging... – amWhy Nov 10 '12 at 1:16
So, you are saying that $a-b=c-d$ becomes $f((x,y))=x-y$? Because I can't see how that alteration occurs. I am sorry, I do wish it was easy. Some day, however, it will be. – Mack Nov 10 '12 at 1:19
@amWhy: Thanks. I removed the "It's really simple" bit just in case. – mike4ty4 Nov 10 '12 at 1:23
@EMACK: You define that function, and then rewrite the equation in terms of it. Then you have an equivalent condition, expressed in terms of a function. This condition is equivalent to the equation, so also equivalent to the original equivalence relation. – mike4ty4 Nov 10 '12 at 1:23
And $a - b = c - d$ is equivalent to $f((a, b)) = f((c, d))$, not equivalent to $f((x, y)) = x - y$. $f((x, y)) = x - y$ defines the function f in the equation $f((a, b)) = f((c, d))$. – mike4ty4 Nov 10 '12 at 1:29

They’re using the result of this problem. First they define the function

$$f:\Bbb Z^+\times\Bbb Z^+\to\Bbb Z:\langle m,n\rangle\mapsto m-n\;.$$

From the earlier problem you know that the relation

$$\langle m,n\rangle\sim\langle k,\ell\rangle\quad\text{iff}\quad f(\langle m,n\rangle)=f(\langle k,\ell\rangle)$$

is an equivalence relation on $\Bbb Z^+\times\Bbb Z^+$. Then they observe that

\begin{align*} \big\langle\langle m,n\rangle,\langle k,\ell\rangle\big\rangle\in R\quad&\text{iff}\quad a+d=b+c\\ &\text{iff}\quad a-b=c-d&&\text{by ordinary algebra}\\ &\text{iff}\quad f(\langle m,n\rangle)=f(\langle k,\ell\rangle)\\ &\text{iff}\quad\langle m,n\rangle\sim\langle k,\ell\rangle\;. \end{align*}

In other words, the relation $R$ is exactly the same as the relation $\sim$ defined using the function $f$, and since $\sim$ is an equivalence relation, so is $R$.

-
Is $m-n \in \Bbb Z^+$ when $m \lt n$? – Henry Nov 10 '12 at 1:25
@Henry: Typo. I’ve been typing $Z^+$’s all day. Thanks; fixed now. – Brian M. Scott Nov 10 '12 at 1:30
I think it was less an error in your answer and more of a sleight of hand in the proof itself, which should not be assuming the existence of $\Bbb Z$. – Henry Nov 10 '12 at 1:32
@Henry: Why on earth shouldn’t the proof assume the existence of $\Bbb Z$? I think that it’s a very nice proof. – Brian M. Scott Nov 10 '12 at 1:38
Because the motivation for R is the construction of all integers from natural numbers (or perhaps a definition of subtraction). Otherwise why start "Let R be the relation on the set of ordered pairs of positive integers". A similar relation such as $(a,b)R(c,d) \text{ iff } ad=bc$ on $Z\times Z^{\not = 0}$ motivates the construction of rationals and it would be similarly wrong to use $x/y$ in the proof. – Henry Nov 10 '12 at 9:44

They are cheating. R is in fact a way of extending the natural numbers (or positive integers) to all integers, as shown in Wikipedia.

But even if you know what subtraction means for natural numbers or positive integers, the statement $f((x,y))=x-y$ is not meaningful for natural numbers or positive integers when $x \lt y$ and so should not be used in a proof.

-
If this is from the kind of course strongly suggested by EMACK’s other questions, they are not cheating at all; you’ve simply completely misunderstood the context. The course almost certainly isn’t about foundational issues at all, and the exercises are simply intended to give students practice working with the basic concepts associated with relations. – Brian M. Scott Nov 10 '12 at 10:06