0

Let $R$ be the relation on $N\times (N\setminus\{0\})$ defined by $((a, b),(c, d)) \in R$ if $ad = bc$. Prove that $R$ is an equivalence relation.

I'm pretty confused with this problem, mainly because I don't understand the significance of $(N\setminus\{0\})$. Any ideas on how to solve this?

Yoka Swag
  • 66
cheslea520
  • 1
  • This happens to be the same equivalence relation used to say that two rational numbers are equal. $\frac{a}{b}=\frac{c}{d}$ iff $ad=bc$. Remember that a fraction $\frac{a}{b}$ cannot have $b=0$ (though $a$ is allowed to be zero). If we were to try to define the equivalence relation on $\Bbb N\times \Bbb N$ instead, something fails. – JMoravitz Jul 25 '16 at 18:59
  • The significance of $\Bbb N\setminus {0}$ is that $(a,b)$ is meant to represent the fraction $\frac{a}{b}\in \Bbb Q$. The resulting equivalence classes consist of fractions with the same value, but are simplified / expanded versions of one another (so $(3,4)$ is related to $(6,8)$). If we used $\Bbb N\times \Bbb N$, then every pair $(a,b)$ would be related to $(0,0)$, and transitivity would fail. – Arthur Jul 25 '16 at 19:00
  • Trying to define the same relation on $\Bbb N\times N$ one has $(0,1)\simeq (0,0)$ and $(0,0)\simeq (1,0)$ however $(0,1)\not\simeq (1,0)$. That is because $0\cdot 0 = 1\cdot 0$ as well as $0\cdot 0 = 0\cdot 1$ however $0\cdot 0\neq 1\cdot 1$. Thus on $\Bbb N\times \Bbb N$ the relation is not transitive. (This is in analogy with how we say $\frac{0}{0}$ is an indeterminate form, it is able to be "equal" to anything) – JMoravitz Jul 25 '16 at 19:02
  • @Arthur does that mean that (c,d) is a fraction, as well? – cheslea520 Jul 25 '16 at 19:03
  • Yes, it's the fraction $\frac cd$. – Arthur Jul 25 '16 at 19:05
  • Part of the point of the exercise is to treat them as the objects they are, not just as the objects they resemble. Use your definitions to show that $R$ is an equivalence relation, that is $R$ is reflexive (show that every pair $(a,b)$ is related to itself), that $R$ is symmetric (If $(a,b)$ is related to $(c,d)$, show that $(c,d)$ is related to $(a,b)$) and that $R$ is transitive (if $(a,b)$ is related to $(c,d)$ and $(c,d)$ is related to $(e,f)$ then show that $(a,b)$ is related to $(e,f)$) – JMoravitz Jul 25 '16 at 19:10

1 Answers1

0

There are 3 things you need to show:

$x\equiv x$ (reflexivity) i.e. $(a,b)\equiv (a,b) \implies ab = ab$ which is true for all $(a,b)$

$x\equiv y \implies y\equiv x$ (symmetry) I am going to leave this and the next one to you.

$x\equiv y,y\equiv z \implies x\equiv z$ (transitivity)

You can just grind through the algebra with little concern what the eqivalence relation actually implies.

However, it might help your intuition if you notice that:

$\frac ab = \frac cd \implies ad = bc$

And then it will make some more sense why $b,d$ cannot equal $0.$

Regardless, it is the same steps to prove the equivalence relation.

Doug M
  • 57,877