The study of cardinalities of infinite sets is one of the most intriguing areas of mathematics that an undergraduate mathematics major will encounter. It never fails to bring crooked smiles of joy, disbelief, confusion and wonder to their faces. The results are beautiful, deep, and unexpected.

Recall that two sets have the same cardinality if they can be put in a 1-1 correspondence. For example, the fingers on my hands can be put in a 1-1 correspondence with the set {1,2,3,4,5,6,7,8,9,10}, thus we say that I have ten fingers.

Things become more interesting when we turn to infinite sets. For example, the positive integers have the same cardinality as the integers. They can be paired up as follows:

This fact usually wows the students (some refuse to accept it at first), but we’re just getting started.

We say that a set is countable if it is finite or if it can be put into a 1-1 correspondence with the positive integers (in this latter case we often say that the set is countably infinite). If a set is not countable, it is uncountable.

Essentially, a set is countable if the elements can be listed sequentially: Examples of countably infinite sets include the integers, the even integers, and the prime numbers.

Finally, we turn to the rational numbers (the set of numbers that can be written as a fraction). We know that there are “many” of them. Not only are they infinite in number, they form a dense subset of the real number line; they are not discrete like the sets mentioned above. Between every two real numbers, regardless of how close together, you can find infinitely many rational numbers.

Shockingly, despite their seeming abundence, they are countable, just like the integers!

The usual proof (which I believe was Cantor’s 1873 proof) is to put the positive rationals in a rectangular grid. In each row the numerators are the same and the denominators increase by 1, and in each column the denominators are the same and the numerators increase by 1. Then we list the numbers by zig-zaging through the grid along 45 degree lines, skipping over fractions that have already appeared in the list (for example, if we had 1/2, then we’d skip over 2/4, 3/6, etc.), but hitting every entry. This shows that the positive rationals are countable. It is not hard to see that this implies that the rationals are countable also. This is a fine, but somewhat inelegant proof. (See this website for details.)

I’ll now present four different, less well-known proofs of the countability of the rationals.

Proof I. In their 2000 paper “Recounting the Rationals” Neil Calkin and Herbert Wilf gave a new and extremely elegant proof that the positive rational numbers are countable.

First, construct a binary tree with 1/1 at the top. Under 1/1 put 1/2 and 2/1. Continue down the tree as follows. Below each rational number , place the two rational numbers and . Part of the tree is shown below.

Here are some remarkable facts about this tree.

1. Every positive rational number appears somewhere in this tree.
2. No rational number appears twice in this tree.
3. All the entries are in reduced form.

Now create a list of the rational numbers by proceeding through the tree breadth first. That is, list the first row, then the second row, then the third row, etc. The first 15 terms are: 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 5/2, 2/5, 3/4, 4/1,… This shows that the positive rational numbers are countable.

Incidentally, although the sequence of rationals may appear unordered, it has some interesting properties.
1. The denominator of one fraction is the numberator of the next one.
2. The th denominator is the number of ways to write as powers of two in which each power of two is allowed at most twice. (For example, when we have a denominator of 3 because .)

The proofs of all of these facts are not too difficult. For more information see Calkin and Wilf’s original paper or this nice 5-part blog post at The Math Less Traveled.

Proof II. The next two proofs use the fact that union of countably many finite sets is countable. This is easy to see. If the sets are finite, then we can list by listing the elements of , followed by the elements of , , , and so on (removing duplicates, if any).

Let . For example, , , , etc. Clearly each such set is finite. Moreover is precisely the set of rational numbers. Thus the set of rational numbers is countable.

(I’m currently teaching real analysis, and this is the proof found in our textbook, Stephen Abbott’s Understanding Analysis.)

Proof III. The third proof is actually much more versatile than the others. It is found in Rob Kantrowitz’s paper “A Principle of Countability” (Mathematics Magazine, Vol. 73, No. 1 (Feb., 2000), pp. 40-42).

He proves that the set of all possible words that can be written with a finite alphabet is countable.

The justification is easy. Let be the set of words of length . Each is finite (if there are letters in the alphabet, then has words). Reasoning as before, is countable.

Of course, we may not be interested in all words (all possible concatenations of letters), but only some words (ones that make sense in the context). Clearly a subset of a countable set is also countable.

Here’s our one sentence proof that the rational numbers are countable (as a corollary of the theorem above). Every rational number is a word written with letters in the following finite alphabet . For example, we have rational numbers .

We can use the theorem to prove that many other sets are countable too.

The set of all surds is countable. By surds we mean any number that can be obtained from the integers using addition, subtraction, multiplication, division, powers, and roots. Any such value can be written using the following alphabet . For example, can be written as .

This final shocking example is not in Kantrowitz’s paper, but can be proved using his method: the set of describable numbers is countable. That is, the collection of all numbers that could possibly be described by anyone in any fashion, using any symbols in any language, must be countable. Examples of describable numbers are 5, , , , and “the smallest positive root of the function .”

Why is this set countable? The describable numbers can only be described using some finite alphabet. This alphabet could be large—our 26 letters (capital and lower case), the greek alphabet (capital and lower case), binary operations, a (space), the integral symbol, punctuation, etc., etc.

As we will see in the next posting, the real numbers are uncountable. This means that the vast majority of the real numbers (uncountably many) are not describable!

I find this technique in Kantrowitz’s paper to be extremely satisfying. It is seems very intuitive and easy to apply in other contexts.

Proof IV. Here is yet another proof of the countability of the positive rational numbers. It can be found in Yoram Sagher’s 2-paragraph note, “Counting the Rationals” (The American Mathematical Monthly, Vol. 96, No. 9 (Nov., 1989), p. 823).

Each positive rational number can be written as where and are relatively prime. Suppose they have prime factorizations and . Note that since the fraction is reduced, for all and .

Create a 1-1 correspondence with the positive integers as follows. is paired up with the integer

.

For example is paired with the value .

Likewise, we can go backward—each positive integer is paired with one rational number. For example, the number 360 has prime factorization . Break this up into factors with even exponents and odd exponents ( and ). This implies that the numerator is and the denominator is . So the rational number associated to is .

I am planning to write a follow-up post that showcases less well-known proofs that the real numbers are uncountable.