# Proof verification for $\mathbb{Q}$ being dense in $\mathbb{R}$ (without the well-ordering principle), 2nd round

One month ago, I tried to prove that $\mathbb{Q}$ is dense in $\mathbb{R}$ without using the well-ordering principle (because, at that point, we didn't have covered it in my lecture) and I already asked for the M.SE community to check if my proof was correct (link here). However, I noticed today that there were other, new mistakes in what we thought was correct, and DonAntonio (who helped me back then) suggested I should create a new post to ask again if, this time, my "new proof" was correct. I would be very happy if anyone could check it out.

So here we go:

We would like to show that for all $x, y \in \mathbb{R}$ such that $x<y$, there exists $q \in \mathbb{Q}$ such that $x<q<y$.

We're going to use:

1. the Archimedean property: for all $x \in \mathbb{R}$, there exists $n \in \mathbb{N}$ such that $n > x$.
2. a consequence of the Archimedean property: if $x > 0$, then there exists $n \in \mathbb{N}$ such that $0 < \frac{1}{n} < x$.
3. the "completeness axiom": any non-empty subset of $\mathbb{R}$ that is bounded below has a greatest lower bound (infimum).

Here is my new attempt:

Since $x<y$ with $x,y \in \mathbb{R}$, we have that $0<y-x \in \mathbb{R}$. Because of the consequence of the Archimedean property, there exists $n_0 \in \mathbb{N}$ such that $0 < \frac{1}{n_0} < y-x$.

Let's now consider the subset $A_0 \subset \mathbb{R}$ defined by:

$A_0:=\{p \in \mathbb{Z} : p > n_0 x \}$

We know that $n_0 x \in \mathbb{R}$ since $x \in \mathbb{R}$ and $n_0 \in \mathbb{N}$. Therefore, because of the Archimedean property, there exists $N \in \mathbb{N}$ such that $N > n_0 x$, which means that $A_0$ is non-empty. Since $A_0$ is non-empty and $n_0 x$ is a lower bound of $A_0$, the completeness axiom tells us that $\inf(A_0)$ exists.

By definition of the infimum:

• $\inf(A_0)$ is a lower bound of $A_0$, which means: $\inf(A_0) \le p$ for all $p \in A_0$
• $\inf(A_0)$ is the greatest lower bound of $A_0$, which means: if $m$ is a lower bound of $A_0$, then $\inf(A_0) \ge m$.

Since $n_0 x$ is a lower bound of $A_0$, we conclude that $\inf(A_0) \ge n_0 x$. Because the first bullet point, we finally have that $n_0 x \le \inf(A_0) \le p$ for all $p \in A_0$.

But: $p$ cannot be equal to $n_0 x$ ($p$ is strictly greater than $n_0 x$). So we actually have either $$n_0 x < \inf(A_0) \le p$$ or $$n_0 x \le \inf(A_0) < p$$

First case: $n_0 x < \inf(A_0) \le p$

In that case, $n_0 x < \inf(A_0)$, which means that $\inf(A_0) \in A_0$. Let us write $\inf(A_0) =: i$. Because $i \in A_0$, we have that $i \in \mathbb{Z}$.

Furthermore, $i-1 \le n_0 x < i$. If it was not the case, i.e. if $i-1 > n_0 x$, then $i$ would not be the smallest element of $A_0$, which would be a contradiction.

So: $$n_0 x < i \Longrightarrow x < \frac{i}{n_0} = \frac{i-1+1}{n_0} = \frac{i-1}{n_0} + \frac{1}{n_0} < x + (y-x) = y$$ So for all $x, y \in \mathbb{R}$ such that $x < y$, there exists $q := \frac{i}{n_0} \in \mathbb{Q}$ such that $x < q < y$. $\square$

Second case: $n_0 x \le \inf(A_0) < p$

In that case, either $\inf(A_0) > n_0 x$, and then the proof follows from what we did just before, or $\inf(A_0) = n_0 x$, and then the proof is the same as the one I did in my first attempt, that is:

(...) $\inf(A_0) = n_0 x$. Therefore, by the completeness axiom, we have:

$\forall \epsilon > 0$, $\exists m \in A_0$ such that $n_0 x +\epsilon > m \ge n_0 x$

And because $n_0 x$ does not belong to $A_0$, we actually have

$\forall \epsilon > 0$, $\exists m \in A_0$ such that $n_0 x +\epsilon > m > n_0 x$.

Because this is true for all $\epsilon$, let's consider, for example, $\epsilon = 1$. We have that $x > \frac{m-1}{n_0}$.

And here comes the conclusion: as $\frac{1}{n_0} < y-x$ and $m > n_0 x$, we have:

$x < \frac{m}{n_0} = \frac{m-1+1}{n_0} = \frac{m-1}{n_0} + \frac{1}{n_0} < x + (y-x) = y$

$\Rightarrow x < \frac{m}{n_0} < y$, with $m \in \mathbb{Z}$ and $n_0 \in \mathbb{N}$. So there exists $q := \frac{m}{n_0} \in \mathbb{Q}$ such that $x<q<y$. $\square$

...FINALLY. The end.

I hope that someone will have the patience to check if it's correct or not. This proof has been haunting me for way too long.

• You might want to extract the part about $\inf A_0$ (i.e., the definition of the ceiling function $\lceil x\rceil$, with the important properties $x\le \lceil x\rceil < x+1$ and $\lceil x\rceil \in\Bbb Z$) into a lemma, mainly because the ceiling function is ineresting and useful in itself. – Hagen von Eitzen Apr 18 '17 at 12:24
• I think you are using a property of $\Bbb Z$ that may be considered non-trivial in this context: "If $n\in\Bbb Z$, then there is no $m\in\Bbb Z$ with $n<m<n+1$." – Hagen von Eitzen Apr 18 '17 at 12:32
• @HagenvonEitzen You're right, I'm using something we've seen during my lecture that I still don't completely understand (that was supposed to be my next question on M.SE, if I were to not find the answer elsewhere first). We've seen that the statement "$i$ is the greatest lower bound of $A_0$" is equivalent to the statement "$\forall \epsilon > 0$, there exists $a \in A_0$ such that $i \le a < i + \epsilon$". I've still not been able to prove why those two statements are equivalent... – justdoit Apr 18 '17 at 12:40
• @HagenvonEitzen I just realized I actually "kinda proved" what I mentioned in my last comment in the proof above. I feel smart and dumb at the same time now. Genius. So: Let $\inf(A_0)=: i$. Then $i \le a$ for all $a \in A_0$. Then $a < i + \epsilon$, because if it was not the case, i.e. if $a \ge i+\epsilon$, then $i$ wouldn't be $\inf(A_0)$. I think that's it. – justdoit Apr 18 '17 at 12:59

This can be simplified as follows. Represent both $x$ and $y$ by unending decimals. Assume first that they are both irrational, so that the number uniquely determines its decimal expansion. Since $x\not=y$, their digits have to be different for a sufficiently high rank. Truncating the unending expansion at that rank gives the desired rational.
If one of the numbers is rational, we can subtract it off both $x$ and $y$ to reduce to the case when one of them is $0$. In that case a similar truncation argument works.
• @alissad, take for example $\pi=3.141592\ldots$. Truncating at the fifth decimal digit gives the number $3.14159$. Any terminating decimal is rational. – Mikhail Katz Apr 19 '17 at 10:16