This is the first in a series of posts I’m planning to write on the paper “Recounting the Rationals“, by Neil Calkin and Herbert Wilf, mathematicians at Clemson University and the University of Pennsylvania, respectively. I’m really excited about it, and I hope that you’ll soon see why! It’s an incredibly elegant and interesting paper, but it’s also quite accessible to anyone with only a modest background in mathematics—that is, it would be if it were longer than three and a half pages. Calkin and Wilf’s main audience is other mathematicians, of course, so their presentation is fairly concise, trusting the reader to fill in many of the details. So, I plan to take my time going through their ideas, filling in many of the details, and highlighting some interesting tangents along the way. However, I do not plan to “dumb it down” in any way—I’m going to write about every single bit of mathematics in their paper.

Today, by way of introduction, I’d like to talk about the motivating question: is it possible to make a list of all the positive rational numbers? If it is possible, how can we do it in a nice way?

Well, let’s think about it. How would you make a list of all the positive rational numbers? (You may wish to stop and actually think about this question for a few minutes. No, really!) Recall that rational numbers are simply fractions of the form , where p (the numerator) and q (the denominator) are integers, and q isn’t zero. For example, , and are positive rational numbers. (You may have learned about “proper” and “improper” fractions in school, where “proper” fractions are those in which the numerator is less than the denominator; I would advise you to forget about such a mathematically useless distinction as quickly as possible!)

Here’s one idea: list all the rational numbers with a denominator of 1, followed by all the rational numbers with a denominator of 2, and so on. Like this:

Unfortunately, while technically correct (for suitable values of “technically”), this is not a very good solution. The problem is that if you tried to write down this list, you’d never even make it through the rationals with denominator 1, since there are infinitely many! You would never, ever get to 1/2, let alone something like 43/19. We’d like our list to contain every positive rational at a finite index: that is, if someone else (say, your evil, plaid-pants-wearing, math-hating arch-nemesis) picks a positive rational number, no matter what it is, you should be able to start writing out your list of rationals from the beginning and eventually—as long as you keep writing for a long enough, yet finite, amount of time—write down the chosen rational. Obviously, our first try is a failure in this department. That evil arch-nemesis has only to pick something like 1/3, and we’re sunk!

Now, you may think this is impossible: our first try failed, so it would seem, because there are “too many” rationals. We couldn’t even make it through all the rationals with denominator 1; how can we possibly hope to rearrange things so that every rational occurs at a finite place in the list? Well, the first rule of dealing with infinity is: don’t trust your intuition when dealing with infinity! As it turns out, there aren’t “too many” rationals, we just happened to put them in a bad order. To get a better sense of what’s going on here, think about making a list of all the positive integers, like this: first, write down all the odd positive integers; then, write down all the even ones.

This list obviously includes all the positive integers, but it’s a bad list in the same way as our initial try at a list of rationals: if you tried to write it down, you would keep listing out odd integers forever, without ever getting around to the even ones. But in this example, it’s easy to see that this can be fixed: everyone knows that if you write out the positive integers in order, you’ll eventually get to any positive integer you want, as long as you keep writing long enough.

Ah, that’s better!

Okay, so here’s another idea: list the positive rationals in order by the sum of their numerator and denominator. We can agree to list rationals with the same sum in order by their numerator. So, the first rational in our list is the only one with a sum of 2, namely, 1/1. Next, the rationals with a sum of 3: 1/2, 2/1. Then 1/3, 2/2, 3/1, followed by 1/4, 2/3, 3/2, 4/1, and so on. This is the same thing as putting the rationals in a grid, and listing them by “diagonals”, like this:

Pretty simple, right? Now, it’s easy to see that every positive rational is included in this list: the numerator and denominator of every positive rational sum to something (duh!), so any rational we can think of will get included when we get to that sum. More exciting is the fact that there are only a finite number of rationals with any given sum (in fact, you can see that there are exactly rationals with sum ), which means that every rational must occur at a finite place in the list! Hooray! (By the way, another way to say that we can make a list of the positive rational numbers like this is that the positive rationals are countable. It is an astonishing fact (with a nifty proof) that although the rational numbers are countable, the real numbers aren’t — but that’s for another post!)

There’s still something unsatisfying about this solution, though: many numbers occur more than once. In fact, every number occurs infinitely many times! For example, 1/1, 2/2, 3/3, 4/4, and so on are really all the same rational number (namely, 1) but they all occur separately in our list. The same is true of 1/2, 2/4, 3/6… and so on. Should we leave the repeats in? (Bleh.) Should we just say that we won’t write down any numbers that have already occurred earlier? (Yuck.) Either way seems inelegant.

Is it too much to ask for a list of the positive rationals which includes each number exactly once, in lowest terms?

As you have probably guessed, it isn’t too much to ask—and that’s where Calkin and Wilf’s paper comes in! They describe an extremely elegant way to list all the positive rational numbers, which has all the nice properties we’ve just talked about, and a few more besides. In the next post in this series, I’ll reveal what that list actually is, and then I’ll spend several posts talking about (and proving) all of its nice properties. Along the way we’ll talk about binary trees and binary numbers, the principle of induction, recursion, and a bunch of other interesting things.

(PS — the Carnival of Mathematics is coming soon! There are still a few more hours left for last-minute submissions… I should have it up by midnight at the earliest or tomorrow morning at the latest. Get excited! =)