# How can I show that the set of rational numbers with denominator a power of two form a dense subset of the reals?

How can I show that the set of rational numbers with denominator a power of two form a dense subset of the reals?

-
To show there exists a number of that form in between any two reals, you could expand them in base 2 and consider the first digit where they're different. –  Myself Feb 21 '11 at 8:45

Just expand the reals in base 2. With this convention, the rationals of the form $m/2^r$ will be identified with those reals whose expansion's digit is definitely $0$, i.e. those which have a "finite" expansion.

It is evident that you can get a finitely expanded real as close as you want to any fixed real $r$, just cut away all the digits after the $n$-th, whatever $n$ you choose (exactly as you do with decimal expansions!)

-

This follows immediately from the Archimedian property. To find a dyadic $\rm\ m/2^n \in (r,s)\$ start at at any dyadic $\rm\ k < r\$ (e.g. an integer) and keep taking dyadic step sizes smaller than the interval, say $\rm\ 1/2^j\ <\ s-r\:.\:$ By the Archimedean property eventually you'll land in the interval, necessarily at some dyadic rational (being a sum of such). This is a special case of the proof I explained here.

-

HINT: Given $x \in \mathbb{R}$, how can you use $\frac{\left \lfloor 2^kx \right \rfloor}{2^k}$?

Here $\lfloor \cdot \rfloor$ is the floor function, which in this case sends $2^kx$ to the nearest integer less than or equal to $2^kx$.

The rational numbers whose denominator is a power of two are called dyadic rationals.

-
So if I let $y\leq x$ with $y\leq \dfrac{\lceil 2^{k} y\rceil}{2^k}$ and $x\geq \dfrac{\lfloor 2^{k}x \rfloor}{2^k}$ and there will always exist a k such that $\lfloor 2^{k}x \rfloor = \lceil 2^{k} y\rceil$ ? –  user7485 Feb 21 '11 at 9:52
Recall also that a set $S$ is dense in $\mathbb{R}$ if $A \cup \{ \text{set of limit points of } A\} = \mathbb{R}$. So showing that for any $x \in \mathbb{R}$ there is a convergent sequence of dyadic rationals converging to $x$ proves that they are dense in $\mathbb{R}$. –  milcak Feb 21 '11 at 10:06
Note that you need an integer power of $2$ (otherwise any rational number would be dyadic). If you take $x=100$, $y=1$, then there is no integer $k$ such that $\lfloor 2^k100 \rfloor = 2^k100= \lceil 2^k \rceil=2^k$. There is a natural sequence that converges to $x$ you should think of here. In fact, given my hint, it is the only possible one you can think of. –  milcak Feb 21 '11 at 10:12

A nice sequence that I can think of would be by looking at the convergents of the continued fraction for any given $x \in \mathbb{R}$, and associating a diadic number to each successive convergent, such that the power of two in the denominator is the "closest" value to the denominator of the convergent.

-
maybe try $\left ( \frac{\left \lfloor 2^kx \right \rfloor}{2^k} \right )_{k \in \mathbb{N}}$? –  milcak Feb 21 '11 at 10:46