The rationals are infinite and dense — can you even list them? It sounds like a trick question. But there is a beautiful tree, built by a rule a child can follow, that places every positive rational at exactly one node, already in lowest terms, with no repeats and no omissions. It is called the Stern–Brocot tree, and once you see it, the question "are there more rationals than integers?" feels answered.

The rule that builds it

Start with two boundary fractions — not in the tree, but flanking it — called the zero fraction \tfrac{0}{1} and the infinity fraction \tfrac{1}{0}. Between any two adjacent fractions \tfrac{a}{b} and \tfrac{c}{d}, insert their mediant:

\text{mediant}\!\left(\dfrac{a}{b},\, \dfrac{c}{d}\right) \;=\; \dfrac{a + c}{b + d}.

The first mediant, between \tfrac{0}{1} and \tfrac{1}{0}, is \tfrac{0+1}{1+0} = \tfrac{1}{1}. That is the root of the tree. Now between \tfrac{0}{1} and \tfrac{1}{1} you get \tfrac{1}{2}; between \tfrac{1}{1} and \tfrac{1}{0} you get \tfrac{2}{1}. Those are the two children. Keep mediant-ing forever.

Why does every step give a fraction in lowest terms? Because if \tfrac{a}{b} and \tfrac{c}{d} are neighbours in this construction, they satisfy bc - ad = 1 — a determinant condition preserved by the mediant operation — and \gcd(a+c, b+d) = 1 follows from that.

The first four rows

The first four rows of the Stern-Brocot treeA binary tree drawn with rows labelled depth 1 through 4. The root at depth one is the fraction one over one. Depth two has one over two on the left and two over one on the right. Depth three has one over three, two over three, three over two, three over one. Depth four has one over four, two over five, three over five, three over four, four over three, five over three, five over two, four over one. Each parent connects down to two children with diagonal lines.depth 1depth 2depth 3depth 41/11/22/11/32/33/23/11/42/53/53/44/35/35/24/1every fraction shown is already in lowest terms — and the tree keeps going forever
Root: $\tfrac{1}{1}$. Each child is the mediant of its parent with the nearest ancestor on that side. Depth $k$ has exactly $2^{k-1}$ nodes, and together the four depths shown list $15$ distinct positive rationals — all in lowest terms, no duplicates.

Two facts that make the tree remarkable

Fact 1: every fraction that appears is already in lowest terms. You never need to simplify. If the tree produces \tfrac{6}{10}, it is because you took a wrong mediant somewhere — the real tree gives \tfrac{3}{5} directly.

Fact 2: every positive rational appears exactly once. No fraction is missed, and no fraction turns up twice under a different disguise. \tfrac{22}{7} is somewhere. \tfrac{355}{113} is somewhere. \tfrac{1}{10^{100}} is somewhere. Each has a unique address in the tree — a specific path "left, left, right, left, right, right, …" from the root that lands on it and no other.

Why exactness? Induction on the tree's construction. At every stage, the fractions listed left-to-right are strictly increasing, each new mediant fits strictly between its two neighbours, and the bc - ad = 1 invariant forces lowest terms. Since each path corresponds to a unique sequence of mediant-takings, and each rational is the limit of exactly one such path of strictly nested intervals, the tree is a bijection with \mathbb{Q}_{>0}.

Finding a specific rational

Suppose you want to find \tfrac{3}{5} in the tree. Start at the root \tfrac{1}{1}. Compare \tfrac{3}{5} to \tfrac{1}{1}: \tfrac{3}{5} < \tfrac{1}{1}, so go left to \tfrac{1}{2}. Compare \tfrac{3}{5} to \tfrac{1}{2}: \tfrac{3}{5} > \tfrac{1}{2}, so go right to \tfrac{2}{3}. Compare \tfrac{3}{5} to \tfrac{2}{3}: \tfrac{3}{5} < \tfrac{2}{3}, so go left to \tfrac{3}{5}. Arrived.

Path: L-R-L. That is the Stern–Brocot "address" of \tfrac{3}{5}. Every positive rational has such an address, and the address is finite — every rational appears at some specific depth, not at infinity.

Read a path

Follow the path L-R-R-L starting at the root.

  • Start: \tfrac{1}{1}, bracketed by \tfrac{0}{1} and \tfrac{1}{0}.
  • L: go below \tfrac{1}{1}. New node is \tfrac{0+1}{1+1} = \tfrac{1}{2}, bracketed by \tfrac{0}{1} and \tfrac{1}{1}.
  • R: go above \tfrac{1}{2}. New node is \tfrac{1+1}{2+1} = \tfrac{2}{3}, bracketed by \tfrac{1}{2} and \tfrac{1}{1}.
  • R: go above \tfrac{2}{3}. New node is \tfrac{2+1}{3+1} = \tfrac{3}{4}, bracketed by \tfrac{2}{3} and \tfrac{1}{1}.
  • L: go below \tfrac{3}{4}. New node is \tfrac{2+3}{3+4} = \tfrac{5}{7}, bracketed by \tfrac{2}{3} and \tfrac{3}{4}.

End: \tfrac{5}{7}. Why: at each step you take the mediant of the current node with the bracket on the side you are moving toward, and that new mediant replaces the bracket on the side you are moving away from.

What this picture is really saying

The Stern–Brocot tree is the proof, made visible, that \mathbb{Q} is countable: its positive elements can be labelled 1, 2, 3, \dots by reading the tree level by level (or by using the path-to-number correspondence above). Between any two integers there are infinitely many rationals — but that does not make the rationals bigger than the integers. Both sets are countable; they have the same cardinality.

The irrationals, by contrast, cannot be listed this way. There is no Stern–Brocot-like tree for \mathbb{R} — any attempted listing misses some reals, by a diagonal argument you will meet later. So density and cardinality are independent properties: the rationals are dense in the reals but vastly smaller in size.

The golden ratio's path

The golden ratio \varphi = \tfrac{1 + \sqrt{5}}{2} \approx 1.618 is irrational, so it is not a node of the tree. But it is a limit of nodes: the path R-L-R-L-R-L-… (alternating forever) generates the fractions

\tfrac{1}{1},\; \tfrac{2}{1},\; \tfrac{3}{2},\; \tfrac{5}{3},\; \tfrac{8}{5},\; \tfrac{13}{8},\; \tfrac{21}{13},\; \dots

the consecutive Fibonacci ratios. They converge to \varphi without ever reaching it — the Stern–Brocot tree's way of saying "\varphi sits in the gap." Irrationals are the infinite paths in this tree; rationals are the finite paths.

This satellite sits inside Number Systems.