Covering the Rationals -- A Paradox?
The following seems to yield a paradox. Can anyone provide the proper resolution?
Preamble
It is easy to show that between any two reals there is a rational. If $\xi1$ and $\xi2$ are real numbers with $\xi2 > \xi1$, there is an integer $n$ large enough such that $1/n < \xi2 - \xi1$. Then for some integer $m$ there must be a rational $m/n$ between $\xi1$ and $\xi2$.
We also know, from Cantor's "diagonal" construction, that the rationals can be sequenced and placed in $1-1$ correspondence with the integers, and so the rationals are countable.
We can use these results to construct the following apparent paradox.
The Covering Process
Suppose we take the interval $[0,1]$ and we order the rationals that lie within this interval. We can cover each rational in the ordering by centering a "mini-interval" of length $\epsilon$ over the first rational, another of length $\epsilon/2$ over the second, another of length $\epsilon/4$ over the third, and so on. (The first, second, etc. rational refer to their Cantor ordering, not their ordering by value.)
Now think about the gaps between these mini-intervals. The number of gaps must be countable as it is initially 1 (treating the whole of $[0,1]$ as a gap) and placing a mini-interval can increase the number of gaps by at most one, which happens if the interval being placed:
- falls entirely inside $[0,1]$, and
- does not overlap any mini-interval previously placed.
Now consider what this covering achieves:
- Every rational is covered.
- Each remaining single gap contains a single irrational, for if it contained two there would be a rational between them and this would be covered, and so it could not be a single gap.
- The amount of the interval $[0,1]$ that has been covered is at most $2\epsilon$, as this is the sum of the length of the mini-intervals. So the portion that remains uncovered is at least $1 - 2\epsilon$.
As we can make $\epsilon$ arbitrarily small, we can make the portion that remains uncovered arbitrarily close to $1$.
A Paradox?
Clearly no single gap can contain a rational (as they are covered) or contain more than a single irrational (as then there would be uncovered rational between them). As we can make the portion of that remains uncovered arbitrarily close to $1$, this appears to require that we can account for an arbitrarily large part of the interval $[0,1]$ using a countable number of single irrational numbers. This appears to be wrong, as a countable set of single numbers is not dense enough to do this. What is wrong? There seem to be four possibilities:
- There is actually no paradox, and it is fine to use a countable number of single numbers to account for an arbitrarily large part of $[0,1]$.
- Because any gap can, at any time during the process, be split into two by having a mini-interval placed inside it and thus "lose its identity", there is no procedure for putting the gaps into 1-1 correspondence with the integers. This means that the gaps, despite the fact that appear to number less than the rationals, are nevertheless uncountable and therefore able to "fill" the exposed part of $[0,1]$. (Perhaps this is a new uncountable infinity, $\aleph_{\small{\textrm{-1}}}$, smaller than $\aleph_{\small{\textrm{0}}}$?)
- The argument is fallacious, in that it is not possible to reason about the situation that pertains after completion of a process that has an infinite number of steps.
- The argument is fallacious for some other reason.
I find the third the most acceptable. However it is interesting to note that, if this is the correct explanation, it casts doubt on other arguments that rely on similar reasoning. For instance, Hilbert's "veridical paradox" that an infinite hotel can never be full: http://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel.
