Can Every Fraction Be Counted?

Definition The diagonal enumeration is a way to list the positive rational numbers. Lay out a grid in which the cell in column $p$ and row $q$, for positive integers $p$ and $q$, holds the fraction $p/q$, so the numerators grow to the right and the denominators grow downward. Visit the cells diagonal by diagonal, where a diagonal is the set of cells with the same sum $p + q$. The sums are taken in the order $2, 3, 4, \dots$, and within a diagonal $p$ increases. A diagonal with sum $d$ has only $d - 1$ cells, so each one is finished after finitely many steps. Keep a cell when its fraction is in lowest terms and skip it otherwise, because the same number was already kept on an earlier diagonal. The kept fractions, in the order visited, form a list $r_1, r_2, r_3, \dots$ that begins

Every positive rational number appears in this list exactly once. It appears, because it can be written in lowest terms as $p/q$, and that cell lies on the diagonal with sum $p + q$, which is reached after finitely many cells, and it is kept. It appears only once, because only one cell holds it in lowest terms. The full list

then contains every rational number exactly once, with zero placed first and each negative number right after its positive partner. So the rational numbers form a countable set. This answers the question in the title. The rational numbers are dense, so they cannot be listed in order of size, but a list does not have to follow the order of size. This one jumps back and forth along the number line, and the entry after $r_k$ is simply the next entry of the list, not a next larger rational number, which does not exist.

Definition A rational number is a number that can be written as a fraction $p/q$, where $p$ is an integer and $q$ is a nonzero integer. Two fractions $p/q$ and $p'/q'$ name the same rational number exactly when $pq' = p'q$, so each rational number is named by many fractions. Every rational number is zero, positive or negative, and every positive rational number can be written as $p/q$ with both $p$ and $q$ positive integers. The set of all rational numbers is written $\mathbb{Q}$.

Definition A fraction $p/q$ with an integer $p$ and a positive integer $q$ is in lowest terms when the only positive integer that divides both $p$ and $q$ is $1$. This is written $\gcd(p, q) = 1$, where $\gcd$ stands for the greatest common divisor. Dividing the numerator and the denominator by their greatest common divisor gives a fraction in lowest terms with the same value. Every rational number has exactly one fraction in lowest terms with a positive denominator, and for zero it is $0/1$. In the grid, where numerators and denominators are positive, each positive rational number therefore has exactly one cell in lowest terms, and that is the cell the diagonal enumeration keeps. Every other cell with the same value is $(gp)/(gq)$ for some integer $g \ge 2$, so the cell in lowest terms has the smallest sum and lies on the earliest diagonal.

Definition A set is countable when it is finite or countably infinite, that is, when its elements can be arranged in a list, finite or endless, in which every element appears at some finite position. Here the positions are numbered $1, 2, 3$ and so on. Starting at $0$ instead, as some books do when they number the natural numbers, changes nothing. A list that contains every element at least once is enough, even with repeats, because deleting each repeat after its first appearance leaves a list in which every element appears exactly once. Some books use the word countable only for countably infinite sets.

Definition A set $D$ of real numbers is dense in the real line when every interval $(a, b)$ with $a < b$ contains at least one element of $D$. The rational numbers are dense. Given $a < b$, choose a positive integer $n$ with $n(b - a) > 1$. Neighboring numbers of the form $m/n$, with $m$ an integer, are then less than $b - a$ apart, so the first of them to the right of $a$ lies strictly between $a$ and $b$. In particular, between two different rational numbers there is always a third, so no rational number has a next larger rational number. Being dense is a property of positions on the number line, while being countable is a property of matching with the positive integers, and a set can have both. Cantor’s Diagonal Argument shows that the real numbers between $0$ and $1$ are not countable.