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

Solution 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.

Solution 2:

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.