Why the rationals can be numbered

Numbering pairs of integers

The starting point is the enumeration of $\mathbb{N}^2$ along successive diagonals. We first go through the pairs whose coordinates sum to $0$, then $1$, then $2$, and so on. Each diagonal contains only finitely many pairs, so the traversal reaches every pair in finite time.

Diagonal $i + j$	Pairs visited	Ranks assigned
$0$	$(0,0)$	$0$
$1$	$(0,1)$, $(1,0)$	$1$, $2$
$2$	$(0,2)$, $(1,1)$, $(2,0)$	$3$, $4$, $5$
$3$	$(0,3)$, $(1,2)$, $(2,1)$, $(3,0)$	$6$ to $9$

Cantor's pairing formula gives the rank explicitly:

$$\pi(i, j) = \frac{(i + j)(i + j + 1)}{2} + i$$

It is a bijection from $\mathbb{N}^2$ onto $\mathbb{N}$: $\mathbb{N}^2$ is countable.

$\mathbb{Q}$ is countable

Every strictly positive rational can be written uniquely as $\dfrac{p}{q}$ in lowest terms, with $p$ and $q$ coprime strictly positive integers. The map

$$\frac{p}{q} \longmapsto (p, q)$$

is therefore an injection from $\mathbb{Q}_+^*$ into $\mathbb{N}^2$, which is countable. Since an infinite subset of a countable set is countable, so is $\mathbb{Q}_+^*$.

We conclude by putting the pieces together: $\mathbb{Q}$ is the union of $\mathbb{Q}_+^*$, $\mathbb{Q}_-^*$ and $\{0\}$, hence a finite union of countable sets — it is countable.

A concrete enumeration

The positive rationals can also be enumerated by increasing height, where the height is the sum $p + q$ of the reduced form, ordering by increasing numerator for equal heights:

$$\frac{1}{1},\ \frac{1}{2},\ \frac{2}{1},\ \frac{1}{3},\ \frac{3}{1},\ \frac{1}{4},\ \frac{2}{3},\ \frac{3}{2},\ \frac{4}{1},\ \ldots$$

Fractions not in lowest terms, such as $\dfrac{2}{2}$, are skipped to avoid repetitions. Since each height gives only finitely many fractions, every rational eventually appears, exactly once.

Algebraic numbers too

The same argument goes further than you might think. An algebraic number is a root of a nonzero polynomial with integer coefficients. Now, for a fixed degree $n$ and a fixed bound $H$, there are only finitely many polynomials with integer coefficients bounded by $H$, each having at most $n$ roots.

The set of algebraic numbers is therefore a countable union of finite sets: it is countable. This remark, combined with the next chapter, will produce a spectacular result.

Classic pitfall

Proposing as an enumeration of $\mathbb{Q}_+^*$ the traversal "first all the $\dfrac{1}{q}$, then all the $\dfrac{2}{q}$, and so on." This list never finishes the first row, so it never reaches $\dfrac{2}{1}$: it is not an enumeration. A proper bijection must assign every element a finite rank, which is guaranteed by cutting into finite slices — diagonals or heights.