The Rationals Are Countable: Euclid's Proof

Article: The Rationals Are Coutable: Euclid's Proof by Jery Czyz and William Self in The College Mathematics Journal

# Article Summary

From the time that we leave high school, we all at least know the difference between a rational number and a natural number. A rational number being a number that can be expressed as a ratio of two integers. In mathematics, we have come to denote a set of all rational number as $\mathbb{Q}$. A natural number, denoted as $\mathbb{N}$, is considered the "counting number." Yet, people everywhere know that rational numbers can be counted and according to Czyz and Self there are numerous proofs that show this fact. The only problem with these proofs, according to the authors, is that they do not show "an explicit one-to-one correspondence from the natural numbers to the set of rationals." One example of this is this one-to-one correspondence between $\mathbb{Q}$ and $\mathbb{N}$is:

(1)
\begin{align} N\leftrightarrow n+\frac{(n+m)(n+m-1)}{2} \end{align}

The authors provide us with the first few numbers of this correspondence:

$\mathbb{N}$ $n/m$
0 0/1
1 0/2
2 1/1
3 0/3
4 1/2
5 2/1

From looking at the table from above, the authors point out the disadvantage of using this type of correspondece because it presents 0 infinitely often. The purpose of this article is to show us how to use continued fractions in order to create an enumeration of the nonnegative rationals that will allow us to calculate the $n$th positive rational without having to calculate any of the rationals that come earlier in our list. We will look at this proof in the "Connection to Real Analysis" section of the review.

# Connection to Real Analysis

The authors call this "Euclid's proof" after the Greek mathematician who is known as "The Father of Geometry." They named this proof after Euclid because this proof is based off of Euclid's algorithm for finding the greatest common divisor.

$\mathbf{Euclid's Proof}$
The basic way that Euclid's Proof works is to consider a randomly chosen rational number such as $50/23$. We first divide 23 into 50 in order to get a quotient of 2 and remainder 4.

(2)
\begin{align} \frac{50}{23}=2+\frac{4}{23} \end{align}

We can then write the right hand side of equation 2 into the form of a continued fraction:

(3)
\begin{align} 2+\frac{4}{23} \longrightarrow 2+\frac{1}{\frac{23}{4}} \end{align}

Next we can divide 23 by 4 to get a quotient of 5 and remainder 4:

(4)
\begin{align} 2+\frac{1}{\frac{23}{4}}=2+\frac{1}{5+\frac{3}{4}} \end{align}

Because $\frac{3}{4}=\frac{1}{\frac{4}{3}}$, we can keep dividing our demoninator and writing our continued fraction:

(5)
\begin{align} 2+\frac{1}{5+\frac{3}{4}}=2+\frac{1}{5+\frac{1}{1+\frac{1}{3}}} \end{align}

This process of forcing the demoninator into a continued fraction can continue until the last demoninator in the continued fraction is equal to 1. This is because every positive rational except 1 has two representations. We also know that this algorithm must terminate because its remainders must form a decreasing sequence.
Based on the above statement, we can go one more step futher and write:

(6)
\begin{align} 2+\frac{1}{5+\frac{1}{1+\frac{1}{3}}}=2+\frac{1}{5+\frac{1}{1+\frac{1}{2+\frac{1}{1}}}} \end{align}

Hence, each nonnegative rational number has a terminating continued fraction which can be written in the form:

(7)
\begin{align} a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{...\frac{1}{a_n}}}} \end{align}

Where $a_0$ is a nonnegative integer, $a_k$ is a positive integer for $k\geq 1$, and $a_n>1$ provided that $n>0$. By using the above requirements, we have shown that the continued fraction expansion of any nonnegative rational can be uniquely determined.

By using Euclid's Proof, we can now easily enumerate the nonnegative rationals to the $n$th degree without having to calculate any rationals that come before $n$. We will begin by enumerating the set of all finite sequences of positive integers, {$a_0,a_1,a_2,...,a_n$}.

$\mathbf{Example}$

Let $n\in\mathbb{N}$ and create the binary expansion of $n$. If $n=194$, then the binary expansion of $n$ is {1,1,0,0,0,0,1,0}. We will drop the first digit, thus making the new binary sequence {1,0,0,0,1,0}. By making our sequence this way, we have found a way to produce all possible finite sequences of zeros and ones since $n$ varies over the natural numbers.

Let $k$ denote the number of digits in the new sequence. From our example when $n=194$, $k=7$. Image $k+1$ dots arranged in a row, seperated only by the digits of the sequence. Our example would look like this: {$\boxdot1\boxdot0\boxdot0\boxdot0\boxdot0\boxdot1\boxdot0\boxdot$}. Note: if you have an empty sequence, that would produce a single dot.

Now erase all of the 0's and pretend that the remaining 1's are dividing lines. By doing this, our example will now look like:
{$\boxdot1\boxdot\boxdot\boxdot\boxdot\boxdot1\boxdot\boxdot$}. Counting the number of dots in each bunch will give us a finite sequence of positive integers. From our example, our sequence would be {$1,5,2$}. But before we can converte this sequence into continued fractions, two adjustments must be made. First, we must subtract 1 from the first number in the sequence because we must allow for the possiblity that $a_0=0$. Second, we have to guarantee that the last term is greater than 1, so we must add 1 to the last term. This will allow us to force the denominator until the last denominator is equal to 1. Our sequence is now {$0,5,3$}.

After these adjustments, we can now create a continued fraction from this sequence. Our example will yield us:

(8)
\begin{align} 0+\frac{1}{5+\frac{1}{3}} \end{align}

which is the rational number 3/16. It should be noted that only one integer $n$ can produce any particular sequence thus meaning that $n$ will have a particular rational number.