# Proving that rational numbers are dense

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.

• That's a much stronger statement that the rational numbers are dense. And look in Niven's number theory book for the proof. – Matthew Leingang Jan 22 '15 at 1:39

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.

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.

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.