# Proof that there is an infinite amount of rationals $t$, $0<t<1$ using the definitions of $=$ and $\leq$

This is a question to which the answer is of course intuitively obvious. We are asked to prove that there is an infinite amount of rationals $t$ with $0<t<1$ using the definitions of $=$ and $\leq$ on $\mathbb{Q}$.

Definition Suppose $r,q\in \mathbb{Q}$. We can write both $r$ and $q$ with the same denominator $b\in \mathbb{N}^*$, $r=\frac{a}{b}$ and $q=\frac{c}{b}$, for some $a,c\in\mathbb{Z}$. Then $r< q \iff a< b$.

Definition Suppose $r,q\in \mathbb{Q}$. Suppose also $r=\frac{a}{b}$ and $q=\frac{c}{d}$ for some $a,b,c,d\in \mathbb{Q}$. Then $r=q\iff ad=bc$.

Now here's my idea for a proof:

Suppose we have a finite subset $S\subset Q$ of rational numbers with every so that for every $s\in S, 0<s<1$.

If $S$ is empty, we have $\frac{1}{2}\in \mathbb{Q}$ and $0<\frac{1}{2}<1$, so $S\neq\{q\in \mathbb{Q}|0<q<1\}$ so the interval contains at least one element.

Suppose $S$ contains one element $s$. Then we have that $1-s$ is also in the interval so the interval contains more than one element.

Now suppose $S$ contains more than one element. Take two distinct elements $r,q, r< q$ such that there is no element $t$ in $S$ with $r<t<q$. We know we can write $r=\frac{a}{b}$ and $q=\frac{c}{b}$, with $b\in \mathbb{N}^*$ and $a,b\in \mathbb{Z}$. Then also $a<c$ so there is a number, say $d$, so that $2a<d<2c$. But then $r=\frac{a}{b}=\frac{2a}{2b}<\frac{d}{2b}<\frac{2c}{2b}=\frac{c}{b}=q$, so we have found a rational number which satisfies the conditions but which is not in $S$. Thus for any finite subset of $S\subset\mathbb{Q}$ which lies completely in $(0,1)$, $S\neq\{q\in \mathbb{Q}|0<q<1\}$ and we can conclude that $\{q\in \mathbb{Q}|0<q<1\}$ is infinite.

While I think this is a good approach, I am not sure and would very much appreciate your help and comments. I also haven't used the definition of $=$, so maybe someone could suggest how I would do that.

Thank you

EDIT: In the comments, Hagen von Eitzen remarks that I haven't proven that $\frac{d}{2b}\notin S$. I have edited the text above in such a way that I think I have gotten around this. I understand the biggest mistake in this proof is the argument that if $|S|=1$ then there is a rational number which satisfies the conditions which is not in $S$.

PS. I don't really have the time to look at the answer but when I get home later I will carefully look through it and upvote/select as answer if it was helpful (don't worry, I'm not that strict :P).

• Why not like this: If $S$ is a finte set of rationals in $(0,1)$, then there is a smallest element $s_0\in S$, i.e. such that $s\in S$ implies $s_0\le s$. Then $s_0>0$ implies $s_0>\frac 12 s_0>0$ and hence $\frac 12 s_0$ is one more rational in $(0,1)$. – Hagen von Eitzen Nov 23 '12 at 11:36
• In the step where you show that $(0,1) \cap \mathbb Q$ contains more than one element you must argue why it can't be true that $s = \frac 12$ is the only element (as for this particular $s$ your argumentaion does not work). – martini Nov 23 '12 at 11:36
• When you find $\frac{d}{2b}$, you do not show that it is $\notin S$. – Hagen von Eitzen Nov 23 '12 at 11:37
• It is very unclear for me what you can use, and what you can't. For example you start with $1/2$, but why you can use it? If you can, you can use $1/n, 2/n, \ldots$ for arbitrary $n$ and get the same result. Also if you have $0$ and $1$ you could just take the average of any two neighbouring numbers and generate infinite sequence (or you could use Stern-Brocot tree). – dtldarek Nov 23 '12 at 11:59
• I think it wouldn't hurt to also give the definition of $\mathbb{Q}$ in the question. without this it is hard to understand precisely what $=$ and $\le$ are. – Dan Shved Nov 23 '12 at 12:10

To prove that $0<\frac{1}{2}<1$ you must use the definition of $\leq \ \text{and} \ =$(i.e. that $0\leq\frac{1}{2}\leq1, \ \frac{1}{2}\neq 0$ and $\frac{1}{2}\neq 1$). Your reasoning that $S$ contains more than one element is incorrect. You said that if $s \in S$ then $1-s \in S$ thus $|S|\geq2$. But if $s=\frac{1}{2}$ then $1-s=s$. Also you must choose $r,q$ in a way that guarantees $\frac{d}{2b} \not \in S$. Fix these and your proof is ok.

If you want you can try this different proof:

• $0<\frac{1}{n}<1, \ \forall n \in \mathbb{N}-\{1\}$ (prove that $0\leq\frac{1}{n}\leq1$ but $0\neq \frac{1}{n} \neq 1, \forall n \in \mathbb{N}-\{1\}$).
• $\frac{1}{n}\neq\frac{1}{m}, \ \forall \ n\neq m \in \mathbb{N}$.

Thus $S$ is infinite.

• @Peter Tamaroff: Thanks. – P.. Nov 23 '12 at 11:53
• I'm sorry, I can't upvote because I don't have sufficient reputation yet. – user50407 Nov 23 '12 at 20:50
• That's OK I'll wait :) – P.. Nov 23 '12 at 21:00
• I added another answer underneath as what I think is the elaboration of your suggestion. Could you take a look and see if it's alright? – user50407 Nov 24 '12 at 20:00

Here is another approach which I think sort of elaborates Pambos' suggestion for a different proof and uses both the ordering and equality on $\mathbb{Q}$. We will explicitly define an injective function from $\mathbb{N}\backslash \{0,1\}$ to $\mathbb{Q}$ so that $im(f)\subseteq \{q\in\mathbb{Q}|0<q<1\}$. It follows that the cardinality of $\{q\in\mathbb{Q}|0<q<1\}$ is at least equal to the cardinality of $\mathbb{N}\backslash \{0,1\}$ which is in turn equal to the cardinality of $\mathbb{N}$. From this we will conclude that $\{q\in\mathbb{Q}|0<q<1\}$ is infinite which just rephrases the statement that was to be proven in set builder notation.

Define $f:\mathbb{N}\backslash\{0,1\}\to\mathbb{Q}, n\mapsto \frac{1}{n}$. First we will show that $im(f)\subseteq \{q\in\mathbb{Q}|0<q<1\}$. Suppose we have $n\in \mathbb{N}\backslash\{0,1\}$. Then $f(n)=\frac{1}{n}$ and $0=\frac{0}{n}<\frac{1}{n}<\frac{n}{n}=1$, using the definition of the ordering and because by definition of $f$ we have that $n>1$. For arbitrary $n$ in the domain $f(n)\in \{q\in\mathbb{Q}|0<q<1\}$ so $im(f)\subseteq\{q\in\mathbb{Q}|0<q<1\}$.

Now we will prove that $f$ is injective. Suppose for some $n,m\in \mathbb{N}\backslash\{0,1\}$ we have $f(n)=f(m)$. Then $\frac{1}{n}=\frac{1}{m}$. By definition of equality on $\mathbb{Q}$ we immediately have $m=1\cdot m=n\cdot 1=n$ so $f$ is injective.

We have shown there is an injective function from $\mathbb{N}\backslash\{0,1\}$ to a subset of $\{q\in\mathbb{Q}|0<q<1\}$. Because $\mathbb{N}\backslash\{0,1\}$ is equal in cardinality to $\mathbb{N}$ and this set is infinite, the subset of $\{q\in\mathbb{Q}|0<q<1\}$ which we have considered is also infinite. Because a subset of $\{q\in\mathbb{Q}|0<q<1\}$ is infinite it must be infinite itself.

• That's correct! – P.. Nov 24 '12 at 20:07
• Ok thanks, thanks as well for the upvote :). – user50407 Nov 24 '12 at 20:08