Prove that the rational numbers are countable - An alternative way There are many answers for this topic in the stackexchange forum but I would like to validate an alternative way of finding that the rational numbers are countable.
The set of rational numbers is defined as $Q = \lbrace \frac{p}{q}: p,q \in Z \rbrace$. So, each number can be writter as $p = aq + r \implies aq = p -r \implies p \equiv r (mod q)$. So, there is the set of residuals $Z_q$. There is also a set $P$ that contains the numbers corresponds to the classes of the $Z_q$. The countable sum of the $Z_q$ is the set $nZ$. We only need to prove that countable union of countable sets is a countable set.
 A: It is $7 \equiv 2 \pmod{5}$ but $\dfrac{7}{5}\not= \dfrac{2}{5}$ so for  $5$ there are more that $|\mathbb{Z}_5|$ rationals with denominator $5$ so I don't think you count all of the rationals.
After discussion: the exact definition of $P$ is that it is $\mathbb{Z}$ and every time there is $P\to \mathbb{Z}_q$ for a different $q\in\mathbb{Z}$. So in order to show that $\mathbb{Q}$ is countable it remains to be shown that countable union of countable sets is countable.
A: As mentioned above, your particular encoding may not work, but there are other ways to encode rationals as integers.
One example is to map $(p,q)$ to "$\text{length}(p)\, 0\, p\, q$".
Where $\text{length(x)}$ is simply a unary encoding of $p$ -- that is a string of 1's as long as $p$.
Then you might write

*

*$7/3$ as $1\, 0\, 7\, 3$.

*Or $100/17$ as $111\, 0\, 100\, 17$.

Since you can always recover the original fraction, the encoding is a bijection, and since it maps into the integers you have shown that the cardinality of the fractions is the same as that of the integers.
