Puzzle 6: Solution

Q     [From a recent Mathematics GRE] Is there a well-ordered uncountable set of real numbers?

(Recall that a set is well-ordered when every nonempty subset has a least element. That is, S is well-ordered when every nonempty subset S' of S has an element x smaller than every other element of S'. Every finite set is well-ordered. The classic example of an infinite well-ordered set is {1,2,3,...}, which is infinite but of course only countable.)

A     No.

We shall show that any well-ordered set S of real numbers is countable by writing S as a countable union of subsets S1,S2,S3,..., each of which is countable. (NB we allow finite, even empty, sets to be “countable”.)

For any x in S, define s(x) to be the successor of x, i.e., the smallest element of S greater than x. By our hypothesis on S, this s(x) exists unless x happens to be the largest element of S, in which case we set s(x)=x+1. Now define d(x) = s(x) - x, a positive real number. Thus if we let Sn be the subset of S consisting of x such that d(x)>1/n then each element of S is contained in some (indeed in all but finitely many) of the subsets Sn. Hence S is the union of these subsets. But Sn is clearly countable because |x-x'|>1/n for all distinct x,x' in Sn. Hence S is also countable, as claimed.

Added July 2006: This topic arose on sci.math and Victor Meldrew noted an even simpler proof: for each x in S, choose a rational number r(x) in the interval (x,s(x)); these are distinct, so we have an injection of S into the set Q of rational numbers, which is countable. [Easy exercise: as written, this proof implicitly invokes the Axiom of Choice; explain why in fact Choice is not needed to specify such a map r from S to Q.]

V.Meldrew also notes that by induction any totally ordered countable set has an order-preserving imbedding into Q, and thus into R; in particular this is true for any well-ordered countable set (a.k.a. countable ordinal).