Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.


share|improve this question
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
add comment

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
I think I'm understanding, almost there. Thank you. –  John Smith Jan 2 '12 at 6:25
add comment

The hint given is pretty much the entire solution. You only need to notice that the function described is natural-valued and injective, thus the cardinality of (positive) rationals is no greater than that of naturals. The converse is obvious, which, along with an application of the Cantor-Bernstein-Schroeder theorem, yields the result for positive rationals. The fact that positive rationals and all rationals are equinumerous should be fairly clear.

Note that the assumption that the fraction is irreducible is inessential -- the proof given works just as well to prove that there are as many pairs of natural numbers as there are natural numbers.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.