Spring 2010

I'm enrolled in two Computer Science courses: CS 6505 for an unneeded grade, and CS 6520 for fun.

In CS6505 on Friday, I was asked to show the rationals are countable. Having seen this problem before, I quickly mapped the rationals onto discrete points in a 2D plane and, while waving hands, showed how they could be counted by spiralling outward from the origin. "There are different classes of infinity," I struggled to explain. The three gentlemen I was sitting with were not necessarily convinced I had done any math or that my explanation was adequate, so I cast about for a better method.

Here it is. Recall that N is the set of natural numbers: {1, 2, 3, ..}, integers are the set Z = {.., -2, -1, 0, 1, 2, ..}, and the rational numbers are numbers that are the ratio of an integer to a natural number. A set is countable iff there exists a mapping to the natural numbers.

Finite sets are of course countable, but showing that infinite sets are countable requires a bit more thought. The integers, for example, may be mapped to natural numbers as follows: let "0" be integer number 1, +1 be integer number 2, -1 be integer number 3, +2 be integer number 4, -2 be integer number 5, and so on. Easy.

Now for the rationals. Consider an integer a represented by the bits (a0 a1 a2 .. an), where a0 is 0 if a is positive and 1 if a is negative, while bits (a1 a2 .. an) denote the absolute value of a. Assume b is an n-bit natural number formed by bits (b1 b2 .. bn). The pair (a, b) represents some rational number. We may now form a string from the bit representation of (a, b) as follows:

(1 a0 a1 b1 a2 b2 a3 b3 .. an bn)

This binary string maps to a unique natural number. Moreover, we see that the set ZxN is a superset of the rationals (-10/5 and -2/1 are the same rational number but distinct in the superset ZxN). Because each element of this superset maps to a unique natural number, it is countable, and therefore the rationals are countable. qed.

My personal take-aways from this experience: (1) writing things down like this rather than drawing visual aids and pointing seems to make people more comfortable, and (2) trying to show something in two slightly different ways is a good exercise.