When defined on the set $N_1=\{1,2,3,\cdots\}$ of positive integers a relation $\sim$ such that two positive integers $x$ and $y$ satisfy $x\sim y$ if and only if $x/y=2^k$ for some integer $k$, show that $\sim$ is an equivalence relation.

How do I approach proving that the relation holds? I understand that I need to prove that it is reflexive, symmetric, and transitive, but I don't entirely understand how to prove each case!



$\forall n \in N_1: \dfrac nn = 1 = 2^0$

$\therefore n \sim n$


$\forall x,y \in N_1: x \sim y \implies \dfrac xy = 2^k \implies \dfrac yx = 2^{-k} \implies y \sim x$


$\forall x,y,z \in N_1: x \sim y \land y \sim z \implies \dfrac xy = 2^m \land \dfrac yz = 2^n \implies \dfrac xz = 2^{m+n} \implies x \sim z$

  • $\begingroup$ Awesome! Thank you for the timely reply! How come k=0 when proving that the equivalence is reflexive? $\endgroup$ – Christopher Kornosky Apr 19 '17 at 5:27
  • $\begingroup$ What else if not 0? $\endgroup$ – DHMO Apr 19 '17 at 5:29
  • $\begingroup$ I dunno! I thought it had to be $2^n$, but evidently I still don't fully understand the implementation of the concept. $\endgroup$ – Christopher Kornosky Apr 19 '17 at 5:36
  • $\begingroup$ Is 0 an integer? $\endgroup$ – DHMO Apr 19 '17 at 5:39
  • $\begingroup$ ... Yeah... I guess it is. Oh... I see now... You're a good teacher. Subtle, but to the point, I like it. $\endgroup$ – Christopher Kornosky Apr 19 '17 at 5:46

Reflexive: $x \sim x$ since $x/x=1=2^0$.

Symmetric: $x \sim y$ means $x/y = 2^k$ for some k, so y/x = (x/y)^{-1} = 2^{-k}.

Transitive: $x \sim y$ means $x/y = 2^k$, while $y \sim z$ means $y/z = 2^n$, together you'll find \begin{align*} \frac{x}{z} &= \frac{x}{y} \cdot \frac{y}{z} \\ &= 2^k \cdot 2^n \\ &= 2^{k+n} \end{align*}

  • $\begingroup$ Thank you for the thorough reply! $\endgroup$ – Christopher Kornosky Apr 19 '17 at 5:27

If $f$ denotes some function that has $N_1$ as its domain then evidently we have:

  • $f(n)=f(n)$ for all $n\in N_1$
  • $f(n)=f(m)\implies f(m)=f(n)$ for all $n,m\in N_1$
  • $f(n)=f(m)\wedge f(m)=f(k)\implies f(n)=f(k)$ for all $n,m,k\in N_1$

This means exactly that the relation $\sim$ defined by $n\sim m\iff f(n)=f(m)$ is reflexive, symmetric and transitive, hence is an equivalence relation.

Now observe that the relation mentioned in your question can be prescribed like that if function $f$ is prescribed by: $$n\mapsto\text{largest odd divisor of }n$$


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.