Show that $S=\{\frac{p}{2^i}: p\in\Bbb Z, i \in \Bbb N \}$ is dense in $\Bbb R$. 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!
 A: 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?
A: 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.
A: 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.
