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! =)
Pingback: Math in the News: Infinities « 360
I think you can guess which part of this I object to.
I remember idling in Matt’s common room, looking at the first page of the math text Frank Morgan had given in its draft form to the class Matt was TAing. Was it Real Analysis? That’s where I learned the rationals were countable; I remember my deep skepticism and then my admiration of the demonstration’s elegance, recalled now by your table above.
I also took note that this proof occurred on page two of the textbook, evidently meaning that far, far more difficult revelations than this stretch were to come . . .
Note that plaid PANTS are totally different than plaid SHIRTS. Like the difference between Darth Vader and Luke Skywalker. They both use the Force, but…
Is it true to say the Calkin and Wilf construction and the Stern Brocot construction as opposed to Cantors diagonal grid method for counting the rationals do not involve the Axiom of Choice?
Stuart: None of them require the Axiom of Choice. The Axiom of Choice states that every set has a well-ordering (a total order on the set under which every subset has a least element). But all three of the methods you mention for enumerating the rationals define nice, well-behaved well-orderings. There is no need to invoke the Axiom of Choice in order to assert the existence of a well-ordering if we can exhibit an actual, concrete one.
Thanks for that, I guess you have to expose your ignorance in order to learn sometimes. Where I was coming from was this quote (wikipedia) “In mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and there is no “rule” for which object to pick from each. The axiom of choice is not required if the number of bins is finite or if such a selection “rule” is available.” I assumed that in order to ‘cross out’ the infinite numbers of repeat fractions eg 1/1, 2/2, 3/3,… one has to make a selection from an infinite number of ‘bins’, is this not the case because as the quote says, there is a “rule”?
Sure, asking questions is a great way to learn, and necessarily questions expose your ignorance. Nothing wrong with that. =) And you’re exactly right: since there is a nice, well-defined “rule” in this case that tells us which numbers to pick/cross out etc., we don’t need AC. You only need the Axiom of Choice if you simply want to assert the existence of a function which will (arbitrarily) choose one thing from each bin, and you have no way of otherwise saying how such a function might actually be constructed. The situations where you actually need this are rather esoteric. Interestingly, AC is “independent” of the other basic axioms of set theory (the so-called “Zermelo-Fraenkel” axioms)–that is, you can neither prove nor disprove AC from the other axioms, and you can assume AC or you can assume its negation, and nothing breaks either way.
Pingback: Full Speed Ahead! « The Math Less Traveled
Pingback: Cardinality of infinite sets, part 1: four nonstandard proofs of countability « Division by Zero
Pingback: Recounting the Rationals, part II (fractions grow on trees!) « The Math Less Traveled
Pingback: Recounting the Rationals, part III « The Math Less Traveled
Pingback: Recounting the Rationals, part IV « The Math Less Traveled
Pingback: The hyperbinary sequence and the Calkin-Wilf tree « The Math Less Traveled
Awesome post. Its been too long since I’ve enjoyed mathematics!
Pingback: Carnival of Mathematics #59 « The Number Warrior
Pingback: Irrationality of pi « The Math Less Traveled
Pingback: The hyperbinary sequence and the Calkin-Wilf tree | The Math Less Traveled
Pingback: Recounting the Rationals, part III | The Math Less Traveled
Pingback: Recounting the Rationals, part II (fractions grow on trees!) | The Math Less Traveled