1
$\begingroup$

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.

$\endgroup$

5 Answers 5

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .