Proving that family of fractions is dense in $\mathbb{R}$

Question

Define a set $S=\lbrace{p}\div{2^n}|p\in \mathbb{Z},n\in\mathbb{Z}^+\rbrace$. Prove that $S$ is dense in $\mathbb{R}$.

My attempt: Given two real numbers $a<b$, suppose that there exists $s\in S$ such that $a<s<b$. Then, $2^na<p<2^nb$ for some $p\in \mathbb{Z}$ and $n\in\mathbb{Z}^+$. If there exists $n$ such that $2^n(b-a)>1$, then there exists $p\in\mathbb{Z}$ satisfying the inequality. Solving for $n$, we have $n>\log_2(\frac{1}{b-a})$ and by the Archimedean property, such $n$ must exist which completes the proof.

I have two questions:

$1)$ Is this proof correct?

$2)$ My class has not covered anything about functions yet, so I am reluctant to use $\log(x)$ in a proof. I would like to know if there is a simpler way to prove this.

Answer 1

Here is one way to do it: Let $a<b.$ To show that $S \cap (a,b)\ne \emptyset$:

(1). We have $2^{-n}<b-a$ for all sufficiently large $n\in \Bbb Z^+$ because if $m\in \Bbb Z^+$ with $m> (b-a)^{-1}$ then $m\leq n\in \Bbb Z^+ \implies 2^{-n}<n^{-1}\leq m^{-1}<b-a.$

(2). Let $[a]$ denote the largest integer not exceeding $a.$ For $n\in \Bbb Z^+$ let $i_n = 2^n([a]-1)$ and $j_n=2^n([a]+1).$ We have $i_n2^{-n}<a<j_n2^{-n}.$

Let $k_n$ be the least $m\in \Bbb Z$ such that $a<m2^{-n}.$ (We have, of course, $i_n< k_n\leq j_n.).$ Observe that $\frac {k_n-1}{2^n}\leq a<\frac {k_n}{2^n}.$

(3). By (1) let $n\in \Bbb Z^+$ where $n$ is large enough that $2^{-n}<b-a.$ We have $$\frac {k_n}{2^n}-a\leq \frac {k_n}{2^n}-\frac {k_n-1}{2_n}=2^{-n}<b-a$$ implying $\frac {k_n}{2^n}<b.$ We also have $a<\frac {k_n}{2^n}.$ So $a<\frac {k_n}{2^n}<b.$

Therefore $\frac {k_n}{2^n}\in S\cap (a,b).$

Answer 2

The spirit of your proof is correct.

The following statement:

((Given two real numbers $a<b$, suppose that there exists s∈S such that $a<s<b.$))

implies the existence of $s$ before proving anything.

You are starting from the end and coming back to the beginning.

If you start at :(( There exists n such that $2^n(b−a)>1$ ))

Please redo your proof using the same ideas but in a different order.

Answer 3

Much more than this is true.

The $2^n$ is a MacGuffin: "an object, event, or character that serves to set and keep the plot in motion despite usually lacking intrinsic importance." It could just as well be $n!$ or $n^{n^n}$.

In this case, let $Q$ be an infinite set of positive integers. Then $S=\{\frac{p}{q}|p\in \mathbb{Z},q\in Q\rbrace $ is dense in $\mathbb{R}$.

All that is needed is that, for any $n > 0$ there is a $m \in Q$ such that $m > n$.

What you want is that, for and $r \in \mathbb{R}$ and $\epsilon > 0$, there is a $p \in \mathbb{Z}$ and $q\in Q$ such that $|\dfrac{p}{q}-r| \lt \epsilon$. This is $|p - qr| \lt \epsilon q $.

By choosing $q > \dfrac1{\epsilon}$ and then $p = \lfloor qr \rfloor$, we have $|p - qr| \le 1 \lt \epsilon q $ so $|\dfrac{p}{q}-r| \lt \epsilon$.