# How can we show that the dyadic rationals are dense in $\mathbb R$?

Numbers of the form $\dfrac{m}{2^{n}}$, where $m$ is an integer and $n$ is a non-negative integer, are called dyadic rational numbers.

How can one show that the dyadic rationals are dense in $\mathbb{R}$?

• As written here all dyadic rationals are positive. They can't be dense in $\mathbb R$. Dec 21, 2012 at 9:48
• I have edited the OP's formulation of the problem. Dec 21, 2012 at 10:34

So, basically, we have to show that the set of dyadic rationals are dense in $\mathbb{R}$. For this, if we show that the set $\left\lbrace \frac{m}{2^n}:m\in \mathbb{N}\cup\lbrace 0 \rbrace,n\in\mathbb{N}\text{ and }0\leq m \leq 2^n \right\rbrace$ is dense in $[0,1]$, then we are done. From this, one can easily extend $\textit{denseness}$ of the above numbers from $[0,1]$ into whole $\mathbb{R}$.

For the above purpose, let $\epsilon >0$, and let $x\in[0,1]$. From the Archimedean property, there is $n\in\mathbb{N}$ such that $\frac{1}{2^n}<\epsilon$. Let $m=\lfloor x\cdot2^n \rfloor$ where $\lfloor\cdot\rfloor$ represents Floor function. Then it is clear that $0\leq m \leq 2^n$. From the usual properties of Floor function, we have $$m=\lfloor x\cdot2^n \rfloor \leq x\cdot2^n \leq m+1=\lfloor x\cdot2^n \rfloor+1$$, i.e., $$\frac{m}{2^n}\leq x\leq \frac{m+1}{2^n}$$, i.e., $$0\leq x-\frac{m}{2^n}\leq \frac{1}{2^n} <\epsilon$$ which is exactly the statement we want to prove. Thus the set $\left\lbrace \frac{m}{2^n}:m\in \mathbb{N}\cup\lbrace 0 \rbrace,n\in\mathbb{N}\text{ and }0\leq m \leq 2^n \right\rbrace$ is dense in $[0,1]$. Now just extend this to whole $\mathbb{R}$.

Hint: if I walk from left to right on the real line taking steps of fixed length $\delta > 0$ and start to the left of some interval $I = (a,b)$, then if $\delta < b-a$, I must set foot in the interval $I$.

• +1 This is as simple and nice a hint as I can think of, though it is almost the whole solution. Dec 21, 2012 at 9:56
• Sir, yes we must set foot in the interval $I$ but how this hint useful to answer OP question? I didn't get the hint. Please help me or @DonAntonio sir can you help in this please? Oct 28, 2020 at 5:54
• @AkashPatalwanshi .Let $\;a<b\;$ and let $\;m\;$ be the first integer such that $\;m\le a\;$. Suppose $\;|[a,b]|=b-a=\delta\;$, and begin walking from $\;m\;$ rightwards taking steps of length $\;\delta\;$ . Then, you step on the points $\;m\,,\;m+\delta\,,\;m+2\delta\,,\;\ldots\;$ . Since $\;(m+n\delta)\xrightarrow[n\to\infty]{}\infty\;$ because $\;\delta>0\;$ and since the difference between consecutive steps is $\;\delta\;$, the exists $\;k\in\Bbb N\;$ ,such that $\;m+k\delta\in (a,b)\;$. Can you see it now? Now take $\;r\in\Bbb N\;$ s.t. $\;2^{-r}<\delta\;$ and etc. Oct 28, 2020 at 7:45
• @DonAntonio no sir still i didn't get it. Taking $(a,b)=(2,3)$ in your comment. We see that $\delta =1$ and $m=2$. Now being walking from $m=2$ rightwards taking steps of length $\delta=1$, we step on $2,3,4,5,...$. Then how can be there is $k\in\mathbb{N}$ such that $2+k(1)\in (2,3)$ ? Please explain? Further please elaborate what is reason for doing so? ... Oct 28, 2020 at 10:18
• Nop. Take for example $\;\delta=0.8\;$ , then begin with $\;2,\,2.8,\,...\;$ and we're done! This is the hint of Pete. Oct 28, 2020 at 10:56

Hint: show that for any non-empty open interval $\,(a,b)\,$ there exist $\,m,n\in\Bbb Z\,$ s.t. $\,\displaystyle{\frac{m}{2^n}\in(a,b)}\,$ (why is this enough?)

HINT: Let $x,y\in\Bbb R$ with $x<y$. There is an $n\in\Bbb N$ such that $2^{-n}<y-x$. Show that $(x,y)$ must contain an integer multiple of $2^{-n}$ and therefore some dyadic rational with denominator $2^m$ for some $m\le n$.

• Sir, i got upto your first line. How to show that, $(x,y)$ 'must' contains integer multiple of $\frac{1}{2^n}$ Oct 27, 2020 at 3:42
• @AkashPatalwanshi: Let $\frac{k}{2^n}$ be the largest multiple of $2^{-n}$ that is $\le x$, and let $\frac{\ell}{2^n}$ be the smallest multiple of $2^{-n}$ that is $\ge y$. Then $$\frac{\ell-k}{2^n}=\frac{\ell}{2^n}-\frac{k}{2^n}\ge y-x>\frac1{2^n}\,,$$ so $\ell>k+1$, and $\frac{k+1}{2^n}\in(x,y)$. Oct 27, 2020 at 3:46
• Thank you so much for replying sir. $\frac{k+1}{2^n}\in(x,y)$ because $\ell>k+1$ and by "definition of $k$ and $\ell$? Oct 27, 2020 at 4:13
• @AkashPatalwanshi: You’re welcome. Yes: $\frac{k+1}{2^n}$ must be in the interval $(x,y)$. Oct 27, 2020 at 4:24

Show that the smallest closed set containing the set of all such dyadic numbers is $\mathbb{R}$. Specifically: any arbitrary open neighborhood $U$ of a real number $q$ not dyadic must intersect nontrivially with the set of all dyadic numbers. So $q$ is a limit point. Can you show why the intersection contains something other than $q$?

We have that if $$A \subset B \subset C$$ and $$A$$ is dense in $$B$$ and $$B$$ is dense in $$C$$, then $$A$$ is dense in $$C$$.

We also have that rationals ($$B$$) are dense in $$\mathbb{R}$$ ($$C$$), so we only have to show that the dyadic rationals ($$A$$) are dense in the rationals.

Given a rational number $$\frac{p}{q}$$ consider the sequence $$\left\{ \frac{\left\lfloor 2^n \frac{p}{q} \right\rfloor}{2^n} \right\}$$ which converges to $$\frac{p}{q}$$.

You can also show it this way if you know the following theorem:

$$\textbf{Theorem}$$:

Let $$(\mathbb{R},\mathcal{T}_{\mathbb{R}})$$ be the standard real space. Let $$(G,+|_{G\times G})\leq(\mathbb{R},+)$$ be a subgroup where $$+$$ is the standard addition on the real number. Then exactly one of the following holds:

$$G=\{0\}$$ or $$G=inf(G\cap]0,+\infty[)\cdot\mathbb{Z}$$ or $$\overline{G}^{\mathcal{T}_{\mathbb{R}}}=\mathbb{R}$$ (i.e. G is dense)

we can summarize this result by saying that additive subgroup of the real numbers are either cyclic or dense (but not both obviously).

Knowing this result, call the dyadic rational set $$\mathcal{D}:=\{\frac{m}{2^{n}} : m\in\mathbb{Z}, n\in\mathbb{N}\}$$ then:

$$(\mathcal{D},+|_{\mathcal{D}\times\mathcal{D}})\leq(\mathbb{R},+)$$ (straightforward verification) thus the theorem applies. But:

• $$\mathcal{D}\neq\{0\}$$

• $$\mathcal{D}$$ is not cyclic: if it was then it would be of the form $$\mathcal{D}=\alpha\cdot\mathbb{Z}$$ with $$0\overset{\mathcal{D}\neq\{0\}}{<}|\alpha|=\frac{|r|}{2^k}\in\mathcal{D}$$ for some $$k\in\mathbb{N}$$ and $$r\in\mathbb{Z}$$ then $$\alpha=min(\mathcal{D}\cap]0;+\infty[)$$ but clearly $$\frac{|r|}{2^{k+1}}\in\mathcal{D}\cap]0;+\infty[$$ and $$\frac{|r|}{2^{k+1}}<\frac{|r|}{2^{k}}=\alpha$$ which contradicts the minimality of $$\alpha$$.

So the only left option is that $$\overline{\mathcal{D}}^{\mathcal{T}_{\mathbb{R}}}=\mathbb{R}$$.