Posted by: Dave Richeson | September 11, 2009

Cardinality of infinite sets, part 1: four nonstandard proofs of countability

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:

\begin{array}{ccc}1&\to& 0\\2&\to& -1\\3&\to& 1\\4&\to &-2\\5&\to& 2\\6&\to &-3\\7&\to& 3\\\vdots&&\vdots\end{array}

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: x_1, x_2, x_3,\ldots 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 a/b, place the two rational numbers a/(a+b) and (a+b)/b. Part of the tree is shown below.

cwtree

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 nth denominator is the number of ways to write n as powers of two in which each power of two is allowed at most twice. (For example, when n=6 we have a denominator of 3 because 6=4+2=4+1+1=2+2+1+1.)

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 A_1, A_2, A_3,\ldots are finite, then we can list \bigcup_{n=1}^\infty A_n by listing the elements of A_1, followed by the elements of A_2, A_3, A_4, and so on (removing duplicates, if any).

Let A_n=\{\pm p/q: p/q\text{ is reduced, and }p+q=n\}. For example, A_1=\{0/1\}, A_2=\{1/1, -1/1\}, A_3=\{1/2,-1/2, 2/1, -2/1\}, etc. Clearly each such set is finite. Moreover \bigcup_{n=1}^\infty A_n 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 A_n be the set of words of length n. Each A_n is finite (if there are m letters in the alphabet, then A_n has m^n words). Reasoning as before, \bigcup_{n=1}^\infty A_n 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 \{-,/,0,1,2,3,4,5,6,7,8,9\}. For example, we have rational numbers 5, 1/2, -22/7.

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 \{+,-,/,(,),\wedge,0,1,2,3,4,5,6,7,8,9\}. For example, \displaystyle\sqrt[3]{5-4\sqrt[5]{\frac{2}{3}}} can be written as (5-4(2/3)\wedge(1/5))\wedge(1/3).

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, \pi, e, \int_1^\infty e^{-x^2}\,dx, and “the smallest positive root of the function x^3-x\sin(x^4-x+\tan(x))+\pi-\frac{\sqrt{2}}{x}.”

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 m/n where m and n are relatively prime. Suppose they have prime factorizations m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r} and n=q_1^{b_1}q_2^{b_2}\cdots q_s^{b_s}. Note that since the fraction is reduced, p_i\ne q_j for all i and j.

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

p_1^{2a_1}p_2^{2a_2}\cdots p_r^{2a_r}q_1^{2b_1-1}q_2^{2b_2-1}\cdots q_s^{2b_s-1}.

For example 22/7 is paired with the value 11^2 2^2 7^1=3388.

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

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

About these ads

Responses

  1. Check out a children’s book called The Cat in Numberland, where the Hilberts are the innkeepers at the Hotel Infinity, and the cat wonders how it happens.

    • I’ve never heard of that book. Thank you for letting me know. I remember learning about Hilbert’s Hotel when I was in high school or junior high school from Martin Gardner’s “Aha Gotcha!” book. At the time it seemed like he was cheating, but I couldn’t put my finger on the problem.

      I must admit that I’m a little disappointed to have been scooped on this idea. I’ve been saying to my friends for the last few years that I wanted to write a children’s book about infinity (although I think it would be highly unlikely that I’d ever follow through on the idea).

  2. I’ve often thought that the process of learning about countability, uncountability, and transfinite numbers is a lot like the Zen story of the bowl and tea:

    “Before enlightnement, the bowl is a bowl and tea is tea. In the process of achieving enlightenment, one discovers that the bowl is not a bowl, and tea is not tea. After enlightenment, the bowl is again a bowl, and tea is again tea.”

    When you first start thinking about numbers like this, confusion sets in – the familiar numbers that you’ve known since childhood are suddenly changed.

    Personally, I didn’t find countability to be too much of a problem, but what I did struggle with was how we construct numbers out of sets and cuts and equivalence classes etc. Recently I’ve been reading Conway’s ONAG (http://books.google.com/books?id=tXiVo8qA5PQC), and bowls are not bowls again for me right now. What do you think of using Conway’s approach in teaching undergrads? Is it ever done?

    • That’s a great analogy.

      In our particular course we aren’t going to construct the real numbers. Instead, we just assume the axiom of completeness. Abbott’s book does have the construction (using Dedekind cuts), but sticks it at the very end of the book. We’re not going to get there.

      I have actually never read about Conway’s surreal numbers. It is on my to-do list. I know that they are an extension of the reals to include infinity and infinitesimals, but I don’t know much more than that.

      • If for no other reason than to further whet your appetite, the surreal numbers can actually be used to model types of combinatorial games (i.e. games with finitely many moves and perfect information). Then “surreal arithmetic” can be used to solve several game theory problems… and vice versa!

  3. [...] appearing once and only once, in reduced form. I originally saw it mentioned on Division by Zero here (along with a bunch of other great non-standard proofs), Calkin and Wilf’s original published [...]

  4. [...] and its connection to the rational numbers before, but to recap: I first came across it on Division by Zero (still waiting for the rest of that series) and the original paper by Calkin and Wilf is [...]

  5. [...] The rational numbers are countable [...]

  6. [...] be showing my Discrete Math class how to “count” the positive rational numbers. (See this old blog post for more information about countable sets.) I used TikZ to create the picture [...]

  7. Some infinities are bigger than other infinities.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 200 other followers

%d bloggers like this: