3
$\begingroup$

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

3 Answers 3

2

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.

  • 0
    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))$.2012-11-10
1

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

  • 0
    @Henry: What you’re missing is that to judge by EMACK’s questions over the last few days, this is almost certainly from a bog-standard introductory discrete math course in which this is simply a handy example, not part of a construction of the integers or the like. Assuming that to be the case, your concerns are therefore wholly irrelevant to the actual context of the question.2012-11-10
0

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.

  • 0
    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.2012-11-10