Education is a difficult task, it really is. Teaching takes a few tries to get the hang of. Writing textbooks is even harder. And math is one of those technical fields in which human error is hard to avoid. So usually, when I see a mistake in a math text, it doesn’t bother me much.

But some things just hurt my soul.

No correspondence between the integers and rationals? Yes there is, Example 2! Yes there is!

This horrifying falsehood was stated in the supplementary “Study Guide and Intervention” worksheet for the Glencoe/McGraw-Hill Algebra 2 textbook, and recently pointed out on Reddit. Or at least it was stated in some version of this worksheet. The original file can be found online at various websites, including one download link from Glencoe’s website that shows up on a Google search. There are other versions of the document that don’t contain this example, but this version was almost certainly used in some high schools, as the Reddit thread claims.

Luckily, mathematicians are here to set the record straight. The Wolfram blog published a fantastic post about this error already, with several proofs of the countability of the rationals. There are also several excellent older expositions on this topic, including on the Math Less Traveled and the Division by Zero blogs. I’ll discuss two of my favorites here as well.

But first, let’s talk about what is wrong with the argument in Example 2. The author is correct in stating that listing all the rationals in order would make a one-to-one and onto correspondence between the rationals and integers, and so they try to do so in a random way and failed. At that point, instead of trying a different ordering, they gave up and figured it couldn’t be done! That’s not a proof, or even logically sound (as my students at this year’s Prove it! Math Academy would certainly recognize.)

If one were going to try to prove that a certain set couldn’t be organized into a list, a common tactic would be to use **proof by contradiction:** assume there was a way to list them, and then show that something goes wrong and you get a contradiction. Of course, this wouldn’t work either in the case of the rationals, because they *can* be listed.

So let’s discuss a correct solution.

## Getting our definitions straight

First, let’s state the precise meaning of a one-to-one and onto correspondence. A **function** $f$ from a set $A$ to a set $B$, written $f:A\to B$, is an assignment of each element of $a\in A$ to an element $f(a)\in B$. To clear up another misuse of notation in the Glencoe Algebra textbook, the set $A$ is called the **domain** and $B$ is called the **codomain** (not the **range**, as Glencoe would have you think – the range refers to the set of elements of $B$ that are assigned to by the function.) A function is:

**One-to-one**, or**injective**, if no two elements of $A$ are assigned to the same element of $B$, i.e., if $f(x)=f(y)$ then $x=y$.**Onto**, or**surjective**, if every element of $B$ is mapped to, i.e., for all $b\in B$, there exists $a\in A$ such that $f(a)=b$.

For instance, if $\mathbb{Z}$ denotes the set of integers, the function $f:\mathbb{Z}\to \mathbb{Z}$ defined by $f(x)=2x$ is injective, since if $2x=2y$ then $x=y$. However, it is not surjective, since an odd number like $3$ is not equal to $2x$ for any integer $x$.

A function which is both injective and surjective is said to be **bijective**, and is called a **bijection**. This is just a shorter way of saying “one-to-one and onto correspondence,” which is wordy and cumbersome.

So, we want to find a bijection $f:\mathbb{Z}\to \mathbb{Q}$, where $\mathbb{Z}$ denotes the integers and $\mathbb{Q}$ the rationals. Notice that we can list all the integers in order: $$0,1,-1,2,-2,3,-3,\ldots$$

and so if we list all the rationals in order, $r_0,r_1,r_2,\ldots$, we can define the function $f$ accordingly by $f(0)=r_0$, $f(1)=r_1$, $f(-1)=r_2$, and so on. The function will be bijective if and only if every rational number appears in the list exactly once.

Next, let’s be precise about the rationals. Recall that the **rational numbers** are those numbers which can be written as fractions $a/b$ where $a$ and $b$ are integers with $b\neq 0$. In order to assign every rational number a unique representation, let us restrict to the case where $b>0$ and $a$ is any integer such that $\mathrm{gcd}(a,b)=1$. This condition makes $a/b$ into a reduced fraction. So the number $2/-4$ should be written as $-1/2$ in this convention. It follows that we can think of the set of rational numbers as the set $$\mathbb{Q}=\{(a,b) | b>0\text{ and }\mathrm{gcd}(a,b)=1\text{ and }a,b\in \mathbb{Z}\}.$$

## Listing the rationals, naively

One way to construct this list is to think of the rationals as ordered pairs $(a,b)$ of integers with $b>0$ and $\mathrm{gcd}(a,b)=1$ as described above. There is an easy way of ordering all pairs of integers – plot them on a coordinate plane, and use a spiral!

Now, to list the rationals, follow the spiral from $(0,0)$ outwards. Each time we reach an ordered pair of integers, say $(a,b)$, write it down if $b>0$ and $\mathrm{gcd}(a,b)=1$, and otherwise skip it and move on. (These are the green dots above.) This process guarantees that we list all the rationals exactly once.

## More elegant methods

There are many other elegant enumerations of the rationals, and one particularly nice one is due to Calkin and Wilf. They construct a binary tree in which each rational number appears exactly once, as shown below.

The tree is constructed as follows: start with $1/1$ at the top, and for each node $a/b$ in the tree, assign it the left and right children $a/(a+b)$ and $(a+b)/b$ respectively. This tree turns out to contain every positive rational number exactly once. It also has an incredible property: if we read the entries of each row of the tree successively from left to right, the denominator of each entry will match the numerator of the next entry, giving us a sequence of numerators/denominators:

$$1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,\ldots$$ such that the consecutive quotients give us a list of the positive rationals.

This makes me wonder is whether there is a way of listing the integers such that (a) every integer occurs exactly once in the sequence, and (b) the consecutive quotients give all rationals exactly once (allowing the consecutive integers to have common factors greater than one). Thoughts?

Nice post, and I like your question at the end! The bad news is that the question as stated has a quick answer of “no”: if 1 must appear as one of the consecutive quotients then … k, k … appears in the sequence of integers, so k is used more than once.

The good news is that, if we ask for every rational *other than 1* to appear exactly once, then it is possible!

Here’s a sketch of an inductive construction (decode with rot13): Svk lbhe snibevgr beqrevat bs gur engvbanyf. Tvira fbzr cnegvnyyl pbafgehpgrq frdhrapr F, yrg a or gur fznyyrfg vagrtre abg va F, naq yrg c/d or gur rneyvrfg engvbany va lbhe beqrevat gung qbrfa’g nccrne nf n pbafrphgvir dhbgvrag va F. Rkgraq F ol n srj ryrzragf gb vagebqhpr a naq dhbgvrag c/d (naq yvxryl fbzr bgure vagrtref naq dhbgvragf), orvat pnershy abg gb vagebqhpr nal ercrgvgvbaf (V’z bzvggvat qrgnvyf urer — guvf vf gur sha fgrc gb chmmyr guebhtu!). Ercrngvat guvf pbhagnoyl znal gvzrf ohvyqf gur qrfverq frdhrapr: vaqrrq, gur xgu vagrtre naq engvbany ahzore ner nppbhagrq sbe orpnhfr gurl ner sbepvoyl vafregrq ba fgrc x vs gurl qba’g nccrne fbbare, naq jr jrer fher arire gb perngr ercrngf.

Note: I assumed “positive integer” and “positive rational” above, but 0 and negatives can be handled in much the same way. Just make sure your sequence starts with 0 to avoid trying to divide by it.

Thanks for sharing, and for the spoiler encoding, Zach! I’ll think about it before reading your solution, but it’s exciting to know it exists. ðŸ™‚

Hi Maria,

Great post! I’d like to add that the second construction has a connection with the Euclid algorithm for the gcd: If you go backwards, you change to (a,a-b) (if you suppose a > b, of course).

Here’s a silly answer to your last question: 1 is a rational, so to achieve all rationals, some integer is going to have to be repeated twice in a row. I think (but haven’t checked carefully) that it’s not hard to get all rationals strictly between 0 and 1 via a strictly increasing sequence of integers. But it’s a good question whether you can get all positive rationals, excluding 1, without repetitions….

Indeed, thanks for pointing that out! Looks like Zach knows such a solution, above, that gets all the rationals except 1.

“The Cat in Numberland” is a great picture book with a proof of this, taking place in a hotel whose proprietor looks just like Hilbert.

vojupklatdfrocokquerqnideqrsed

Pingback: Homepage