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.

  • 1
    +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...2012-11-10
  • 0
    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.2012-11-10
  • 1
    @amWhy: Thanks. I removed the "It's really simple" bit just in case.2012-11-10
  • 0
    @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.2012-11-10
  • 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
    Is $m-n \in \Bbb Z^+$ when $m \lt n$?2012-11-10
  • 0
    @Henry: Typo. I’ve been typing $Z^+$’s all day. Thanks; fixed now.2012-11-10
  • 0
    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$.2012-11-10
  • 0
    @Henry: Why on earth shouldn’t the proof assume the existence of $\Bbb Z$? I think that it’s a very nice proof.2012-11-10
  • 0
    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.2012-11-10
  • 0
    Once you have proved R is an equivalence relation, you can define the integers as the equivalence classes. You can then define addition on the integers in the obvious way and can prove it is a group with an identity and additive inverses, which can lead to a definition of subtraction. So using subtraction of integers in the proof is premature.2012-11-10
  • 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