Enumerating the Rationals

As a brief excursion, here is a standard technique for enumerating a collection. We used this technique in Trapping a Transcendental to enumerate the algebraic numbers.

We start with an inspiration, and define the "mass" of an item. The objective is that for each mass there are only finitely many objects of that mass, but every item has a finite mass. Then if we list all the items of mass 1, 2, 3, and so on, the everything will eventually get listed.

With the algebraic numbers the "mass" was derived from the polynomial for which the algrabraic was a root. Here, as we enumerate the rationals, we choose a different definition.

Let's see it in action ...

We start by deciding on a canonical representation for each rational point on the number line. In particular, given a rational point on the number line we'll choose always to use a fraction with a positive denominator, and where the numerator and denominator do not share a common factor other than 1 (or -1).

Specifically, we don't use the representation 3/6, or 3/-7, but instead we will use 1/2 and -3/7. The points designated are, of course, the same, but it means that for every rational point, there is a single, specific way of writing it.

Now we define the concept of the "mass" of a fraction. This is where we need some inspiration. We choose to define the mass of a fraction a/b to be abs(a)+b. Thus the mass of 1/2 is 3, and the mass of -3/7 is 10. Since the denominator is strictly positive, the mass of a fraction must be strictly positive.

So we want to check that for any given mass there are only finitely many fractions, and that every fraction has a finite mass.

We'll start by writing down all the fractions with mass 1.

Since the denominator must be greater than 0, it can only be 1, and so the numerator must be 0. The only fraction of mass 1 is 0/1.

What about mass 2? The denominator can apparently be 1 or 2, but with denominator 2 the numerator has to be 0, and that's not a valid representation because 0 and 2 have a common factor of 2. So the denominator must be 1, and the numerator can be 1 or -1. So our fractions of mass 2 are -1/1 and 1/1.

And so we proceed:

We can now list the fractions:

and so on. Each fraction will appear, and for each fraction, if we choose, we can even give a limit as to when it must appear by.

The definition of the mass means that we can only have a finite number of fractions for a given mass, and clearly each fraction is given a finite mass, so we can simply write down all the fractions in order of mass, and for those of the same mass, in order of size.

Thus we can number off the fractions.

We can enumerate the fractions.