Show that $S=\{\frac{p}{2^i}: p\in\Bbb Z, i \in \Bbb N \}$ is dense in $\Bbb R$. [duplicate]

Show that $S=\{\frac{p}{2^i}: p\in\Bbb Z, i \in \Bbb N \}$ is dense in $\Bbb R$.

Just found this given as an example of a dense set while reading, and I couldn't convince myself of this claim's truthfulness. It kind of bugs me and I wonder if you guys have any idea why it is true. (I thought of taking two rational numbers that I know exist in any real neighborhood and averaging them in some way, but I didn't get far with that idea..)

Thank you!

marked as duplicate by Adar Hefer, Ayman Hourieh, Cameron Buie, Amzoti, Tom OldfieldAug 9 '13 at 21:13

• $S$ is a proper subgroup of $\mathbb Q$ – mrs Aug 9 '13 at 20:32
• @BabakS. Thanks for the idea, but I'm unfamiliar with group theory at the moment.. I'll read up on the proof for $\Bbb Q$ being dense in $\Bbb R$, I don't remember it at all. Thanks for the ideas! – Adar Hefer Aug 9 '13 at 20:37
• Yes. That is just a small point. I see the tag. See Cameron's idea. – mrs Aug 9 '13 at 20:40
• This has been asked here before. – Pedro Tamaroff Aug 9 '13 at 20:40
• You're right. I didn't find it before, but a "related" question just came up at the right so this is indeed a duplicate. – Adar Hefer Aug 9 '13 at 20:44

Try writing out elements in the set: these are rational numbers whose denominators are powers of $2$. So the elements look like

$$\frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, ...$$

The "gap" between $\frac{n}{2^{m}}$ and $\frac{n + 1}{2^{m}}$ can be made as small as you like by simply letting $m$ be large enough; so if you think of the numbers as points on the line, they can be really close together.

An idea of how to put rigor into this: Let $r \in \mathbb{R}$ and $\epsilon > 0$. Choose $m$ large enough that $\frac{1}{2^m} < \epsilon$ and consider the numbers of the form $\frac{n}{2^m}$. Choosing $n$ correctly will then give

$$|r - \frac{n}{2^m}| < \epsilon$$

which gives density.

• So a good choice of $n$ could be $n= \lfloor {r2^m}\rfloor$, right? – Adar Hefer Aug 9 '13 at 20:41

Suppose not, so that there exist $a,b\in\Bbb R$ with $a<b$ such that for all $p\in\Bbb Z$ and all $n\in\Bbb N,$ we have $\frac{p}{2^n}\le a$ or $\frac{p}{2^n}\ge b$. For each $n\in\Bbb N,$ let $p_n$ the greatest integer $p$ such that $\frac{p}{2^n}\le a.$ (Why must there exist such a $p$?) From this, it follows by hypothesis that $$\frac{p_n}{2^n}\le a<b\le\frac{p_n+1}{2^n}$$ for all $n\in\Bbb N$. But then $$0<b-a\le\frac{p_n+1}{2^n}-\frac{p_n}{2^n}=\frac1{2^n}$$ for all $n\in\Bbb N.$ (Why?) Can you derive a contradiction from this?

• Alright, I think I followed you through. A contradiction would come from taking $n$ large enough so that $a,b$ are arbitrarily close to one another. – Adar Hefer Aug 9 '13 at 20:47
• Loosely speaking, yes, that's the idea. Alternately, rewrite as $$2^n\le\frac1{b-a}$$ for all $n\in\Bbb N,$ whence we've put a real upper bound on the natural numbers (since $n<2^n$ for all $n\in\Bbb N$), which is impossible by the Archimedean property. – Cameron Buie Aug 9 '13 at 20:52

I like to think of the answer intuitively. Represent $p$ in binary (base 2). Then $\frac{p}{2^i}$ is simply a number with finitely many binary digits. Conversely, any number whose binary representation has finitely many digits can be written as $\frac{p}{2^i}$.

To show a set is dense, we have to show that given an element $a$ in the set, we can always find an element $b\neq a$ such that $a$ is arbitrarily close to $b$. As a consequence, the density is infinite: You can find infinite numbers from the set in an unit interval. That's the intuitive meaning of "dense".

If you look at the intuition, it should be clear that the set is dense: You can always find a number that is as close as you want to any other number.