Enumerating the Rational Numbers

From Fractions to a List

A rational number has a representation \(p/q\), where \(p\) is an integer and \(q\) is a positive integer. There are infinitely many such pairs, and a rational usually has more than one representation: \(1/2=2/4=3/6\). To enumerate the rationals, we need a systematic order for the pairs and a rule that prevents repeated values from appearing in the final list.

Throughout, \(\mathbb{N}=\{1,2,\dots\}\). A set is countably infinite if there is a bijection from \(\mathbb{N}\) to that set. We will organize pairs \((p,q)\in\mathbb{Z}\times\mathbb{N}\) into finite blocks according to the integer \(h=|p|+q\), called the height of the pair. Within each block, order the pairs by increasing \(p\).

For any fixed height \(h\), the denominator is determined by the numerator: \(q=h-|p|\). The condition \(q\ge1\) restricts \(p\) to the finite range \(-h+1\le p\le h-1\). Thus each height gives a finite block, and scanning heights \(1,2,3,\ldots\) visits every pair. For example, the block of height \(3\) consists of \((-2,1),(-1,2),(0,3),(1,2),(2,1)\).

Scanning Pairs and Removing Repetitions

Replace each pair \((p,q)\) by the rational \(p/q\). Scan the blocks in order, retaining a value only the first time it appears. Equality can be checked exactly: \(p/q=r/s\), with \(q,s>0\), if and only if \(ps=rq\). No decimal approximation is needed.

Proof. Every retained value is rational, since it is a ratio \(p/q\) with integer numerator and positive denominator. No two retained values are equal: if a value has already appeared, the rule discards every later occurrence of it. To show that no rational is omitted, let \(x\in\mathbb{Q}\). By the definition of the rationals, \(x=p/q\) for some \(p\in\mathbb{Z}\) and \(q\in\mathbb{N}\). This pair has finite height \(|p|+q\), so it is reached after finitely many blocks. At that point the value \(x\) has either already been retained at an earlier pair or is retained at \((p,q)\). Hence every rational occurs in the list. Finally, the list does not end: the distinct rationals \(1,2,3,\ldots\), represented by \(1/1,2/1,3/1,\ldots\), all occur. Thus the retained values form an infinite list with no repetitions. \(\square\)

This scanning method proves countability, but we can describe the duplicate-free list more directly. Every rational can be written in a reduced form, and that reduced form is unique when the denominator is required to be positive. We record the elementary facts that justify using it.

Proof. Start with any representation \(p/q\), \(q>0\), and let \(g\) be the greatest common divisor of \(|p|\) and \(q\). Dividing both by \(g\) gives \(p/g\) and \(q/g\), with positive denominator. These have no common divisor greater than \(1\): such a divisor would give a common divisor of \(p\) and \(q\) larger than \(g\). This also handles \(p=0\), since then \(g=q\) and the reduced form is \(0/1\).

For uniqueness, suppose \(a/b=c/d\), where \(b,d>0\) and both fractions are reduced. If \(a=0\), reducedness forces \(b=1\). The equality then gives \(c=0\), and reducedness forces \(d=1\), so the representations agree. If \(a\ne0\), then \(c\ne0\) as well. Cross multiplication gives \(ad=bc\). Since \(b\) is relatively prime to \(a\) and divides \(ad\), Euclid’s lemma gives \(b\mid d\). Since \(d\) is relatively prime to \(c\) and divides \(bc\), it gives \(d\mid b\). Positive integers that divide each other are equal, so \(b=d\); the cross-multiplied equality then gives \(a=c\). Thus the reduced representation is unique. \(\square\)

Here Euclid’s lemma says that if relatively prime integers \(u,v\) satisfy \(u\mid vw\), then \(u\mid w\). It follows from Bézout’s identity: there are integers \(r,s\) with \(ru+sv=1\); multiplying by \(w\) shows that \(u\mid w\) when \(u\mid vw\). This is the elementary divisibility fact used in the uniqueness argument.

A Concrete Enumeration by Reduced Fractions

Use the same height blocks, but now retain only pairs \((p,q)\) for which \(p/q\) is reduced. Because reduced representations are unique, no two retained pairs give the same rational. Every rational has a reduced representation, so every rational appears in its corresponding finite block. The resulting blocks can therefore be concatenated into a list.

Proof. Each height block is finite because \(-h+1\le p\le h-1\), and \(q=h-|p|\) is then determined. Each block is nonempty: at height \(h\), the pair \((h-1,1)\) is reduced, including \((0,1)\) when \(h=1\). Thus the blocks can be concatenated in order as a sequence. Every rational has a reduced representation by the lemma, and the pair for that representation has some finite height, so the rational occurs. If two entries in the sequence represented the same rational, they would be two reduced representations with positive denominators. The uniqueness part of the lemma says those pairs are equal. Hence no rational appears twice. The sequence is therefore a bijection from \(\mathbb{N}\) to \(\mathbb{Q}\). \(\square\)

Why the Conditions Matter

The numerator must range over all integers, and the denominator must be positive. If both are restricted to positive integers, the resulting list cannot contain negative rationals or zero. For example, no ratio \(p/q\) with \(p,q\in\mathbb{N}\) is negative, and none is \(0\). Allowing negative denominators as well is unnecessary: a negative denominator can be made positive by changing the signs of both numerator and denominator.

A second pitfall is to list all pairs without removing repetitions and then call the resulting values an enumeration of \(\mathbb{Q}\). The pair list does visit every rational, but it does not list each rational exactly once: \(1/2,2/4,3/6,\ldots\) all give the same value. Filtering repeated values fixes this, while restricting to reduced fractions gives a direct rule for a list with no duplicates. The key is that each block is finite and every rational is reached at a finite height; merely writing down a few rows of fractions would not establish either fact.