# Proving the countability of the rational numbers

I'm having a hard time with the very-last proof I'm supposed to make:

Prove that the set of rational numbers is countable by setting up a function that assigns to a rational number $\textbf{p/q}$ with $\textbf{gcd(p,q)=1}$ the base $\textbf{11}$ number formed by the decimal representation of $\textbf{p}$ followed by the base $\textbf{11}$ digit $\textbf{A}$, which corresponds to the decimal number $\textbf{10}$, followed by the decimal representation of $\textbf{q}$.

Any help would be kindly appreciated.

Thanks.

-
The function is described by a recipe. Have you applied the recipe to, for instance, the rational numbers between $0$ and $1/2$ with denominator less than $20$? Do you see why different rational numbers give different (integer) results? Do you recognize that the recipe does indeed describe a function from the (positive) rationals to the positive integers, far from onto, but definitely one-to-one? Do you see that the existence of such a function guarantees the countability of the rationals? –  Lubin Jan 2 '12 at 5:59
Your questions are helping me in understanding, thanks. –  John Smith Jan 2 '12 at 6:24

Well you know that the natural numbers are countable (by definition), and you should also know that they can be written uniquely in base 11 using the digits $0,1,2,3,4,5,6,7,8,9,A$. In order to prove that $\mathbb{Q}$ is countable, you want a function $f: \mathbb{N}\to \mathbb{Q}$ which is surjective (meaning that every element of $\mathbb{Q}$ is the image of some element of $\mathbb{N}$). What the problem wants you to do is construct $f$ by setting $$f(x_1x_2\cdots x_nAy_1y_2\cdots y_m) = \frac{x_1x_2\cdots x_n}{y_1y_2\cdots y_m}$$ where $x_1,x_2,\ldots,A,y_1,y_2,\ldots,y_m$ are the base 11 digits of the natural number and the right-hand side is interpreted as fraction of base 10 natural numbers with digits $x_1,x_2,\ldots,x_n$ and $y_1,y_2,\ldots,y_m$. Any positive rational number can be written this way, so all you need to do is modify the function slightly to get the negative rational numbers as well, which shouldn't be too hard. A caution though: as defined right now, $f$ is not a function, as not all natural numbers take the form $x_1x_2\cdots x_nAy_1y_2\cdots y_m$ in base 11. In order to make it a function, you need to pick some element of $\mathbb{Q}$ as the value of $f(n)$ for natural numbers $n$ which do not take this form. It doesn't matter which element you pick though.