# Showing that $R$ is an equivalence relation on $X \times X$

Let $X = \{1,2,3,..,10\}$ define a relation $R$ on $X \times X$ by $(a,b)R(c,d)$ if $ad=bc$. Show that R is an equivalence relation on $X \times X$.

I know that the $R$ have to be reflexive (because $ad=bc$), but I don't know how to prove that $R$ is reflexive, symmetric, and transitive? thx

-
Just write down what it would mean for each of the properties being true, and check if that is valid for all allowed values of $a$, $b$, $c$ and $d$. – vonbrand Feb 8 '13 at 4:18
Hint: See $(a,b)$ as a fraction and observe that your relation splits all possible fractions into classes according to their ratio. – 1015 Feb 8 '13 at 4:18
@amWhy Ah, right. +1 – 1015 Feb 8 '13 at 4:26
@julien: ${}$:-) ${}{}{}{}{}{}$ – amWhy Feb 8 '13 at 4:30

Hint: it might help to note that your relation $$R: (a, b)\,R\,(c, d) \iff ad = bc$$ can be equivalently expressed as

$$R: (a, b)\,R\,(c,d) \iff \frac ab= \frac cd$$

That is, if the ratio of $a$ to $b$ equals the ratio of $c$ to $d$, then $(a, b) R (c, d)$.

You need to apply the definitions of reflexivity, symmetry, and transitivity: in this case

($a$) Reflexivity: Is it the case that for all $(a, b) \in X\times X$, $(a,b)\,R\,(a,b)$?

($b$) Symmetry: Is it the case that for all $(a, b), (c, d) \in X\times X,$ if $(a, b) R (c, d),$ then $\,(c, d) R (a, b)\,?\,$ Why does $(a, b) R (c, d)$ immediately imply about whether $(c,d)\,R\,(a,b)$?

($c$) Transitivity: Is it the case that for all $(a, b), (c, d), (e, f) \in X\times X,$ that if $(a,b)\,R\,(c,d)$ and $(c,d)\,R\,(e,f)$, then it must follow that $(a,b)\,R\,(e,f)$?

If you can answer yes to each of the above (and you can), then your relation $R$ is an equivalence relation.

-
What are your thoughts, user1988385? – amWhy Feb 8 '13 at 4:26
I got the reflexive and symmetry part, but still stuck on the transitivity part – user1988385 Feb 8 '13 at 4:35
Suppose $(a, b) R (c, d)$, and $(c, d) R (e, f)$. Then $ad= bc$ and $cf = de$. Then $\frac ab = \frac cd$. And $\frac cd = \frac ef$. And we want to show that it must be true that this implies $(a, b) R (e, f)$. We know that $\frac ab = \frac cd = \frac ef$, so it follows that $\frac ab = \frac ef$. Cross mulitply and we get $af = be$. But this means that $(a, b) R (e, f)$. Hence, the relation R is transitive! – amWhy Feb 8 '13 at 4:48
ah I got it. thx man – user1988385 Feb 8 '13 at 5:07

Hint: ($1$) Reflexive: What does it mean to say $(a,b)\,R\,(a,b)$? Write it out and you'll see it immediately.

($2$) Symmetric: Using the definition for $R$, what does it mean to say $(a,b)\,R\,(c,d)$? Why does it immediately imply $(c,d)\,R\,(a,b)$?

($3$) Transitive: Again, take three elements, $(a,b)\,R\,(c,d)$ and $(c,d)\,R\,(e,f)$. Show how this implies $(a,b)\,R\,(e,f)$.

-

Hint $\$ You have $\rm\:(a,b)\sim (b,d) \smash[t]{\overset{\ def}{\iff}} a/b = c/d\iff f(a,b) = f(c,d)\$ for $\rm\:f(x,y) = x/y.$

Now it is quite easy to prove that any relation of the above form is an equivalence relation.

More generally, suppose $\rm\ u\sim v\ \smash[t]{\overset{\ def}{\iff}}\, f(u) \approx f(v)\$ for a function $\rm\,f\,$ and equivalence relation $\,\approx.\, \$ Then the equivalence relation properties of $\,\approx\,$ transport (pullback) to $\,\sim\,$ along $\rm\,f\,$ as follows:

• reflexive $\rm\quad\ f(v) \approx f(v)\:\Rightarrow\:v\sim v$

• symmetric $\rm\,\ u\sim v\:\Rightarrow\ f(u) \approx f(v)\:\Rightarrow\:f(v)\approx f(u)\:\Rightarrow\:v\sim u$

• transitive $\rm\ \ \ u\sim v,\, v\sim w\:\Rightarrow\: f(u)\approx f(v),\,f(v)\approx f(w)\:\Rightarrow\:f(u)\approx f(w)\:\Rightarrow u\sim w$

Such relations are called (equivalence) kernels. One calls $\, \sim\,$ the $\,(\approx)\,$ kernel of $\rm\,f.$

-
I was just writing down the same idea! +1 – 1015 Feb 8 '13 at 5:02

Consider the function $f:X\times X\rightarrow \mathbb{R}$ defined by $$f(a,b):=\frac{a}{b}$$ and note that $$(a,b)\;R\;(c,d)\quad\Leftrightarrow\quad f(a,b)=f(c,d).$$

The fact that it is an equivalence relation on $X\times X$ follows from the following general result.

If $f:Y\longrightarrow Z$ is a function, then the relation $$y_1\;R_f\;y_2\quad\mbox{if}\quad f(y_1)=f(y_2)$$ is an equivalence relation on $Y$.

The proof is very close to trivial, if not trivial.

Note that the equivalence classes are the inverse images of singletons of $Z$ by $f$, or the level sets of $f$, if you prefer.

-