Question:Let $X=\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$. Define a relation $\sim$ on $X$ by declaring that $(a, b)\sim(c, d)$ if and only if $ad = bc$ Prove that the relation $\sim$ is an equivalence relation.

My attempt $ab = ba \Leftrightarrow (a, b) \sim (a, b)$. When I focus on left side of the biconditional, the relation $\sim$ is symmetric, but when I see the right side, the relation is reflexive. I can't clearly say the relation.

$ab= ab \Leftrightarrow (a, a) \sim (b, b)$. I don't know how to define this relation when I look at the right side. But when I look at the left side, it's reflexive relation.

For a transitive relation, I'm not clearly sure if I have to write "$ab=bd=cd$". But what should follow after "$ab=bd=cd$"?

Can you complete the proof?

[Edit] Now I know how to prove it.

(i) $ab = ba \Leftrightarrow (a, b) \sim (a, b)$

Therefore,~ is reflexive

(ii) $[ad = bc \Leftrightarrow (a, b) \sim (c, d)]$

$\implies$ [cb=da $\Leftrightarrow$ (c, d) $\sim$ (a, d)]

Therefore, ~ is symmetric

(iii) $[ad = bc \Leftrightarrow (a, b) \sim (c, d)]$ $\land$ [cf=de $\Leftrightarrow$ (c, d) $\sim$ (e, f)]

$\implies$ [ $\dfrac {ad} {de}$= $\dfrac {bc}{cf}$ $\Leftrightarrow$ af=be $\Leftrightarrow$ (a, b) $\sim$ (e, f)]

Therefore ~ is transitive

By (i), (ii), (iii), the relation ~ is an equivalence relation.

[FYI] A relation $R$ from $A$ to $B$ is a subset of the Cartesian product $A\times B$. It is customary to write $aRb$ for $(a, b)\in R$. The symbol $aRb$ is read "$a$ is $R$-related to $b$.

$A$ relation on a set $A$ is a relation from $A$ to $A$.

$R$ is reflexive if and only if $\forall x\in X, xRx$

$R$ is symmetric if and only if $xRy\Rightarrow yRx$

$R$ is transitive if and only if $xRy\land yRz\Rightarrow xRz$.

$R$ is an equivalence relation if and only if R is reflexive, symmetric, and transitive.


Since multiplication is commutative in $\Bbb Z,$ then $ab=ba.$ Hence, as you noted, the relation is reflexive.

To prove symmetry, start by supposing that $(a,b)\sim(c,d),$ meaning that $a,b,c,d$ are integers with $b,d\ne0,$ and $ad=bc.$ You must then prove that $(c,d)\sim(a,b),$ which you will do by showing that $cb=da.$

To prove transitivity, start by assuming that $(a,b)\sim(c,d)$ and $(c,d)\sim(x,y).$ This means that $a,b,c,d,x,y$ are integers with $b,d,y\neq0,$ such that $ad=bc$ and $cy=dx.$ You must use these assumptions to prove that $(a,b)\sim(x,y),$ which you will do by proving that $ay=bx.$

Added: As a side note, your second paragraph--the one about $(a,a)\sim(b,b)$--isn't in any way pertinent to the proof.


(You don't need biconditionals for these)

Reflexive: Take any $(a,b)$ in the set. Then clearly $(a,b)\sim(a,b)$ since $ab=ba$.

Symmetric: Take another $(c,d)$ in the set. We want to show that $(a,b)\sim(c,d)\implies(c,d)\sim(a,b)$. The left side means that $ad=bc$. This means of course that $cb=da$, so the right side is also true.

Transitive. Take another $(e,f)$ in the set. Suppose that $(a,b)\sim(c,d)$ AND $(c,d)\sim(e,f)$. We have $ad=bc$ and $cf=ed$. Then we have $adf=bcf=bed$, so $af=be$. This means that $(a,b)\sim(e,f)$.

Note that, in the last step, we must divide by $d$, so $d$ can't be zero. This is why we can't define the same equivalence relation on $\Bbb{Z}\times\Bbb{Z}$.


It seems like you are on the right track, but let me write the proofs as I would have done it to clear up any confusion.

I want to prove that the relation is reflexive, so take $(a,b)\in X$. We need to show that $(a,b)\sim (a,b)$. By definition of $\sim$, this is equivalent to $ab = ba$, which is true, because the order of multiplication doesn't matter.

To show that it is symmetric, suppose that $(a,b)\sim (c,d)$. We have to prove that then also $(c,d)\sim (a,b)$. By definition, our hypothesis is equivalent to $ad = bc$. I can rewrite this as $cb = da$, which is equivalent to $(c,d)\sim (a,b)$, which proves that the relation is symmetric.

As for transitivity, take $(a,b),(c,d),(e,f)\in X$, such that $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$. We need to show that $(a,b)\sim (e,f)$. By our hypothesis, we have that $ad = bc$ and $cf = de$. We are trying to prove that $af = be$. Take $ad = bc$ and multiply it by $f$ (which is non-zero), and take $cf = de$ and multiply it by $b$ (which is non-zero). This gives you $$adf = bcf,$$ and $$bcf = bde.$$ Combining these two equations, we see that $$adf = bde,$$ which you can divide by $d$ (which is non-zero) to obtain $af = be$, which is what we set out to prove. The relation is thus transitive.

As a side note, what relation does this resemble? You have $X=\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$, and $(a,b)\sim (c,d)$, iff $ad = bc$. This is very similar to equality of fractions, i.e. $\frac{a}{b} = \frac{c}{d}$, iff $ad = bc$.


$(a,b)\sim(c,d) : ad=bc$ then $(a,b)\sim(a,b) : ab=ba$ $(a,b)\sim(c,d) : ad=bc$, since$ad=da,bc=cb$, then $bc = ad :(c,d)\sim(a,b)$ $(a,b)\sim(c,d) , (c,d)~(e,f): ad=bc, cf=de$ then since $b,d,f \neq 0$ we have $adf=bcf=bde$, since $ab=ba$, we have $daf=dbe$. Again, since $d \neq 0$, we have $af=be$ which means $(a,b)\sim(e,f)$. Thus, it is an equivalence relation.


1.) $(a,b) ∼ (a,b)$ since $ab = ba$

2.) $(a,b) ∼ (c,d) \Rightarrow ad = bc \Rightarrow cb = da \Rightarrow (c,d) ∼ (a,b)$

3.)$(a,b) ∼ (c,d)$ and $(c,d) ∼ (x,y) \Rightarrow ad = bc,cy =dx \Rightarrow adcy = bcdx \Rightarrow ay = bx \Rightarrow (a,b) ∼ (x,y) $


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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