# Proof that there are infinitely many positive rational numbers smaller than any given positive rational number.

I'm trying to prove this statement:- "Let $x$ be a positive rational number. There are infinitely many positive rational numbers less than $x$."

This is my attempt of proving it:-

Assume that $x=p/q$ is the smallest positive rational number.

Consider $p/q - 1$ $= (p-q)/q$

Case I: $p$ and $q$ are both positive

Then, $p-q<p$

And hence, $(p-q)/q < p/q$

Since $p$ and $q$ are integers, $(p-q)$ is also an integer. Thus, $(p-q)/q$ is a rational number smaller than $p/q$. Therefore, our assumption is wrong, and there always exists a rational number smaller than any given rational number $x$.

Case II: $p$ and $q$ are both negative

Then, let $p/q = -s/-t$, where $s$ and $t$ are both positive integers.

Then, $-s-(-t)>-s \implies (-s+t)/-t < -s/-t \implies (p-q)/q <p/q$

Since $p$ and $q$ are integers, $(p-q)$ is also an integer. Thus, $(p-q)/q$ is a rational number smaller than $p/q$. Therefore, our assumption is wrong, and there always exists a rational number smaller than any given rational number $x$.

Q.E.D

Is my proof correct? And there are a couple of questions that I've been pondering over:-

1) How do I justify the subtraction of $1$ from $p/q$? I mean, I assumed that $p/q$ is the smallest rational number, so how do I even know if this operation is valid?

2) I proved that there always exists a smaller rational number given any positive rational number. But how do I prove that there's always a smaller positive rational number?

3) Also, I don't seem to have proved that there are infinitely many smaller rational numbers than $x$. If I use a general integer $k$ instead of $1$, this would be taken care of, right? But then again, how do I justify this subtraction?

I'd be really grateful, if someone could help me with this! Thanks!

-
Up-voted for demonstrating substantial effort. –  dfeuer Jun 25 '13 at 0:19
I haven't looked at your proof, because it seems very long and there is a shorter way to do it. For a given positive rational $x$, take integer $N$ such that $\frac1N <x$ (possible by Archimedes theorem if you want to be totally rigorous) $x_n=x-\frac1n$ is always rational for integer $n$, and is always positive for $n\geq N$, so now you have infinitely many positive rationals smaller than $x$. –  Tom Oldfield Jun 25 '13 at 0:20
@TomOldfield: That's a slick proof there, thank you! I hadn't even thought of using the Archimedean property for this. –  Jobin Idiculla Jun 25 '13 at 0:33
Or another option take half of the smallest positive rational. –  Baby Dragon Jun 25 '13 at 5:24
@BabyDragon I'm not a maths expert, but when I saw the question I thought you could divide it by ten. Would that work too? –  11684 Jun 25 '13 at 14:10
show 1 more comment

First, you don't need Case II. If $x\in\mathbb Q_{>0}$, then you can assume, that $x=\frac{p}{q}$, where $p,q>0$.

Your general idea is good: Assume, that $x$ is smallest possible and find an even smaller one, which then is a contradiction. Now let's answer your questions:

2) You already noticed, that you only proved that there is a smaller rational number, not necissarily positive. Your proof is basically "If $x$ is the smallest, then $x-1$ is smaller, a contradiction."

1) Of course, this a valid operation, it actually disproved your assumption, that $x$ was the smallest rational number.

3) is right, too. With an arbitrary $k$, you get infintely many smaller rationals.

To prove the positive case, notice, that if $x\in\mathbb Q_{>0}$, then $0<\frac{x}{k}<x$ for all $k\in\mathbb Z$.

-
In 2), he says, that he only proved, that there is no smallest rational number. He asked if this is right - which it is. In 3) he asked, if he gets infintely many smaller rationals (not positive rationals) by subtracting an $k\in\mathbb Z$ - which he does. I stated above, that his whole proof is only about showing that there is no minimal rational number. –  Tomas Jun 25 '13 at 0:39
Apologies (and +1). I failed to separate the objective from the unuseful steps that were taken. Well answered. –  Cameron Buie Jun 25 '13 at 3:50

Your proof does not work. Indeed, subtracting $1$ from $\frac p q$ will give you a rational number, but it will be negative by assumption, so this doesn't help you (since it doesn't give you a contradiction).

A simpler approach: Explicitly state what the infinitely-many positive rationals less than $x$ are.

Hint: If $y$ is a positive rational, what can you say about $\frac{y}2$? About $\frac{y}4$? $\frac{y}8$? ...

-
Oh, now I see it's that simple, haha! Thank you! But again, how do I justify this division? How do I prove that it is actually possible? –  Jobin Idiculla Jun 25 '13 at 0:20
Well, if you write $y=\frac p q,$ with $p,q$ integers and $q\ne 0,$ then $$\frac{y}{2^n}=\frac{p}{2^nq}$$ for all positive integers $n$. Can you show that $2^nq$ is a non-zero integer (with the same sign as $q$) for all positive integers $n$? –  Cameron Buie Jun 25 '13 at 0:21
Ah, yes of course! I understand it now. Thank you for the answer! –  Jobin Idiculla Jun 25 '13 at 0:26
Incidentally, you can use this result to prove that there are infinitely many positive rationals less than any positive real number $x$. Use Archimedean property (or density of the rationals) to show that for any real $x$ there is a rational $0<r<x$. Then since there are infinitely many positive rationals less than $r$.... –  Cameron Buie Jun 25 '13 at 0:35

Before diving into a proof right away, it might help to think of some examples and generalizing a pattern you find. For example, suppose $x=1/3$. Can you think of a smaller positive rational number? Well, we could do a bunch of things to make a fraction smaller. We could try decreasing the numerator $-$ but as you discovered, things might not work out if the numerator is already very small. Instead, we can try increasing the denominator. Indeed, since the integers are unbounded above, this is always possible.

Proof. We proceed by contradiction. Suppose instead that there are only finitely many positive rational numbers less than $x$. Now let $y$ be the smallest of these positive rational numbers. Observe that $y=p/q$ where $p,q\in \mathbb{Z}$ and $p,q>0$. Now consider the number: $$z=\dfrac{p}{q+1}$$ Observe that since $q+1\in \mathbb{Z}$ and $q+1>1>0$, we know that $z$ is a positive rational number. But then we have $z<y$, contradicting the minimality of $y$. Hence, there are infinitely many positive rational numbers less than $x$, as desired.

-

There is no way to justify the subtraction of $1$: If $\frac{p}{q}\lt 1$, and $p$ and $q$ are positive, then indeed you showed correctly that $\frac{p-q}{q}\lt \frac{p}{q}$.

However, you did not show that $\frac{p-q}{q}$ is positive, and it will not be, for instance, if $p=3$ and $q=5$.

-

I would first prove that there is a rational number between any two (by taking an average $(p_{1}/q_{1} + p_{2}/q_{2})/2$) and then apply that to the number we claim to be the smallest and zero.

-

if $\frac{p}{q} > 0$.

(Consider $p,q >0$ or |p|,|q|)

You have:

$$0 < \frac{p}{q+1} < \frac{p}{q}$$

$$0 < \frac{p}{q+2} < \frac{p}{q}$$

......

$$0 < \frac{p}{q+n} < \frac{p}{q}$$

$$\forall n \in \mathbb{N} . \ 0 < \frac{p}{q+n} < \frac{p}{q}$$

-