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?

Solution 1:

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

Solution 2:

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