Bijection from $\mathbb{N}$ to set of equivalence class

Question

If I have an equivalence relation ~ where $x ∼ y$ if $x = 2^{k}y$ or $y = 2^{k}x$

How would I show that there is a bijection $f : \mathbb{N} \rightarrow \mathbb{N}/\sim$

where $\mathbb{N}/\sim$ is the set of equivalence classes of $\sim$?

Answer 1

If $n$ is odd, then the equivalence class of $n$ wrt. $\sim$ is

$$|n| = \{ 2^k n \mid k \geq 0 \}$$

Note that for any odd $n_1, n_2$ where $n_1 \neq n_2$ we have that $|n_1| \cap |n_2| = \emptyset$, so all the equivalence classes generated by odd numbers are pairwise distinct. This shows that there are countably many equivalence classes $C_1, C_2, C_3 \ldots$. In fact, there can be no other equivalence classes.

For if $n$ is even, it is of the form $2^k n_1$, where $n_1$ is odd, and we then have

$$|n| = |n_1|$$.

The desired bijection is therefore $$i \mapsto C_i \text{ for } i \in \mathbb{N}.$$

Answer 2

Suppose $x\in\mathbb N$ and let $[x]$ denote the equivalence class of $\sim$ which contains $x$, then $$\mathbb N/\sim\ =\ \{\ [0],[n]\mid n=2m+1,\ m\in\mathbb N\ \}.$$ Now, we can construct a bijection$\ \ f:\mathbb N\to\mathbb N/\sim$ as the following $$f(x)=\left\{\begin{matrix}\ \ [0]\ \ \ \,\quad\text{if $\ x=0$}\\ [2x-1]\ \ \ \text{otherwise}\end{matrix}\right..$$