# Is this a valid proof for the existence of a rational number between any two real numbers?

Given $a, b \in \mathbb R$ with $a<b$, prove that there exists some $r \in \mathbb Q$ such that $a<r<b$.

Before I prove the main statement, there's a lemma I'd like to prove:

Lemma

$\forall x, y \in \mathbb R$, if $x-y>1$, then $\exists m \in \mathbb Z$ such that $y<m<x$.

Proof of Lemma

Suppose the negation of the lemma is true. Then $\exists x,y \in \mathbb R$ such that $\forall m \in \mathbb Z$, $m\leq y$ or $m \geq x$.

$m \leq y$ is not possible, because it would imply that $\mathbb Z$ is bounded above in $\mathbb R$. Also, $m \geq x$ is also not possible, because it would imply that $\mathbb Z$ is bounded below in $\mathbb R$. Therefore, the negation of the lemma is false, and hence, the lemma is true.

Proof of main statement

This is equivalent to proving that there exist $p,q \in \mathbb Z$ such that $aq<p<bq$.

Consider $bq-aq = q(b-a)$. Now, $b-a>0$. So, by the Archimedean property, there exists some $q \in \mathbb Z$ such that $q(b-a)>1$, i.e, $qb-qa>1$.

Now, by using the lemma which I proved earlier, $\exists p \in \mathbb Z$ such that $aq<p<bq$, and hence there exists some $r \in \mathbb Q$ such that $a<r<b.$

Q.E.D

A possible pitfall I've realized is if $q<0$, then the inequality above would change to $aq>p>bq$. But since $\dfrac{p}{-q} = \dfrac{-p}{q}$, I can always shift the negative sign to the numerator.

Is this proof correct? Please feel free to nitpick, as I'm still a beginner in proof-writing.

• The proof of the first Lemma is wrong. Note that you don't even assume that $x-y>1$, so your proof exhibits an integer between $\frac1{2}$ and $1$. The negation of the lemma is $\exists x,y. x-y>1 \land \forall m\in\mathbb Z(m\leq y\lor m\geq x)$, not $\exists x,y. x-y>1 \land [(\forall m\in\mathbb Z, m\leq y)\lor (\forall m\in\mathbb Z, m\geq x)]$. Aug 3, 2014 at 7:57
• The proof of the lemma is incorrect but it is the good idea. Just take care to the logical implications : If $\forall m\in \mathbb Z, m\leq y$ or $m\geq x$, it does not imply that $\forall m\in \mathbb Z, m\leq y$ or $\forall m\in \mathbb Z, m\geq x$...
– D.L.
Aug 3, 2014 at 7:57
• Not that your "pitfall" cannot happen: since $b-a>0$ and you seek for a $q$ such that $q(b-a)>1$, one has $q>0$ too. Aug 3, 2014 at 8:12
• Would you believe it? I had the exact same proof in mind, (while going through Rudin's proof which was quite unnecessarily long) right now. Jul 15, 2016 at 18:44

For the lemma, you can simply note that if $x-y>1$ then $x>y+1$.

Then if I note $[]$ the floor function, you have that : $x>y+1>[y]+1>y$, so $m=[y]+1$ is a solution.

### Proof of the Lemma

If you negate the lemma, you get: $\exists x,y\in\Bbb R$, $x-y>1$ such that $\forall m\in\Bbb Z$, $m\le y$ or $m\ge x$.

What you have to point out is that "$m\le y$ or $m\ge y$". It does not mean that ($\forall m\in\Bbb Z$, $m\le y$) or ($\forall m\in\Bbb Z$, $m\ge x$), but $\forall m\in\Bbb Z$, ($m\le y$ or $m\ge x$). You might be mistaken this part.

You have to prove like this: if $x\in\Bbb Z$, $x-1\in\Bbb Z$ and $y<x-1<x$. If $x\not\in\Bbb Z$, $[x]\in\Bbb Z$ and $x>[x]>x-1>y$. Thus we can always find $m\in\Bbb Z$ in $(y,x)$.

### Proof of the main statement

is true.

You only have to fix your proof for the lemma.

Your lemma is correct but the proof is wrong, cosider the case when $x-y< 1$.

According to you:

Then $\exists x,y\in \bf R$ such that $\forall m\in \bf Z$$, m\le y$ or $m\ge x$. $m\le y$ is not possible, because it would imply that Z is bounded above in R. Also, $m\ge x$ is also not possible, because it would imply that Z is bounded below in R. Therefore, there must also exist an integer in between $\bf x$ and $\bf y$.

Suppose x and y as 2 and 3 and then try your lemma, this makes an integer between 2 and 3, but actually there doesn't exist one.

Your reasoning can be backed up with a counterexample to show the non-negation of lemma.

• "Probably you should not make $\forall m\in\mathbf Z$"? What does that mean? The mistake is in how the disjunction is mixed with the universal quantifier, it is not about the range of $m$. This does not qualify as an answer to me. In those proof-checking questions, I'd rather see comments explaining the mistakes and then the OP answering to himself with a correct proof. Aug 3, 2014 at 8:02
• You don't have $3-2>1$...
– D.L.
Aug 3, 2014 at 8:09
• @FPE ..you are right Aug 3, 2014 at 8:10
• yes you dont have $3-2>1$ but the OP's reasoning also implies an integer between 2 and 3 Aug 3, 2014 at 8:10

The other answers should be sufficient to clarify the type of proof you were looking for, but there is a more transparent proof. If you look at truncated decimal expansions of the larger of the two real numbers, then for sufficiently high rank these should be sufficiently close to the larger number so as to be greater than the smaller number, q.e.d.

Note that to use decimal truncations it is convenient to assume that the numbers are positive. This can be achieved by adding a sufficiently large natural number $n$ first, and once a suitable rational has been found, subtracting $n$ off.