Who proved the rationals are countable? (No fair looking this up.) If you're not sure, guess.
I'm wondering if people know the answer to this one; via some informal surveying it seems less well known that I'd expect. Then again, I didn't know it.
On a related note, the usual proof that N × N is countable (where N = {1, 2, 3, 4, ...} is the natural numbers) goes by giving an explicit enumeration of the pairs of natural numbers, namely,
(1,1), (2,1), (1,2), (3,1), (2,2), (1,3), (4,1), (3,2), (2,3), (1,4), ...
where we list all pairs of integers summing to 2, then to 3, then to 4, then to 5, ... Thus we list pairs of integers in order of their "size". Alternatively, we're enumerating pairs of sets in order of their "size", where sets are only distinguished up to cardinality.
Combinatorialists are often concerned with classes of objects where there are a finite number of objects of size n for any integer n... of course this means that any such class is in fact countable. I don't think I'd heard this stated explicitly, probably because it's not particularly important for doing combinatorics.
For the answer to the question: see the comments.
Subscribe to:
Post Comments (Atom)
11 comments:
I heart Cantor.
Who proved the rationals are countable? I would guess Cantor, since he came up with the idea of countability, after all, and I can't imagine he would have let that question slide. Why, is it someone else?
I second Kelly.
As far as I can tell it's Cantor. That seems to be the standard attribution, and in fact the proof is in Contributions to the Founding of the Theory of Transfinite Numbers, p. 107. (The proof there is actually a proof that the set of ordered pairs of positive integers are countable, but that's the main idea.) But nobody seems willing to just come out and credit this to him; it's always "well, it must have been Cantor, because he [came up with the idea of countability/proved the reals were uncountable/...]"
I always assume that the answer to any question containing the words "who" and "countable" is Cantor.
In fact, Zachary Abel (Harvard) in one of his articles titled "Bert and Ernie" (in the HCMR) points out an explicit enumeration in terms of a rational polynomial (which I think is not very well-known):
p(x, y) = (x+y-2)(x+y-1)/2 + y
Since all natural numbers can be expressed as a power of 2 multiplied by the remaining odd prime factors, you can also use f(x,y) = 2^y(2x+1)-1 as a nice 1-1 correspondence between the natural numbers and an ordered pair.
For enumerating the positive rationals, my favourite method is this: Put one rational at each vertex of an infinite binary tree. At the root, put 1/1=1. At the two children of a vertex where you find m/n with gcd(m,n)=1, put m/(m+n) and (m+n)/n. To prove that all rational numbers appear, and they appear just once, employ the Euclidean algorithm.
Now it only remains to enumerate the vertices of the infinite binary tree. Do so in the obvious order, with number 1 at the root, 2 and 3 below it, 4, 5, 6, 7 below them, then 8, 9,...,15, and so on. The two children of node number n will bear the numbers 2n and 2n+1.
Harald,
I like that enumeration as well. Surprisingly, it has combinatorial significance; see this paper of Calkin and Wilf. Your nth node is b(n-1)/b(n) where b(n) is the number of ways to write n as a sum of powers of two, where each power of two is used at most twice.
You saw Brent's nice post about this counting back in January? In case you didn't: Recounting the Rationals Part III
Jonathan
Post a Comment