If there is a 1-1 correspondence between a set and the integers, then the set is called countable. Cantor proved that the real numbers are not countable, while the rational numbers are countable. The integers are obviously a subset of the rational numbers, but there is a way to label the rationals with integers so that each label is used exactly once. These results are covered in a college introduction to real analysis, but without giving an explicit construction. This is a shame, since the Calkin-Wilf tree produces a simple, natural bijection between the positive integers and the positive rationals.
To construct the Calkin-Wilf tree, start with 1/1. This is a binary tree, and every node has two children. The left child of 1/1 is 1/2, and the right child is 2/1. The left child of a/b is a/(a+b), and the right child is (a+b)/b. The descendants of 1/2 are 1/3 and 3/2. The descendants of 2/1 are 2/3 and 3/1.
Euclid’s algorithm is a classical method for finding the greatest common divisor of two numbers. Any number which is a factor of both 10 and 24 is also a factor of their difference, 14, so GCD(10,24) = GCD(10,14) = GCD(10,4) = GCD(6,4) = GCD(2,4) = GCD (2,2) = 2.
The Calkin-Wilf tree is related to Euclid’s algorithm, since the descendants of a/b are the fractions whose (numerator,denominator) pair leads to (a,b) under Euclid’s algorithm: (a,a+b) and (a+b,b). Since every positive rational number has a unique form p/q with p and q relatively prime, and Euclid’s algorithm reduces (p,q) to (1,1), every positive rational is contained in the Calkin-Wilf tree precisely once.
If we read the rows of the Calkin-Wilf tree in order, 1/1, 1/2, 2/1, 1/3, 3/2, … we get a list containing each positive rational number exactly once. Where does p/q appear? To find the binary expansion for the location, perform Euclid’s algorithm on (p,q) to reduce it to (1,1), and record a 0 when you replace (a,a+b) by (a,b), and a 1 when you replace (a+b,b) by (a,b). Add a terminal 1, and then reverse the digits. This is the binary expansion of the location n in the list.
The denominator of a/(a+b) is the same as the numerator of (a+b)/b. Surprisingly, this pattern also holds between adjacent fractions of the list which are not descendants of the same fraction, e.g., the right child of 1/3 is 4/3, and the left child of 3/2 is 3/5, and the denominator of 4/3 is the numerator of 3/5. (We highlighted this by using the same color.) This means the list of numerators 1,1,2,1,3,… determines the list of fractions, as the nth fraction is (numerator n)/(numerator n+1). What is this sequence of numerators?
The nth numerator is the number of ways of expressing n-1 as a sum of powers of two, where each power of two is used at most twice. For example, 6 can be expressed in 3 ways, as 4+2, 4+1+1, and 2+2+1+1. This provides a combinatorial way to construct the Calkin-Wilf tree, and to produce a bijection between the natural numbers and the positive rationals.
We chose the Calkin-Wilf tree as the subject for one of our math shirts because of its connections to multiple areas of mathematics, and because it deserves to be better known.