# Equivalence Relations

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$.

(a) Prove that $R$ is an equivalence relation.

Here is what I have so far. Is this correct?

Reflexive: $a \sim a$ $\implies$ $a+b=a+b$; $(a,b) R (c,d)$

Symmetric: if $a \sim b$ then $b \sim a$ $\implies$ if $a+d=b+c$ then $c+b=d+a$

Transitive: if $a \sim b$ and $b \sim c$ then $a \sim c$ $\implies$ if $a+d=b+c$ and $c+f=d+e$ then $a+d=d+e$

(b) Find $[(1,1)]$.

I'm not sure how to approach this.

-
Your derivation of transitivity looks incorrect. Can I suggest to stop using a and b to denote both ordered pairs and elements of the pair? –  Jacopo Notarstefano Feb 9 '11 at 22:00
Your symbols are hard to follow. Try writing out your proofs using complete sentences. For (b), this means finding all pairs $(c,d)$ such that $(1,1) \sim (c,d)$, which should be pretty easy given the definition. –  Nate Eldredge Feb 9 '11 at 22:01
How would I refer to the ordered pairs then? –  Krysten Feb 9 '11 at 22:06
in any way you like, as long as it is not the same way you use to refer to the components of pairs! –  Mariano Suárez-Alvarez Feb 9 '11 at 22:41
add comment

## 4 Answers

Your proof regarding the fact that $R$ is in fact an equivalence relation is indeed correct.

Now think what the equivalence class of $(1,1)$ could be, since $(1,1) R (1,1)$ you know that everyone in the equivalence class has the property that $(a,b)$ holds $a+1=b+1$, therefore $a=b$.

This means that the equivalence class of $(1,1)$ is $(a,a)$ for $a\in\mathbb{N}$.

-
add comment

HINT: The equivalence class of $(1,1)$ is made up of all pairs $(x,y)\sim(1,1)$. Write explicitely what the latter means and get a relation that need to be satisfied by $x$ and $y$.

-
add comment

HINT $\$ This is geometrically obvious once you note that the equivalence class containing $\rm\ (a,b)\$ is simply the slope $1$ line through it (with positive integer coordinates). In effect you are discovering the negative integers as those lines having no positive $x$-intercept (= normal-form), i.e. whose intercept is "negative". This "group of differences" construction is the additive analog of the field of fractions construction.

-
add comment

Let (a,b)R(a,b) a+b=b+a => R is reflexive (a,b are integers)

(a,b)R(c,d) if a+d=b+c and (c,d)R(a,b) if c+b=d+a; both are equal(a,b,c,d are integers) hence R is symmetric

(a,b)R(c,d) if a+d=b+c --->(1) (c,d)R(e,f) if c+f=d+e --->(2) add (1)&(2)
a+c+d+f=b+d+c+e, ==> a+f=b+e ie. (a,b)R(e,f) R is transitive. Hence R is an equivalence relation

-
add comment