Enumeration of rationals from Stein-Shakarchi's Real Analysis (Chapter 1, Exercise 24)

Question

The exercise is from Stein-Shakarchi's Real Analysis (Chapter 1, ex. 24).

Does there exist an enumeration $\{r_{n}\}_{n=1}^\infty$ of the rationals such that the complement of $\bigcup_{n=1}^{\infty}{\left(r_{n}-\frac{1}{n},r_{n}+\frac{1}{n}\right)}$ in $\mathbb{R}$ is non-empty. [Hint: Find an enumeration where the only rationals outside of a fixed bounded interval take the form $r_n$, with $n=m^2$ for some integer $m$.]

While, I understand that we probably need some enumeration of the rationals such that the only rationals outside a fixed bounded interval are of the form $r_{m^{2}}$ for some $m$, I'm having trouble seeing how to get such an enumeration.

As always, help is very appreciated :)

Answer 1

Fix some irrational $\alpha$ and any enumeration $\{q_n:n\in\Bbb Z^+\}$ of the rationals. We’ll build a new enumeration $\{p_n:n\in\Bbb Z^+\}$ of $\Bbb Q$ in such a way that for each $n\in\Bbb Z^+$, $\alpha\notin(p_n-\frac1n,p_n+\frac1n)$.

Let $n_1=\min\{n\in\Bbb Z^+:|q_n-\alpha|\ge 1\}$, and let $p_1=q_{n_1}$; clearly $\alpha\notin(p_1-1,p_1+1)$. Let $Z_1=\Bbb Z^+\setminus\{n_1\}$, the set of indices of rationals not yet re-enumerated.

Now suppose that we’ve already defined $p_1,\dots,p_m$ and $Z_m$. Let $$n_{m+1}=\min\left\{n\in Z_m:|q_n-\alpha|\ge\frac1{m+1}\right\}\;,$$ and set $p_{m+1}=q_{n_{m+1}}$ and $Z_{m+1}=Z_m\setminus\{n_{m+1}\}$. Clearly $p_{m+1}$ is distinct from $p_1,\dots,p_m$ and $$\alpha\notin\left(p_n-\frac1n,\,p_n+\frac1n\right)\;.$$

All that’s left is to prove that every rational is eventually enumerated as $p_n$ for some $n\in\Bbb Z^+$. That follows from the fact that at each stage we took the first available rational in the original enumeration; I’ll leave it to you to fill in the details, unless you get stuck and ask for help.

Answer 2

Just for fun, here's a different method:

Let $r_1=2$, $r_2=3$, and $r_3=4$.

Enumerate the rationals in $[0,1]$ by $\{q_k\}_{k\ge 4}$. For $k\ge4$, set $r_{2^k}=q_k$. Define the remaining $r_n$ in an arbitrary fashion.

Then the measure of $[0,1]\setminus \bigcup\limits_{n=1}^\infty(r_n-{1\over n}, r_n+{1\over n})$ is no less than $$\Bigl(1-2\sum\limits_{k=4}^\infty {1\over 2^k}\Bigr)- {1\over 4}- {1\over 5} ={3\over 10}.$$

Answer 3

Following up your idea, enumerate the rationals in $[0,1)$ as $r_n$ and enumerate $\mathbb Z$ as $z_n=(0, 1, -1, 2, -2, \ldots)$. Then we can enumerate all the rationals as $(r_0+z_0, r_1+z_0, r_0+z_1, r_2+z_0, r_1+z_1, r_0+z_2, \ldots)$ as in the proof that pairs of naturals are countable. Now if you consider a unit interval, say $[4,5)$, you should be able to convince yourself that the rationals in that interval are spaced quadratically far apart. You have to worry about spillover from the neighboring intervals, but you can minimize that by taking one far enough from the origin.