Covering the Rationals -- A Paradox?

The following seems to yield a paradox. Can anyone provide the proper resolution?


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.


closed as off topic by Joel David Hamkins, Bill Johnson, Simon Thomas, Dmitri Pavlov, François G. Dorais Feb 12 '12 at 13:42

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ I have no idea what to write about that, but usually when coming up with an uncountable $\aleph_{-1}$ which is "smaller than $\aleph_0$" should hint you that you lack the needed understanding of infinities. You should probably start with reading about basic cardinal arithmetic and $\aleph$-numbers. $\endgroup$ – Asaf Karagila Feb 12 '12 at 11:41
  • 1
    $\begingroup$ It is not true that the number of gaps must be countable. Your argument is simply "The number of gaps when the first n mini-intervals have been placed is <= n + 1; therefore, the number of gaps when all the mini-intervals have been placed is countable". But this argument is fallacious. $\endgroup$ – Sridhar Ramesh Feb 12 '12 at 11:49
  • 7
    $\begingroup$ Indeed, instead of using mini-intervals, we might imagine removing single points: removing one rational at a time from [0, 1], we end up with n + 1 many connected components left after the first n many rationals have been removed. But after removing every rational, we are not left with a countable collection of connected components; instead, we are left with an uncountable collection of single points (the irrationals). $\endgroup$ – Sridhar Ramesh Feb 12 '12 at 11:53
  • 13
    $\begingroup$ Sridhar Ramesh has given you exactly the right answer. I want to add that although this question will surely (and appropriately) be closed as too elementary for MO, and although you are in fact making what could fairly be called a "rookie mistake", your careful writeup suggests to me that you've got a lot of talent, a lot of insight, and a lot of genuine intellectual curiosity. I expect you're going to be very good at math. $\endgroup$ – Steven Landsburg Feb 12 '12 at 12:22
  • 4
    $\begingroup$ Even though I voted to close, I agree with Steven's previous comment. $\endgroup$ – Joel David Hamkins Feb 12 '12 at 13:12

There are, in fact, uncountably many gaps between the intervals of your construction. Indeed, the complement $F$ of your open set is (homeomorphic to) a Cantor set. You are correct that it contains no interval. Investigate a write-up of the "Cantor set" itself in a real analysis (or topology) textbook to understand how this is possible.


Not the answer you're looking for? Browse other questions tagged or ask your own question.