Proving that rational numbers are dense

Question

I am trying to show that for any real number a, there exist infinitely many rational numbers m/n with $ |a - m/n| < 1 /n^{2} $. I've tried to attempt the question by assuming there are finite rational numbers and finding a contradiction.

Answer 1

Try to show that for every real number $a$ and every positive integer $N$ there exist $p,q$ integers with $1 \le q \le N$ such that $|qa - p| \le 1/(N+1)$.

This can be shown just using the pigeonhole principle in a clever way.

The result is called Dirchlet's approximation theorem. In this way you could easily find more detailed information in case it is needed.

Answer 2

There might be simpler ways to prove this, but the only way I know how to do this is via the following theorem (which makes use of the pigeonhole principle):

Theorem. Now show that given any positive integer $Q$ we may find positive integers $p, q$ with $1\leq q\leq Q$ and such that $|x-p/q|\leq 1/(qQ)\leq 1/q^2$.

Proof. Let $Q$ be any positive integer. Consider a list of $Q+1$ terms $a_0,\dotsc, a_{Q}$ where $a_k=kx-\lfloor kx\rfloor$ for $k=0, 1,\dotsc, Q$. Note that each $a_k$ is the decimal part of $kx$, so $a_k\in [0,1)$. We divide $[0,1)$ into $Q$ parts: $$[0,1)=\bigcup_{n=0}^{Q-1}\left[\frac{n}{Q}, \frac{n+1}{Q}\right)=\left[0, \frac{1}{Q}\right)\cup\left[\frac{1}{Q}, \frac{2}{Q}\right)\cup\dotsm\cup\left[\frac{Q-1}{Q}, 1\right).$$ Since there were $Q+1$ terms in our list and we divided $[0,1)$ into $Q$ parts, the pigeonhole principle implies at least one of our subintervals contains two terms, which we label $a_i$ and $a_j$. Without loss of generality, assume $i>j$. Each subinterval has length $1/Q$, so $|a_i-a_j|<1/Q$. Thus,

\begin{align*} |a_i-a_j| &=\left|(ix-\lfloor ix\rfloor)-(jx-\lfloor jx\rfloor)\right| \\ &=\left|(i-j)x-(\lfloor ix\rfloor-\lfloor jx\rfloor)\right|<1/Q. \end{align*}

Define $p:=\lfloor ix\rfloor-\lfloor jx\rfloor$ and $q:=i-j$. Then $1\leq q\leq Q$ and $$|xq-p|<\frac{1}{Q}\implies \left|x-\frac{p}{q}\right|<\frac{1}{Qq}\leq \frac{1}{q^2}.$$

EDIT: After all that work, I kind of lost sight of the question at hand. If there were finitely many rationals $p_i/q_i$ satisfying the inequality, we could find a positive integer $m$ such that $$\frac{1}{m}<\left|x-\frac{p_i}{q_i}\right|.$$ Now let $m=Q$ in our theorem above, and find the corresponding pair of integers $a,b$. You should be able to show that $a/b$ was not one of our original $p_i/q_i$ from there, a contradiction.

Answer 3

Consider any point $x$ on real line. An open sphere centered at $x$ with radius $r$ is an open interval of radius $2r$. Let the open interval be $(a,b)$. Let the binary representations be

$a=a_1,a_2,\cdots, a_n, \cdots$

$b=b_1,b_2,\cdots, b_n, \cdots$

For every such numbers we can find an intermediate binary representation having finite digits. This corresponds to a rational number. So every real number is a limit for set of rationals showing that set of rationals is dense.

Suppose $m$ is the last integer such that $a_m = b_m$. As $b>a$, $b_{m+1}=1$, $a_{m+1}=0$. If for all $n>m$ the $a_n=1$ and $b_n=0$ then a=b so $(a,b)$ will not be an interval.

Therefore we have three possibilities, In each case we can find a binary number lying between them having a finite number of digits and thus representing a rational number. 1)

$a=a_1,a_2,\cdots, a_m, 0 ,1 \cdots 0, a_{n+k}$

$b=b_1,b_2,\cdots, b_m, 1, 0 \cdots 0, b_{n+k}$

$c=a_1,a_2,\cdots, a_m, 0,1 \cdots 1$

2)

$a=a_1,a_2,\cdots, a_m, 0, 1 \cdots 1, a_{n+k}$

$b=b_1,b_2,\cdots, b_m, 1, 0 \cdots 1, b_{n+k}$

$c=a_1,a_2,\cdots, a_m, 1, 0 \cdots 0$

3)

$a=a_1,a_2,\cdots, a_m,0, 1 \cdots 0, a_{n+k}$

$b=b_1,b_2,\cdots, b_m,1, 0 \cdots 1,b_{n+k}$

$c=a_1,a_2,\cdots, a_m, 0, 1 \cdots 1$

Here we have not explicitly written about the case $a_m,0,1..$ and $b_m,1,1$ or $a_m,0,0..$ and $b_m,1,0$ but that can be dealt with by removing the digits $a_{m+2}$ and subsequent dots in above explanation.