1

Show that $R=\{(x,y) \in\mathbb{N}^2:\exists m,n \in \mathbb{N} \text{ s.t. } x^m=y^n\}$ is an equivalence relation or disprove otherwise

Reflexivity and symmetricity were really easy to show but how do I show that it's transitive?

Let $(a,b),(b,c)\in R$, so $a^m=b^n$ and $b^{m'}=c^{n'}$, how can I show that $a^{m''}=c^{n''}$?

user239268
  • 13
  • If you take $c^{n'}$ to the power of $n$ then you get $b^{m'n} = \left(b^n\right)^{m'}$. How does this relate to $a$ and $c$, given your assumptions. – Dead-End May 09 '15 at 22:48
  • 1
    That there are natural numbers $m, n$ such that $x^m = y^n$ means exactly the same as the fact that there is a positive, rational number $q$ such that $x^q = y$. I think transitivity is a bit easier to show there. – Arthur May 09 '15 at 22:55
  • Do you mean to allow $m=n=0$? After all, that means $R=\mathbb{N}^2$! – PJTraill May 13 '15 at 22:13

2 Answers2

2

In your notation, try $m'' = mm'$ and $n'' = nn'$.

Lukas Betz
  • 4,506
  • 1
    $$a^{m''} = a^{mm'} = (a^m)^{m'} = (b^n)^{m'} = (b^{m'})^n = (c^{n'})^n = c^{nn'} = c^{n''}$$ – Arthur May 09 '15 at 22:57
1

Let $a^m = b^n$ and $b^x = c^y$.
Then $(a^m)^x = (b^n)^x$ and $(b^x)^n = (c^y)^n$.
We have $a^{mx} = b^{nx} = c^{yn} \implies a^{mx} = c^{yn}$

rackne
  • 307