Prove the set of all dyadic numbers is countable

Question

A number is said to be dyadic if it has the form $\frac{k}{2^n}$ for some integers $k$ and $n$ in $\mathbb Z^+ $. Show that the set of all dyadic numbers is countable.

Here is a proof I have (but couldn't complete),

Proof: Let $ M_k := \{ \frac{k}{2^n}: n \in \mathbb Z^+ \}$ for each $k \in \mathbb Z^+$

To show that $M_k$ is countable for any $k$, I tried to construct a one-to-one mapping from $M_k \to \mathbb N$. But I couldn't be sure if such a mapping is correct: $\frac{k}{2^m} \mapsto m-1$ (or while mapping is the left hand side always a single variable such as x so I have to do mapping like $x \mapsto ...$?). After mapping, I will show that the function(mapping) is one-to-one. Since $M_k$ is countable and the countable union of countable sets is countable, the set of dyadic numbers is countable.

Answer 1

Your mapping is just fine.

Notice, however, that $0 \not \in \mathbb{Z}^+$ and $0 \not \in \mathbb{N}$ and thus you do not need to have $\frac{k}{2^m}\mapsto m-1$.

Also, it is totally fine to write the mapping like you did, with

$$\frac{k}{2^m} \mapsto m$$

If it confuses you, you can also instead define a one-to-one correspondence from $\mathbb{N} \to M_k$ by

$$m \mapsto \frac{k}{2^m}$$

Answer 2

The set $\mathbb{Z}^+\times\mathbb{Z}^+$ is countable and, by definition,$$\begin{array}{ccc}\mathbb{Z}^+\times\mathbb{Z}^+&\longrightarrow&\{\text{dyadic numbers}\}\\(k,n)&\mapsto&\dfrac k{2^n}\end{array}$$is surjective. Therefore, the set of dyadic numbers is either finite or countable. But since it is infinite, it is countable.