I recently came across the set $O=\bigcup_{n=1}^\infty O_n$ ,where $$\mathcal{O}_n = \left(r_n - \frac{\epsilon}{2^{n + 2}}, r_n + \frac{\epsilon}{2^{n + 2}}\right)$$

where {$r_n$} is an enumeration of rationals.The above subset is dense in R and of finite measure. But my question is :

Can we explicitly construct an irrational not in the above set ?

  • $\begingroup$ It would depend on the enumeration to start with. It would be really interesting if such an irrational number was, in fact, non-computable. $\endgroup$
    – user123641
    Feb 19 '14 at 8:17
  • $\begingroup$ @Bryan can you please give an example by taking some enumeration? $\endgroup$
    – happymath
    Feb 19 '14 at 8:46
  • $\begingroup$ Related: math.stackexchange.com/a/475302 $\endgroup$ Feb 19 '14 at 15:05

Let $O=\bigcup_{n=1}^\infty O_n$. If by 'construct' you mean that you can find a computable irrational $q$ such that $q\not\in O$, the answer is interestingly no.

Let $r_n$ represent your sequence of rationals. And let $q$ be an irrational not in $O$. If $q$ were computable there would be a subsequence $r_{n_k}$ of your sequence which converges to $q$ and such that $|r_{n_k}-r_{n_{k+1}}|<\varepsilon 2^{-(n_k+2)}$ for each $k$ (we can assume the subsequence is increasing also). That being said we get that $|r_{n_k}-q|=\sum_{i=k}^\infty |r_{n_i}-r_{n_{i+1}}|<\sum_{i=k}^\infty\varepsilon 2^{-(n_i+2)}=\varepsilon\sum_{i=k}^\infty 2^{-(n_i+2)}<\varepsilon 2^{-(n_k+2)}\sum_{i=1}^\infty 2^{-n_i}<\varepsilon 2^{-(n_k+2)}$.

Thus $q\in(r_{n_k}-\varepsilon 2^{-(n_k+2)}, r_{n_k}+\varepsilon 2^{-(n_k+2)})\subseteq O$.

Thus any such irrational not in your set is non-computable. Since computers can't even compute all computable numbers, let alone noncomputable ones, 'constructing' such an irrational seems out of the question.


The above is incorrect. Not only is there problems with the epsilon-ics, but the statement is also false. You can certainly choose any computable irrational and then find an enumeration of the rationals such that your set avoids that irrational (for any $\varepsilon>0$ in fact).

However, if we can demonstrate an $\varepsilon>0$ and an enumeration of the rationals such that your set contains all the computable numbers, we will be able to conclude that, in general, the answer is no.

That we can do this is fairly clear. Since the computable numbers are countable, we can well order them $\{c_n\}$. And now for each $n$ we just need to pick a rational in $(c_n-\varepsilon 2^{-(n+2)}, c_n+\varepsilon 2^{-(n+2)})$. Since the rationals are computable, we can just choose that rational itself when we come to it. This sequence we construct will not be a strict bijection, but after we construct it we can go through and skip those things we have already chosen. This new sequence will not lack any computable numbers in the union either as the radii only increase. So, in general, you cannot construct an irrational not in your set.

  • $\begingroup$ can you please explain why this subsequence $r_{n_k}$ satisfying the above assumed properties exists $\endgroup$
    – happymath
    Feb 19 '14 at 10:43
  • $\begingroup$ I'm looking at the epsilon-ics, and I can see there is a mistake here, but the idea is the same. I'll rework the computations later if someone else doesn't come through and fix it up. Basically an irrational which satisfies the property you want is erratically spaced away from the rationals. Choosing a rational approximating sequence with even a little bit of order will show that it falls in the union of your sets. $\endgroup$
    – user123641
    Feb 19 '14 at 12:18
  • $\begingroup$ taking $r_1$=0.5 and radius around it as 0.5 then $r_2$=1.25 and radius around it as 0.25 and so on. This sequence converges to 2 but can be made to converge to any irrational.This gives a counter for the property since $r_{n_{k+1}}$ is not in the ball around $r_{n_k}$. $\endgroup$
    – happymath
    Feb 19 '14 at 13:31
  • $\begingroup$ The way I think you're constructing that sequence is not a complete enumeration of the rationals, but I have to say that I am rethinking my answer. If you take any computable irrational, I'm fairly certain you could choose an enumeration of the rationals such that each gets the appropriate radius to avoid that irrational. This is sort of the reverse of your question though. $\endgroup$
    – user123641
    Feb 19 '14 at 14:34
  • $\begingroup$ My goal is now to demonstrate an enumeration of the rationals such that your set contains all the computable numbers, so that you cannot construct an irrational not in the set. $\endgroup$
    – user123641
    Feb 19 '14 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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