First, a quick recap: continuing an exposition of the paper Recounting the Rationals, we’re investigating the tree of fractions shown below (known as the Calkin-Wilf tree), which is constructed by placing 1/1 at the root node, and giving each node the two children (on the left) and (on the right). Here are the first four levels of the tree (of course, it has infinitely many levels):

The Calkin-Wilf Tree

In my last post I claimed that this tree has a number of remarkable properties; in this and subsequent posts I plan to show exactly why these properties are true, since for the most part they have relatively simple explanations—although that in no way makes them any less remarkable!

Today let’s begin by tackling the first property I claimed, namely, that every single positive rational number occurs somewhere in this tree. How can we prove this?

First, notice that given any rational in the tree, there is any easy way to tell whether it is the left or right child of its parent. (Can you figure it out before reading on?)

Since left children are always of the form , they will always have a denominator greater than their numerator (, since j is positive); and vice versa for right children, which are of the form and consequently have a numerator greater than their denominator. So, given some fraction in the tree , to decide whether it is a left or right child, just compare m and n. If n is greater, it is a left child, and its parent is ; otherwise, it is the right child of .

Moving up the Calkin-Wilf tree

For example, if we start with 5/3, we see that 5 > 3, so 5/3 must be the right child of (5-3)/3 = 2/3; 2/3, in turn, has a greater denominator, so it is the left child of 2/(3-2) = 2/1, and 2/1 is the right child of 1/1.

Moving up the Calkin-Wilf tree starting from 5/3

In fact, it is easy to see that I’ve just described a simple procedure for finding your way up the tree, starting from any positive rational in lowest terms. At each step, just take the numerator and denominator, and subtract the smaller from the larger. (They can never be equal until we get to 1/1, since we start out with something in lowest terms.) But how do we know that we will eventually reach 1/1 this way? Well, both the numerator and the denominator are always positive during this process (they start out positive, and you can’t get something negative by subtracting something smaller from something larger), and one of them gets smaller at every step. Think about this for a minute. They must eventually reach 1/1 — there’s nowhere else for them to go!

Well, if we can find a path up to 1/1 from any reduced positive rational, every such rational must be in the tree in the first place! You may also note that since we have no choice at each step, there is exactly one path from any rational up to the root of the tree — which means that each reduced rational occurs in only one place in the tree; there are no duplicates.

Now, technically, one thing we haven’t shown is that there aren’t any unreduced rationals which sneakily sneak in along with the reduced ones; but that’s not too hard to show, and I’ll talk about that next time.

There are several other interesting things going on here — for example, the path from any reduced rational up to the root of the tree corresponds directly to using the Euclidean Algorithm to prove that the rational is, in fact, reduced! And if you interpret the lefts and rights in the path as zeros and ones in binary… but I’m getting ahead of myself, that’s for a later post. =)