9
$\begingroup$

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} $?

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

7 Answers 7

20
$\begingroup$

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}$.

$\endgroup$
12
$\begingroup$

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$.

$\endgroup$
6
  • 4
    $\begingroup$ +1 This is as simple and nice a hint as I can think of, though it is almost the whole solution. $\endgroup$
    – DonAntonio
    Dec 21, 2012 at 9:56
  • $\begingroup$ 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? $\endgroup$ Oct 28, 2020 at 5:54
  • $\begingroup$ @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. $\endgroup$
    – DonAntonio
    Oct 28, 2020 at 7:45
  • $\begingroup$ @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? ... $\endgroup$ Oct 28, 2020 at 10:18
  • 1
    $\begingroup$ Nop. Take for example $\;\delta=0.8\;$ , then begin with $\;2,\,2.8,\,...\;$ and we're done! This is the hint of Pete. $\endgroup$
    – DonAntonio
    Oct 28, 2020 at 10:56
10
$\begingroup$

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?)

$\endgroup$
1
  • $\begingroup$ Sir, can you please help to prove the hint( assertion) in your answer. $\endgroup$ Oct 27, 2020 at 3:24
9
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Sir, i got upto your first line. How to show that, $(x,y)$ 'must' contains integer multiple of $\frac{1}{2^n}$ $\endgroup$ Oct 27, 2020 at 3:42
  • 2
    $\begingroup$ @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)$. $\endgroup$ Oct 27, 2020 at 3:46
  • $\begingroup$ 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$? $\endgroup$ Oct 27, 2020 at 4:13
  • 1
    $\begingroup$ @AkashPatalwanshi: You’re welcome. Yes: $\frac{k+1}{2^n}$ must be in the interval $(x,y)$. $\endgroup$ Oct 27, 2020 at 4:24
2
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .