The relation $R$ defined on $\mathbb{Z}$ by $aRb$ if and only if $a=(2^n)b$ prove/disprove symmetry, transitive and reflexive

Question

The relation $\mathbf R$ defined on $\mathbb Z$ by $a\mathbf{R} b$ if and only if $\exists n, a=(2^n)b$

prove/disprove symmetry

prove/disprove transitive

prove/disprove reflexive

This was a question I had on my math test previously and it is driving me crazy. I was trying to use an induction proof but couldn't figure out what to put as my base case.

Answer 1

This is an order relation. It is transitive and reflexive, but asymmetric.

• Transitive since if $a=(2^n)b$ and $b=(2^m)c$ then $a=(2^{n+m})c$
• Reflexive since $a=2^0a$
• Assymetric since if $a=(2^n)b\wedge b=(2^m)a$ then $a=(2^{n+m})a$ so $n=m=0$ and therefore $a=b$

Answer 2

Is $n \in \mathbb Z$? Or is $n \in \mathbb N$? And is $0 \in \mathbb N$.

If it must be $n\in \mathbb Z$:

$a = b2^n \iff b = a2^{-n}$ so $aRb \iff bRa$ so symmetric

But if $n$ must be be $n\in \mathbb N$ then

$a = b2^n \iff b = a2^{-n}$ but $n, -n \in \mathbb N$ only if $n =0$ and if $0 \in \mathbb Z$. In that case $a=b$ and $R$ is not symmetric. In fact it is anti-symmetric.

If $n\in \mathbb R$ is the only restriction it is symmetric by the first argument. But notice that it will always be the case that $aRb$ if i) $a,b$ both positive. (Because $a = b2^{\log_2 \frac ab}$) ii) $a,b$ both negative (same reason) iii) $a = b =0$. Making this a very simple relation: $a Rb$ if and only if $a,b$ are either both positive, or both negative, or both $0$.

.....

I will assume the assumption is that $n \in \mathbb N$ and that $n$ may be $0$. That just seems to be the standard.

So I'll say $R$ is not symmetric.

.....

Transitive. If $a R b$ and $bRc$ then $a = 2^nb$ and $b= c2^{m}$ and $a = 2^{n+m}c$. So $a R c$. So transitive.

Reflexive. If $a = a*2^m$ either $a=0$ or $m= 0$. So if $0$ is an acceptable value for $n$ then for every possible $a \in \mathbb Z$, $aRa$ so it is reflexive.

If however $0$ is not an acceptable value of $n$ then it is not reflexive.