1
$\begingroup$

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.

  • 0
    Your questions are helping me in understanding, thanks.2012-01-02

2 Answers 2

1

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.

  • 0
    I think I'm understanding, almost there. Thank you.2012-01-02
0

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.