# Showing that ~ is an equivalence relation

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!

## Reflexive

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

$\therefore n \sim n$

## Symmetric

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

## Transitive

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

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

• Thank you for the thorough reply! – 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$$