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.

  • $\begingroup$ 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. $\endgroup$ – Hagen von Eitzen Apr 18 '17 at 12:24
  • $\begingroup$ 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$." $\endgroup$ – Hagen von Eitzen Apr 18 '17 at 12:32
  • $\begingroup$ @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... $\endgroup$ – justdoit Apr 18 '17 at 12:40
  • $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ This is clever. Just one question: can you deduce what you need about decimal expansions without using well ordering, as the OP requires? $\endgroup$ – Ethan Bolker Apr 18 '17 at 12:32
  • $\begingroup$ @MikhailKatz I don't know if it's because of my lack of knowledge about decimal expansions, but I don't understand why truncating the unending expansion should necessarily give a rational number... could you please give an example? :) $\endgroup$ – justdoit Apr 18 '17 at 12:47
  • $\begingroup$ @EthanBolker, the existence of a well-ordering on the reals is a property that requires rather advanced foundational material like the axiom of choice. The approach I outlined is completely constructive and works in ZF or weaker foundational systems. $\endgroup$ – Mikhail Katz Apr 19 '17 at 10:15
  • $\begingroup$ @alissad, take for example $\pi=3.141592\ldots$. Truncating at the fifth decimal digit gives the number $3.14159$. Any terminating decimal is rational. $\endgroup$ – Mikhail Katz Apr 19 '17 at 10:16
  • $\begingroup$ @MikhailKatz I finally got it. That's awesome! Thanks a lot for that answer :) $\endgroup$ – justdoit Apr 19 '17 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.