$$\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

  • $\begingroup$ (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$ $\endgroup$ – Rob Bland Sep 2 '16 at 21:30
  • $\begingroup$ 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. $\endgroup$ – DonAntonio Sep 2 '16 at 21:32
  • $\begingroup$ @DonAntonio I'm guessing this was a typo on the part of the OP. $\endgroup$ – 211792 Sep 2 '16 at 21:35
  • $\begingroup$ yes was a typo error, just fixed. thanks to everyone! $\endgroup$ – Alfonse Sep 2 '16 at 21:59
  • $\begingroup$ @Alfonse, I think you will also want to change $c=2^k a$ to $c=2^p a$ ? $\endgroup$ – user326210 Sep 2 '16 at 22:19

Looks correct to me! (Except for the exponents on the right hand side of the proof for transitivity, which are probably just typos.)

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 \begin{equation} b = 2^ka \end{equation} for some $k\in\mathbf{Z}$. Can you think of an integer $l$ so that \begin{equation} a = 2^lb? \end{equation} (Hint: Remember that negative integers are integers too!) Once you have such an integer, you can conclude that $bRa$, meaning that $R$ is symmetric.

  • $\begingroup$ I totally forgot to think to "negative subset" of integers, thanks a lot! $\endgroup$ – Alfonse Sep 2 '16 at 21:55

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.