A suggested proof of the uncountability (sic) of rational numbers

Question

[Note: I initially made the mistake of posting this over at MathOverflow, where it was promptly closed. There are however some comments there. Link. ]

At MathOverflow, I found a very interesting comment to this question here, about proving the uncountability of the real numbers. I observed that it can be modified to a contradictory statement about rational numbers. (Jump to the end to get to the point.)

(I'm sorry, writing this on a smartphone I find it hard to produce a nicely named link, a good qoute, and a good credit to the quoted author...)

Quoting:

I haven't seen the following proof mentioned, which I learned from Hai Dang at Mississippi State.

Suppose the reals are countable, and let $a_1, a_2, a_3, \dots$ be an enumeration. For each $j$, let $I_j$ be an interval centered at $a_j$ and having length $1 / 2^j$.

Since the sequence $\{a_j\} $ enumerates the reals, it follows that $$ \bigcup_{j=1}^\infty I_j = \mathbb{R}. $$ But since the sum of the lengths of the $ I_j $ is the geometric series $$ \sum_{j=1}^\infty \frac{1}{2^j} = 1, $$ this is nonsense.

Please carefully consider the following modification.

Let $ a_1, a_2, a_3, \dots $ be a complete enumeration of all rational numbers. For each $ j $, let $ I_j $ be an interval of real numbers centered at $ a_j $ and having length $ 1 / 2^j $.

Now, since the rational numbers are dense, and every interval has length $ >0 $, every such interval $ I_j $ includes an infinite number of rational numbers to both sides of $ a_j$. Since every rational number is being enumerated and assigned an interval, it is inevitable that all intervals will overlap with other intervals in both ends, and any gaps are impossible.

It follows that $$ \bigcup_{j=1}^\infty I_j = \mathbb{R}. $$ This is the interval $(-\infty, \infty)$, clearly of infinite size or length (using the standard measure on real intervals).

But at the same time, the sum of the lengths of the $ I_j $ is the sum of the geometric series $$ \sum_{j=1}^\infty\frac{1}{2^j} = 1,$$ and furthermore due to the overlaps, the actual accumulated length will be $ <1 $.

Contradiction! Accumulated length of intervals is infinite and within $[1/2, 1)$.

It seems to me that above is a proof by contradiction that the rational numbers are not countable after all. Or at least, that any set of numbers cannot be both countable and dense.

Comments? Or rather, where is the error?

---

Bonus material: additional food for thought, based on comments to the first post.

Consider putting an $\epsilon$-surrounding (a symmetric interval of size $2\epsilon, \epsilon>0$) around every rational number. Let's say $\epsilon=0.1$ for a start. It should be clear that this covers the real number line completely. Now, is there a limit for this $\epsilon$ where it becomes small enough that the complete coverage is no longer true? I would say no, based on the density of rational numbers and what makes the Dedekind cuts work.

Answer 1

The error is this statement: " Since every rational number is being enumerated and assigned an interval, it is inevitable that all intervals will overlap with other intervals in both ends, and any gaps are impossible."

You haven't proved that, and in fact it's false. The proof works for $\Bbb R$ because every real number is necessarily within (in fact, the center of) one of your countably many intervals (under the assumption that $\Bbb R$ is countable). But how do you know that, say, $\pi$, is within $\dfrac{1}{2^n}$ of any rational number $q_n$? You don't, and you'll find that you can't prove it.

Answer 2

What you have come up with is the proof that the rationals are measure zero, a familiar proof that will come up with any introductory measure theory course (almost surely at least). The issue with your proof is in the step where you conclude that the union covers $\mathbb R$, as a previous answer has mentioned. To show that this fails, it would require a difficult and lengthy construction which depends on the specific enumeration of the rationals you use.

To illustrate this, suppose you try to show that the dyadics in $[0,1]$ are uncountable via your method, let: $$D_n:=\{k2^{-n}: 0 \leq k \leq n\}$$ The dyadics are $D:=\bigcup_{n \geq 0} D_n$. Enumerate $D$ by enumerating each $D_n \backslash D_{n-1}$ and going in sequence, i.e. $0,1,0.5, 0.25,0.75,\dots$

This is indeed a dense set, but also countable, as we just constructed an enumeration. Suppose we call this enumeration: $q_0 = 0,q_1 = 1,\dots$, and now if we center a ball of radius $2^{-m-2}$ around each $q_m$, then by your logic, these balls should cover the unit interval.

However, at each level, $D_n$, given an arbitrary dyadic $q_m=k2^{-n} \in D_n$, and hence there are at least $2^n=\#D_{n-1}$ terms before it in the enumeration. Hence the radius of the ball around each $q_m \in D_n$ is at most $2^{-2^n-2}$. Now we check if we have covered $\frac 13$: the $q_m \in D_n$ which closest approximates $\frac 13$ is either $\lfloor \frac{2^n}3\rfloor 2^{-n}$ or $(\lfloor \frac{2^n}3\rfloor +1)2^{-n} = \lceil \frac{2^n}3\rceil2^{-n}$.

Now we have that the distance from $\frac 13$ to either of those numbers above are bigger than $2^{-2^n-2}$. Indeed, we can prove this with a simple calculation: \begin{align} \left|\lfloor \frac{2^n}3\rfloor 2^{-n} - \frac 13\right| & = \frac 13 - \lfloor \frac{2^n}3\rfloor 2^{-n}\\ & \geq \frac 13 - (\frac{2^n}3 - 1)2^{-n}\\ & = 2^{-n} \geq 2^{-2^n-2}\\ \end{align} And similarly for the other number: \begin{align} \left|\lceil \frac{2^n}3\rceil2^{-n} - \frac 13\right| & =\lceil \frac{2^n}3\rceil2^{-n} - \frac 13\\ & \geq (\frac{2^n}3 + \frac 13)2^{-n} - \frac 13\\ & =\frac 132^{-n} \geq 2^{-n-2}\geq2^{-2^n-2}\\ \end{align} This shows that the intervals which we put around each element of $D_n$ do not cover $\frac 13$, regardless of the $n$, and hence $\frac 13 \not\in \bigcup_{n \geq 0} B(q_n,2^{-n-2})$ and so this does not cover the unit interval.

As a fun side note, if you know some measure theory, it is in fact true that there are uncountably many such numbers which are covered with any cover constructed as such.