# Enumeration of rationals from Stein-Shakarchi

The exercise is from Stein-Shakarchi's Real Analysis (Chapter 1, ex. 24). It asks about an enumeration of the rationals $\left\{r_{n}\right\}_{n\geq 1}$ 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.

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 :)

-

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.

-
Expressed somewhat more succinctly: for each positive integer $n$, take the first rational (in your first enumeration) with distance more than $1/n$ from $\alpha$ that has not yet been enumerated. Somewhat more generally, you can get that complement to contain any closed set of irrationals. –  Robert Israel Mar 12 '12 at 16:51
This is a really beautiful solution! And way more natural than the one I was thinking about with the perfect squares. Thanks –  Anna Mar 12 '12 at 16:58

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}.$$

-

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.

-

I think the way this problem was intended to be solved is as follows, though it is similar to one above. And it's short. We denote all rationals in $[0,1]$ as $\{p_{n}\}$ and those in $\mathbb{R}-[0,1]$ as $\{q_{n}\}$. Now let's construct $\{r_{n}\}$ as follows: if n is a square of some integer, we take the next one in $\{q_{n}\}$; otherwise we take the next one from $\{p_{n}\}$. It is easy to proof that $\cup(r_{n}-\frac{1}{n},r_{n}+\frac{1}{n})\subset[-1,2]\cup(\cup(q_{n}-\frac{1}{n^{2}},q_{n}-\frac{1}{n^{2}}))$. Take summation we will find the right side has finite measure.

-