Countable Dense Sets

So here’s a problem. Sometimes someone’ll ask me why the real numbers are uncountable. Should I give the somewhat unconvincing diagonalization argument, or the non-empty perfect set argument that I barely understand?

Well I just thought of an argument that I think is fairly simple to understand and, as far as I can tell, mathematically correct. Basically I want to prove the following statement:
If A and B are countable, linearly ordered sets, neither of which has a maximum or minimum element, and they are both dense in the sense that for all a1, a2 in A, there is an a3 in A with a1 < a3 < a2, then A and B have the same order type.

To do this we want to construct an order-preserving bijection between A and B. We can do this recursively. Since A and B are both countable, number the elements a1, a2, … and b1, b2 …. . Call the bijection to be constructed f:A–>B, and assign it values like follows.

For picking f(a[n]), the previous a[1] … a[n-1] box off an interval of A containing a[n] (or really they box off a lot of intervals but we only care about the one containing a[n]) (you can see this is true because they are finite). And because we’ve been careful to keep f({a[1], … a[n-1]}) order-preserving, the corresponding f(a[j]) box off an interval in B that we’re allowed to put f(a[n]) in. And the rule we’ll use is to make f(a[n]) be b[j] for the smallest j corresponding to a point in that box.

– We’ll always have a non-empty box because B is dense;
– f is clearly injective because we only pick from an interval nothing’s been mapped to yet;
– That f is order preserving seems obvious, but I suppose this could be elaborated (if a[i] < a[j], and say i < j, then when f(a[j]) was picked after f(a[i]), so it must be that f(a[i]) < f(a[j]) by the rule we picked with. Similarly if j < i).
– We still need to prove that f is surjective.

So say we have b[j] in B. We want to show that there is an a in A with f(a) = b[j]. We can do that by induction. Clearly f(a[1]) = b[1]. Now say b[1], … b[j-1] have all been mapped to by elements of A. These section off a box containing b[j]. Since f is 1-1, the preimage of this box gives an interval in A. This interval is non-empty (A is dense), so it has a least-numbered element in it, call it a[k]. When f(a[k]) is chosen it must map to b[j] (by the rule we used).

So f is bijective and order-preserving.

Now the real numbers are dense (since a < (a+b)/2 < b) and have no maximum or minimum element. So if they were countable, they would have the same order-type as the rationals (or say the rationals excluding 0, if we don't want to prove the existence of irrationals just now). But they can't, because the defining property of real numbers is the supremum property, which the rationals don't have. So the reals must be uncountable.

So what do you think — is it intuitive enough for dinner-table conversation?

This entry was posted in math. Bookmark the permalink.

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s