Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
    
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)$.

share|improve this answer

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.