# prove that $R$ is an equivalence relation

$$\forall a,b \in \mathbb{Q} \quad aRb \Leftrightarrow \quad \exists k \in \mathbb{Z}: \quad b=2^ka$$ 1) Reflexivity:

$\forall a \in \mathbb{Q}\quad aRa \Leftrightarrow \quad \exists k \in \mathbb{Z}: \quad a=2^ka$

choosing $k=0 \quad \Rightarrow a=2^0a=a \Rightarrow aRa \Rightarrow R \text{ is reflexive}$

2) Symmetry

3) Transitivity:

$\forall a,b,c \in \mathbb{Q}:$ $$aRb \Leftrightarrow \quad \exists k \in \mathbb{Z}: \quad b=2^ka$$ $$bRc \Leftrightarrow \quad \exists h \in \mathbb{Z}: \quad c=2^hb$$ Then $$aRc \Leftrightarrow \quad \exists p \in \mathbb{Z}: \quad c=2^pa$$

so $aRb,bRc \Rightarrow c=2^hb=2^h2^ka=2^{h+k}a$

choosing $p=k+h \Rightarrow c=2^pa \Rightarrow aRc \Rightarrow \text{ R is transitive}$

Can anyone confirm that 1) and 3) are correct? I tried to prove 2) but is ended like transitive proof and I think that is entirely wrong, I have no idea how to succeed, can anyone provide some hints/proof/solution?. thanks in advance

• (1) and (3) look correct to me. Also, for the symmetric proof, note that $aRb \to b = 2^k a \to a = 2^{-k}b$, also note that if $k$ is an integer, then $-k$ is also an integer, and therefore $aRb \to bRa$ – Rob Bland Sep 2 '16 at 21:30
• In (3) you don't necessarily have the same $\;k\in\Bbb Z\;$ for both cases. Yet afterwards you uszxe $\;h,k\;$ so it is fine. – DonAntonio Sep 2 '16 at 21:32
• @DonAntonio I'm guessing this was a typo on the part of the OP. – 211792 Sep 2 '16 at 21:35
• yes was a typo error, just fixed. thanks to everyone! – Alfonse Sep 2 '16 at 21:59
• @Alfonse, I think you will also want to change $c=2^k a$ to $c=2^p a$ ? – user326210 Sep 2 '16 at 22:19

For symmetry, note that if $a R b$, then there is some $k$ for which $b = 2^k a$. But then $a = 2^{-k} b$; hence $b R a$. (Indeed, there exists an $\ell \equiv -k$ for which $a = 2^\ell b$.)
Your proofs for parts (1) and (3) are correct. For symmetry, suppose $aRb$, so that $$b = 2^ka$$ for some $k\in\mathbf{Z}$. Can you think of an integer $l$ so that $$a = 2^lb?$$ (Hint: Remember that negative integers are integers too!) Once you have such an integer, you can conclude that $bRa$, meaning that $R$ is symmetric.