Prove transitivity of relation $R=\{(a,b) \in Z \times Z | \exists m,n \in N\setminus\{0\}: a^m = b^n \}$

Question

Transitivity means: $(a,b) \in R \quad \land \quad (b,c) \in R \quad \implies (a,c) \in R$

But I'm not really sure how to go about it. I know that there is some $s,t,v,u$ such that $a^s = b^t$ and $b^v = c^u$ but to prove transitivity of the relation I'd have to find some $x,y$ such that $a^x = c^y$.

Anyone have a pointer?

score 2 · Accepted Answer · answered Oct 12 '16 at 01:24

2

HINT: If $a^s=b^t$, then $a^{sv}=(a^s)^v=(b^t)^v=b^{tv}=(b^v)^t=\ldots$

answered Oct 12 '16 at 01:24

Brian M. Scott

616,228

$ ... = (c^u)^t = c^{ut} $ – user3340459 Oct 12 '16 at 01:31
@user3340459: Exactly — and that does what you need, since the product of positive integers is a positive integers. – Brian M. Scott Oct 12 '16 at 01:32
Certainly, that's what I was trying to say. I just wanted to have the solution completed in the post here, too, just in case (unlikely) that anyone runs into this again. Quite remarkable that sometimes one gets stuck with the simplest of problems. Thank you very much. – user3340459 Oct 12 '16 at 01:35
@user3340459: You’re very welcome. – Brian M. Scott Oct 12 '16 at 01:36

Prove transitivity of relation $R=\{(a,b) \in Z \times Z | \exists m,n \in N\setminus\{0\}: a^m = b^n \}$

1 Answers1