A New Proof That the Rationals Are Countable

The proof below that is due to K. B. Subramaniam has been published in The Mathematical Gazette. I reproduce it practically verbatim.

Let $\mathbb{Q}^{*}$ be the set of positive factions expressed in their lowest terms. For $\displaystyle x=\frac{N}{D}\in\mathbb{Q}^{*},$ let $n$ and $d$ be the number of digits in $N$ and $D$ respectively. Define the function $: \mathbb{Q}^{*} \rightarrow \mathbb{N}$ by

$\displaystyle f(x)= \begin{cases} 10^{n}N+D,&d\le n\\ 10^{2d}+10^{d}N+d,&d\gt n. \end{cases}$

Here's a few examples:

$\displaystyle\frac{12345}{7} = 1234500007;\,$ $\displaystyle\frac{1234}{57} = 12340057;\,$ $\displaystyle\frac{123}{457} = 123457;\,$

$\displaystyle\frac{12}{3457} = 100123457;\,$ $\displaystyle\frac{1}{23457} = 10000123457.$

From the definition, it is clear that if $d\le n,$ $f(x)$ has an even number of digits, and if $d \gt n,$ $f(x)$ has an odd number of digits and has a leading digit of $1.$ Suppose, then, that we are given a number $k \in f(\mathbb{Q}^{*}).$ Then there is one and only one \mathbb{Q}^{*}$x\in\mathbb{Q}^{*}$ such that $k = f(x).$ Two cases are possible:

$k$ has an even number $2n$ of digits. Then $k = 10^{n}N + D,$ so $N$ and $D$ are uniquely determined.
$k$ has an odd number $2d+1$ of digits digits and its leading digit is $1.$ Then $k-10^{2d}=10^{d}N+D$ so that $N$ and $D$ are uniquely determined.

Hence $f$ is an injective (but not surjective) function. This shows that $\mathbb{Q}^{*}$ is countable, and it is now easy to show that $\mathbb{Q}$ is also countable.

Note that the if we defined $g(x) = 1O^{d}N + D,$ $g$ would not be injective, since then $g$ would take the value $123457$ for all the rationals considered earlier. Note also that, since $f$ is not surjective, we are not able to find $x,$ with $f(x)=k$ for an arbitrary $k\in\mathbb{N}.$ For example, for $k=124134,$ the above procedure results in $\displaystyle\frac{124}{134}$ which, not being in lowest terms, is not in $\mathbb{Q}^{*}.$

References

K. B. Subramaniam, A new proof that the rationals are countable, The Mathematical Gazette 98, n 542, July 2014, 345

Countability of Rational Numbers

Counting Ordered Pairs
Countable Times Countable Is Countable
Countability of Rational Numbers
Countability of Rational Numbers: PWW
Countability Principle
Countability of Rational Numbers via Conitnued Fractions
Fractions on a Binary Tree II
Countability of Rational Numbers as a Union of Finite Sets
A New Proof That the Rationals Are Countable

71239618