Understanding proof that rationals of the form $\frac{p}{2^n}$ are dense in $\mathbb{R}$

Question

Only the following definitions may be used in the proof:

1) A set $X$ is dense in $\mathbb{R}$ if the closure of $X = \mathbb{R}$.

2) The closure of $X$ is $X \cup X'$, where $X'$ is the set of all limiting points of $X$.

3) A limiting point $p \in \mathbb{R}$ is a point which a non-eventually constant sequence in $X$ converges to.

(Let $X$ be the set of rationals of the form $\frac{p}{2^n}$.)

My intuitive idea of density here is that between any two real numbers, there exists some rational number of the form $\frac{p}{2^n}$. But the given definition of density here is set equality, so I have no idea how this definition is equivalent or even remotely related to the intuitive notion of density I just mentioned.

So according to these definitions, I have to show that $X$ including all the convergence points of the non-eventually constant sequences that have terms of the form $\frac{p}{2^n}$, are all the members of $\mathbb{R}$. This seems difficult using only the given definitions but nothing else, but here is the proof that was provided:

For all $x \in \mathbb{R}$ and for all $\epsilon > 0$, it suffices to show that there exists a point in the open interval $(x - \epsilon, x + \epsilon)$ of the form $\frac{p}{2^n}$. (cont'd)

Why does this suffice for our proof?

(cont'd) There exists an $n > 0$ such that $\frac{1}{2^n} < \frac{\epsilon}{2}$. Let $p \in \mathbb{Z}$ be the last such that $\frac{p}{2^n} \leq x$. This means that $\frac{p + 1}{2^n} \geq x$. So either $\frac{p}{2^n}$ or $\frac{p + 1}{2^n}$ must be in the open interval $(x - \epsilon, x + \epsilon)$. Take either $x_n = \frac{p}{2^n}$ or $x_n = \frac{p + 1}{2^n}$. Then $x_n$ converges to $x$, so every point is a limit point. Thus the closure of $X = \mathbb{R}$.

I have no idea what is going on here. How do we know there exists an $n > 0$ such that $\frac{1}{2^n} < \frac{\epsilon}{2}$? How do we know if $\frac{p}{2^n} \leq x$, then $\frac{p + 1}{2^n} \geq x$? Isn't it possible that the rational also depends on $n$, not just $p$? Why are we only worried about $p$ here? How do we know either $\frac{p}{2^n}$ or $\frac{p + 1}{2^n}$ must be in the open interval $(x - \epsilon, x + \epsilon)$? I don't see any conditions restricting both from being less than $x - 2\epsilon$ and greater than $x + 2\epsilon$, so that neither is in $(x - \epsilon, x + \epsilon)$. Then it says we take a sequence to be either of these points, and they converge to $x$ somehow, which I don't see. And then finally it says that every point of $X$ is a limit point, even though we haven't proven that all sequences in $X$ converge to a point in $X$, according to the given definition of limit point.

Answer 1

The closure of $X$ is $X \cup X'$, the union with the limit points as you mention. So fix some $x \in \mathbb {R}$. We want to show it is a limit point of rationals of the form $p/2^r$.

To do this, it suffices to show that for any $\epsilon > 0$, we can find a rational of the form $p/2^r$ within $\epsilon$ of $x$. This is because we can take $\epsilon \to 0$ to get a sequence of rationals converging to $x$, and thus $x$ is a limit point.

There exists an $n$ such that $2^{-n} < \epsilon$ because $2^{-n} \to 0$. Alternatively, and more basically, there is no largest positive integer and for any real number $y$, there is a positive integer $m$ such that $m > y$. This is sometimes called the Archimedian property, and is an axiom of the real numbers (which is sometimes encoded in ordering axioms of the real numbers).

The integers have the well-ordering principle, which says that any set of integers bounded below has a least element (or equivalently, that any set of integers bounded above has a greatest element). This is one of the axioms of the integers (also sometimes encoded in ordering axioms, for what it's worth). So once we've fixed an $n$ such that $2^{-n} < \epsilon$, the integers $p$ such that $p/2^n < x$ is bounded above, and thus has a largest element. Denoting this largest element by $p$, we see that $p+1$ is not in this set, and thus $(p+1)/2^n > x$.

Then the distance between $p/2^n$ and $(p+1)/2^n$ is less than $\epsilon$ and $x$ is in the middle, so that both are at most $\epsilon$ from $x$ (I notice here that you have used $\epsilon/2$ in some places, which I did not. But this changes almost nothing).

Thus for any $\epsilon > 0$, there exists a rational of the form $p/2^n$ within $\epsilon$ of $x$. A sequence of these rationals as $\epsilon \to 0$ gives a convergent sequence of rationals to $x$. As this can be done for every $x \in \mathbb{R}$, we see that $\mathbb{R}$ is contained in the closure of the rationals of the form $p/2^n$. Of course, the real numbers are complete (yet another axiom of the real numbers), so no sequence of real numbers will converge to a nonreal number. Thus $\mathbb{R}$ is the closure of the rationals of the form $p/2^n$.

Answer 2

You ask why this is true:

For all $x \in \mathbb{R}$ and for all $\epsilon > 0$, it suffices to show that there exists a point in the open interval $(x - \epsilon, x + \epsilon)$ of the form $\frac{p}{2^n}$.

Suppose that we’ve shown this; then for each $n\in\Bbb Z^+$ there is an $x_n\in\left(x-\frac1n,x+\frac1n\right)\cap X$. If $\epsilon>0$, there is an $m\in\Bbb Z^+$ such that $\frac1m\le\epsilon$, and it’s clear that $|x-x_n|<\frac1m\le\epsilon$ whenever $n\ge m$. Thus, $\langle x_n:n\in\Bbb Z^+\rangle$ converges to $x$. There are now two possibilities.

• Suppose that $\langle x_n:n\in\Bbb Z^+\rangle$ is eventually constant. Then there is an $m\in\Bbb Z^+$ such that $x_n=x_m$ for all $n\ge m$. Show that this is impossible unless $x_m=x$, in which case $x\in X$.

• Otherwise, $\langle x_n:n\in\Bbb Z^+\rangle$ is not eventually constant, and $x\in X'$.

In either case $x$ is in the closure of $X$.

Now let’s look at the rest of the argument:

There exists an $n > 0$ such that $\frac{1}{2^n} < \frac{\epsilon}{2}$. Let $p \in \mathbb{Z}$ be the last such that $\frac{p}{2^n} \leq x$. This means that $\frac{p + 1}{2^n} \geq x$. So either $\frac{p}{2^n}$ or $\frac{p + 1}{2^n}$ must be in the open interval $(x - \epsilon, x + \epsilon)$.

Let me stop here for now. We’re trying to find a member of $X$ in $(x-\epsilon,x+\epsilon)$. Without worrying for a moment about what $n$ is, consider the possible values of $\frac{p}{2^n}$: they’re evenly spaced in $\Bbb R$ at intervals of $\frac1{2^n}$. If $\frac1{2^n}$ is too big, they could miss the interval $(x-\epsilon,x+\epsilon)$ entirely. This part of the argument is a way to show how to choose $\frac1{2^n}$ small enough so that this doesn’t happen. Specifically, we choose $n$ big enough so that $\frac1{2^n}<\frac{\epsilon}2$. This is actually overkill: his argument works just fine if we take $n$ big enough so that $\frac1{2^n}<\epsilon$, so that’s what I’m going to do. (In fact, taking $\frac1{2^n}<2\epsilon$ is good enough, but it requires a little more work.)

Let $X_n=\left\{\frac{p}{2^n}:p\in\Bbb Z\right\}$, the set of multiples of $\frac1{2^n}$. The idea is that $x$ splits $X_n$ into a left part $X_n^L$ and a right part $X_n^R$: $X_n^L=\{y\in X_n:y\le x\}$, and $X_n^R=\{y\in X_n:y>x\}$. The left part has a biggest element, $\frac{p}{2^n}$. Because this is the biggest element of the left part, the next larger multiple of $\frac1{2^n}$, which is $\frac{p+1}{2^n}$ must be in the right part:

$$\frac{p}{2^n}\le x<\frac{p+1}{2^n}\;.$$

Then $$0<\frac{p+1}{2^n}-x<\frac{p+1}{2^n}-\frac{p}{2^n}=\frac1{2^n}<\epsilon\;,$$

so $$x<\frac{p+1}{2^n}<x+\epsilon\;,$$

and $\frac{p+1}{2^n}\in(x-\epsilon,x+\epsilon)$, as desired. For that matter,

$$0\le x-\frac{p}{2^n}<\frac{p+1}{2^n}-\frac{p}{2^n}=\frac1{2^n}<\epsilon\;,$$

so $\frac{p}{2^n}\in[x,x+\epsilon)\subseteq(x-\epsilon,x+\epsilon)$ as well: we took $\frac1{2^n}$ small enough to get both of these points of $X_n$ inside $(x-\epsilon,x+\epsilon)$. You might like to try showing that if $\frac1{2^n}<2\epsilon$, we can still show that at least one of the two points is in the interval $(x-\epsilon,x+\epsilon)$.

(The author could have been more rigorous about the assertion that $X_n^L$ has a biggest element, but he appears to be willing to use basic consequences of the Archimedean property of $\Bbb R$ without going through the details.)

Now for his conclusion:

Take either $x_n = \frac{p}{2^n}$ or $x_n = \frac{p + 1}{2^n}$. Then $x_n$ converges to $x$, so every point is a limit point. Thus the closure of $X = \mathbb{R}$.

This is very poorly stated; I would simply ignore it and use the argument that I gave to explain ‘it suffices’.

Answer 3

For a direct proof that the rationals of the form $\frac{p}{2^k}$ are dense in $\mathbb R$, here is a simpler proof.

I will denote the integer part of $x$ by $\lfloor x \rfloor$. If $x \in \mathbb{R}$ and not in $X$ the sequence $$ a_{n} =\frac{\lfloor 2^nx \rfloor }{2^n} $$ satisfies $$ \frac{ 2^nx -1 }{2^n} < a_n \leq \frac{2^nx }{2^n} $$ and hence converges to $x$. Since $a_n \in X$ and $x \notin X$ it follows that $x \in X'$.