Consider the relations R and S on $\Bbb N$ defined by $x\; R\; y$ iff

$2 \;$divides $x + y$ and $x \;S \;y$ iff $3$ divides $x + y.$

$\text{QN: Prove that $R$ is an equivalence Relation }$

So my question for this one is that I understand how one is able to prove that it is reflexive and symmetric. But I am struggling to figure out how to prove that it is transitive. I cannot seem to grasp that concept.

$x+y = 2a \Rightarrow x+y = 3a$

$(i)$ $xRx$ , then $2$ divides $x+x = 2x$, therefore reflexive.

$(ii)$ If $xRy$ $2$ divides $x+y$, $2$ divides $y+x$ ,$yRx$. Thus Symmetric.

  • $\begingroup$ Do you mean $2$ divides $y+x$ in (ii)? $\endgroup$ – Zain Patel Jul 8 '16 at 17:09
  • $\begingroup$ It is worth mentioning that $R$ will indeed be an equivalence relation, but $S$ will not. For you to think about: why isn't $S$ an equivalence relation? Which property or properties will fail for $S$? $\endgroup$ – JMoravitz Jul 8 '16 at 17:17
  • $\begingroup$ I made that a separate question as it would be unfair to ask two questions for one problem. $\endgroup$ – Jon Jul 8 '16 at 17:19

For transitivity, like so:

$xRy$, so $2$ divides $x+y$

$yRz$, so $2$ divides $y+z$

Now add the two together, you know that $2$ has to divide the sum, so $2$ divides $x + y + y + z = x + z + 2y$.

But since $2 | 2y$ and $2 | (x + z + 2y)$ then $2$ must divide $x + z$, hence $xRz$.

  • $\begingroup$ How come you have to two y's but only one x? $\endgroup$ – Jon Jul 8 '16 at 17:37
  • 1
    $\begingroup$ Because, if $2$ divides $a$ and $2$ divides $b$, then $2$ divides $a + b$. Here $a = x + y$ and $b = y + z$, so $a + b = x + y + y + z = x + 2y + z$. The intuitive way to think about this is that we know that $x$ is connected to $y$, and $y$ is connected to $z$. We want to show that $x$ is connected to $z$ via the connection of $y,$ which is why the 'boundary' $y$ has a different role, i.e: there are two $y$'s and one $x$. $\endgroup$ – Zain Patel Jul 8 '16 at 17:39

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.