Define a relation ~ on N whereby a~b if and only if there exists $\displaystyle k \in Z$ such that $\displaystyle \frac{a}{b} = 2^k$.

(a) Prove that ~ is an equivalence relation.

(b) Write out the equivalence classes for ~ on the set {1,2,3,....10}

Here's my attempt at part (a):

To show that ~ is an equivalence relation, I must show that it's reflexive,symmetric and transitive:

* ~ is reflexive $\displaystyle \Longleftrightarrow$ a~a $\displaystyle \forall a \in Z$

$\displaystyle \Longleftrightarrow \frac{a}{a} = 2^k$

But we know: $\displaystyle \frac{a}{a} = 1$, well I'm sort of stuck here and I don't know how to conclude that ~ is reflexive...

* ~ is symmetric $\displaystyle \Longleftrightarrow$ a~b $\displaystyle \Rightarrow$ b~a

$\displaystyle \Longleftrightarrow \frac{a}{b} = 2^k \Rightarrow \frac{b}{a} = 2^k$

We can suppose $\displaystyle \frac{a}{b} = 2^k$ and then try to show that $\displaystyle \frac{b}{a} = 2^k$ but I don't know how to do it...

* ~ is transitive if and only if a~b $\displaystyle \wedge$ b~c $\displaystyle \Rightarrow$ a~c

$\displaystyle \Longleftrightarrow$ $\displaystyle \frac{a}{b}=2^k \wedge \frac{b}{c} = 2^k \Rightarrow \frac{a}{c} = 2^k$

Suppose $\displaystyle \frac{a}{b}=2^k \wedge \frac{b}{c} = 2^k$ then:

$\displaystyle \frac{a}{c} = \frac{a}{b} + \frac{b}{c}$ $\displaystyle = 2^k + 2^k = 2^{2k} = 4.2^k$

I'm not sure how to continue this part either... any help with this problem is greatly appreciated.