False Proof – The Reals are Countable

It seems that false proofs are quickly becoming some of the most popular posts on Math ∩ Programming. I have been preparing exciting posts on applications of graph coloring, deck stacking, and serial killers. Unfortunately, each requires resources which exist solely on my home desktop, which is currently dismantled in California while I am on vacation in Costa Rica. Until I return from the tropics, I will continue with more of the ever -popular false proofs.

Problem: Show the real numbers \mathbb{R} are countable. [For a primer on set theory and countability, see our post on the subject].

“Solution”: Recall from our post on well-orderings that every set has a well-order (assuming the axiom of choice). So \mathbb{R} has a well-ordering. Call it <. Recall additionally that by the definition of a well-order, every nonempty subset of \mathbb{R} has a least element with respect to <. We construct a sequence x_i \in \mathbb{R} that uses this well-order in the following way:

Let x_1 be the smallest element of \mathbb{R} with respect to <. Let x_2 be the smallest element of \mathbb{R} - \left \{ x_1 \right \}. Let x_i be the smallest element of \mathbb{R} - \left \{ x_1, x_2, \dots, x_{i-1} \right \}.

Define f: \mathbb{N} \to \mathbb{R} by f(i)=x_i. Clearly this map is injective, and we argue that it is surjective because any element y \in \mathbb{R} is the smallest element of the subset of \mathbb{R} that contains strictly greater elements with respect to <. So this map is a bijection, and the reals are countable.

Explanation: The reader should be extremely wary of this argument, because it does not only claim that the reals are countable. If the argument above held, then we could apply it to any set (since every set has a well-order!). So something is definitely fishy here.

The problem with analyzing this argument is that the well-order of the reals is not known explicitly. However, our noses point us to recognize that the only place a flaw could exist is in the claim of surjectivity.  We prove the falsity of the above argument now, by proving that the same argument fails to show the integers \mathbb{Z} are countable with respect to a well-order of our choosing.

Define a well-order <_{\xi} on \mathbb{Z} by letting non-positive numbers be larger than all positive numbers, and ordering negative numbers by increasing absolute value. In other words, we order the integers like 1,2, \dots, n, \dots, 0, -1, -2, \dots, -n, \dots. We leave it as an exercise to the reader to prove <_{\xi} is a well-order.

Notice that with the argument above, we never choose -1, or any negative number, as an x_i. Specifically, the sequence of x_i is precisely the natural numbers. Hence, we cannot enumerate all of \mathbb{Z} in this fashion. Clearly the argument fails for \mathbb{R} as well.

This false proof is significant in that we get some intuition about well-orders. In particular, a function from the natural numbers to a set S is also a way to “order” S. However, a well-order is more general and more expressive than a bijection from \mathbb{N} \to S, in that we can construct such an order on any set. As we have seen, with a well-order we don’t have to worry about a contiguous sequence of elements from smallest to greatest. We are allowed the power to say “all of these guys are bigger than all of these guys,” regardless of how many are in each group.

And, as always, with more power comes the responsibility to manage counter-intuitive results, either by accepting them through rigorous proof or rejecting false constructions like the one above.


2 thoughts on “False Proof – The Reals are Countable

  1. “non-negative numbers be larger than all positive numbers”

    You seem to’ve meant non-positive instead of non-negative there.

    “However, a well-order is more general and more expressive than S, in that we can apply it to any set.”

    Instead of S here maybe you meant `a bijection from N’, but likely needs different fixing.

    Nice collection though


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