# Equivalence Relation problem [duplicate]

Let $S$ be the relation on $\mathbb{N} \times \mathbb{N}$ defined by $(a,b)S(c,d)$ if and only if $ad=bc$. Prove this is an equivalence relation on $\mathbb{N} \times \mathbb{N}$.

I think I've found this to be reflexive and symmetric, but I'm stuck on transitivity. Can someone check my work so far and assist with testing transitivity?

Reflexive: Let $(x,y)S(x,y)$. Then $xy = yx$. So $S$ is reflexive. Symmetric: Suppose $(a,b)S(c,d)$. Then, $ad = bc$. Therefore, $da = cb$ and $cb = da$. Therefore, $(c,d)S(a,b)$. Thus, $S$ is symmetric. Transitive: Suppose $(a,b)S(b,c)$. Then $ac = bb$.

This is where I'm stuck. Any ideas?

-

## marked as duplicate by Davide Giraudo, apnorton, Amzoti, Dominic Michaelis, Mark BennetJul 31 '13 at 20:38

Let $(x,y)S(x,y)$. Then $xy=yx$. So $S$ is reflexive.

Your logic here is backwards. The way you have it, you’re assuming that $(x,y)S(x,y)$, when in fact that’s what you’re supposed to be showing. What you should say is something like this:

Let $(x,y)\in\Bbb N\times\Bbb N$. Then $xy=yx$, so $(x,y)S(x,y)$, Since $(x,y)$ was an arbitrary element of $\Bbb N\times\Bbb N$, $S$ is reflexive.

Your argument for symmetry of $S$, on the other hand, is fine.

For transitivity you want to let $(a,b),(c,d),(e,f)\in\Bbb N\times\Bbb N$ be such that $(a,b)S(c,d)$ and $(c,d)S(e,f)$, and from that you want to prove that $(a,b)S(e,f)$. Your hypothesis tells you that $$ad=bc\tag{1}$$ and $$cf=de\tag{2}\;,$$ and you want to show that $af=be$. What happens if you multiply together equations $(1)$ and $(2)$; can you then use the fact that your $\Bbb N$ does not include $0$ to deduce that $af=be$?

-
Well if I multiply both equations I get adcf = bcde. Factoring out cd would yield af = be. I'm not sure if that is a sufficient answer though. – blutuu Dec 10 '12 at 6:22
@blutuu: That’s exactly what you need to do. The fact that $cd\ne 0$ allows you to conclude that if $adcf=bcde$, then $af=be$, and that’s precisely what you were trying to prove. – Brian M. Scott Dec 10 '12 at 6:23
Ok then perfect. Thanks again. – blutuu Dec 10 '12 at 6:29
@blutuu: You’re welcome. – Brian M. Scott Dec 10 '12 at 6:30

Your problem is that you're comparing the wrong things. You want to show that if $(a,b),(c,d),(e,f) \in N\times N$, and $(a,b)S(c,d)$ and $(c,d)S(e,f)$ then $(a,b)S(e,f)$.

-
Yeah I was confused about how to do this with ordered pairs. – blutuu Dec 10 '12 at 6:17
When in doubt, go back to the set-theoretic definition. Your set is NxN, so you need to start with three arbitrary elements of NxN, then put the transitivity condition on them and prove that they are equal. – Gyu Eun Lee Dec 10 '12 at 6:25

Instead of using the usual definition for an equivalence relation, let me try to apply the alternative definition I discovered recently; see Is this alternative definition of 'equivalence relation' well-known? useful? used?

All variables in this answer range over the non-zero natural numbers: if zero is allowed then $\;S\;$ is not an equivalence relation.

We're to prove that $\;S\;$ is an equivalence relation, i.e. --using the alternative definition and applying it to ordered pairs-- that for every $\;a,b,c,d\;$ $$(a,b)S(c,d) \;\;\equiv\;\; \langle \forall x,y :: (a,b)S(x,y) \;\equiv\; (c,d)S(x,y) \rangle$$ Expanding the definition of $\;S\;$, this is equivalent to $$(0)\;\;\;ad=bc \;\;\equiv\;\; \langle \forall x,y :: ay=bx \;\equiv\; cy=dx \rangle$$ It seems reasonable to try and simplify the right hand side to the left hand side. We calculate: \begin{align} & \langle \forall x,y :: ay=bx \;\equiv\; cy=dx \rangle \\ \equiv & \;\;\;\;\;\text{"divide left hand side by $\;a\;$ and right hand side by $\;c\;$} \\ & \;\;\;\;\;\phantom{"}\text{-- this gives us a bare $\;y\;$ which we can use in the next step"} \\ & \langle \forall x,y :: y=bx/a \;\equiv\; y=dx/c \rangle \\ \equiv & \;\;\;\;\;\text{"logic: using rule $(1)$ below"} \\ & \langle \forall x :: bx/a = dx/c \rangle \\ \equiv & \;\;\;\;\;\text{"divide by $\;x\;$; leave out now-superfluous $\;\forall x\;$; multiply by $\;ac\;$"} \\ & bc = da \\ \end{align} Note how all divisions were allowed because our domain does not contain zero.

We've now proven $(0)$, which completes the proof.

Note that rule $$(1)\;\;\; \langle \forall y :: y = p \;\equiv\; y = q \rangle \;\;\equiv\;\; p = q$$ has a very simple proof: for $\;\Rightarrow\;$ take $\;y := p\;$, and $\;\Leftarrow\;$ is just Leibniz' rule.

-