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.

This **math shirt** can be purchased via our nerdy shirt site.

March 13th, 2010 at 9:13 pm

Hi, there’s a typo in the second paragraph of this page.

“The integers are obviously a subset of the natural numbers, but there is a way to label the rationals with integers so that each label is used exactly once”

While you can obviously choose an embedding to make that statement true, you probably meant to write “The natural numbers are obviously a subset of the rational” so that it makes sense with the second part of the sentence.