Prove the relation $R$ in $N \times N$ defined by $(a,b) \simeq (c,d)$ iff $ad=bc$ is an equivalence relation.

Question

If $N$ is the set of all natural numbers, $R$ is a relation on $N \times N$, defined by $(a,b) \simeq (c,d)$ iff $ad=bc$, how can I prove that $R$ is an equivalence relation ?

Answer 1

Hint:

You need to prove that $R$ is reflexive, symmetric and transitive.

I leave the first two to you. They are very straight forward.

Now suppose $(a,b) \simeq (c,d)$ and $(c,d) \simeq (e,f)$

Then $ad = bc$ and $cf=de$

Thus

$(ad)(cf)=(bc)(de)$

and by cancelling from both sides

$af=be$

Accordingly $(a,b) \simeq (e,f)$ and $R$ is transitive.

Answer 2

Hint: To prove that this is an equivalence relation, you must prove reflexivity, symmetry, and transitivity. Each of these is a different statement that you must prove.

• Reflexivity: Suppose that $(a,b)\in\mathbb{N}\times\mathbb{N}$. Then, you want to prove that $(a,b)R(a,b)$. This can get a little confusing because sometimes a relation is written as a pair - so students sometimes consider the case where $a=b$, i.e., $(a,a)$. If you want to write a relation in terms of a pair, you would write $((a,b),(a,b))$.

• Symmetry: Suppose that $(a,b),(c,d)\in\mathbb{N}\times\mathbb{N}$ such that $(a,b)R(c,d)$ (so $ad=bc$). Now, you would like to prove $(c,d)R(a,b)$, in other words that $cb=da$. This can get a little confusing because students sometimes try to look at symmetry of $(a,b)$, in other words, look at $(b,a)$. Since the objects are in $\mathbb{N}\times\mathbb{N}$, you want to reverse the two elements of $\mathbb{N}\times\mathbb{N}$.

• Transitivity: Suppose that $(a,b),(c,d),(e,f)\in\mathbb{N}\times\mathbb{N}$ such that $(a,b)R(c,d)$ and $(c,d)R(e,f)$; in other words, you know that $ad=bc$ and $cf=de$. You would like to prove $(a,b)R(e,f)$, in other words, that $af=be$. If you manipulate $ab=bc$ by multiplying both sides by $f$, you get the desired $(af)b$ on the LHS. Now, use the other equality on the RBS and divide by $b$ (is $b\not=0$!?)

Answer 3

Let's do it step by step:

$$\forall (a,b)\in \Bbb{N}\times \Bbb{N}^{*},\, ab=ab$$

So $(a,b)\mathcal{R}(a,b)$ and $\mathcal{R}$ is reflexive.

Assume now that $(a,b)\mathcal{R}(c,d)$ i.e $ad=bc$. Multiplication is commutative so we can write $cb=da$ and this gives $(c,d)\mathcal{R}(a,b)$. The relation is symmetric

Now take $(a,b)\mathcal{R}(c,d)$ and $(c,d)\mathcal{R}(e,f)$ ; this means $ad=bc$ and $cf=de$. Multiply the first equality by $f\neq 0$ to get $afd=bcf$ and the second by $b\neq 0$ to get $bcf=bed$. So we have $afd=bed$ and keeping in mind $d\neq 0$ we have $af=be$ i.e $(a,b)\mathcal{R}(e,f)$ and the relation is transitive

It is therefore an equivalence relation