Stern sequence visualized

The usual proof that the rationals are countable is done by first nesting the rationals inside ordered pairs of natural numbers: $$ℚ \rightarrow \N^2, \frac{a}{b} \rightarrow (a, b)$$ and then enumerating $\N^2$ diagonally. Since $\N^2$ is countable and ℚ $\subset \N^2$, then clearly ℚ is countable as well. This proof is great not just because of its straightforwardness, but because it illustrates one of the confusing aspects of cardinality: the natural numbers sit inside the rationals which sit inside the ordered pairs of naturals, yet they’re all the same “size!” This is an early indication of why we need cardinality, since the usual intuition of sizes of sets start breaking down once you get into infinite sets.

That doesn’t have to mean we stop here, though.

There’s another way to show that ℚ is countable, and even better, directly write down our bijection. For this, we bring in Stern’s diatomic sequence:

$$S_0 = 0, S_1 = 1$$ $$S_{2n} = S_n$$ $$S_{2n + 1} = S_n + S_{n+1}$$

The Stern sequence has been around since 1858 and has been studied and written about by many, many people. For comparison, Georg Cantor, who’s responsible for introducing the concept of cardinality, was born in 1845; the Stern sequence predates almost his entire mathematical career. But neither Cantor nor Stern got to connecting their two ideas together; that’s owed to Calkin and Wilf a full 150 years later. They use $b(n)$, the number of hyperbinary representations of $n$, which has a lot of interesting properties and links to the Stern sequence, but I find it’s simpler to use the Stern sequence itself; for that, I’m referencing a paper by Northshield. We start with a lemma:

For every pair of two relatively prime numbers $[a,b]$, there exists a unique number $n$ such that $[S_n, S_{n+1}] = [a, b]$.

There’s two proofs available (here). This lemma gets us almost the entire way there, since any rational number is just a pair of relatively prime numbers $p/q$.