Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Because the nonnegative rationals $\mathbb{Q}_+$ are countable, I can enumerate them as a sequence $\{q_i\}_{i\in\mathbb{N}}$. For any pair of rationals $q$ and $p$, I can perform the comparison $q\leq p$ according to the ordering of the real numbers. Is it possible to enumerate the rationals as an increasing sequence, i.e., $q_i\leq q_{i+1}$ for all $i\in\mathbb{N}$? More generally, given an ordering on $\mathbb{Q}_+$, can I enumerate $\mathbb{Q}_+$ as an increasing sequence under this ordering?

I do not think this is true, but I cannot think of a good approach to proving it false.

EDIT: I meant to only ask about the nonnegative rationals, so I am correcting my question to fix that mistake. The original version of the question asked about enumerating the rationals.

share|cite|improve this question

No, it is not possible, since if you had such an ordering then by considering two consecutive (distinct) rationals in your ordering, there are (in the real line) an infinite number of rationals between them, but not in your ordering.

share|cite|improve this answer
In other words: You may choose $q_1$ and $q_2$ with $q_1<q_2$, but then $q:=\frac12(q_1+q_2)$ cannot by among your $q_n$ because $q_1<q_n<q_2$ should imply $1<n<2$, contradiction. – Hagen von Eitzen Sep 26 '12 at 22:03
Yes, that is even clearer! – Old John Sep 26 '12 at 22:07

Note: This answer was for the original version of the question.

No, you can’t: what could possibly be the first rational in your list? No matter what $q$ you choose, $q-1$ is a smaller rational that ought to precede $q$ in your list.

share|cite|improve this answer
Oops, I realized I meant to only consider the nonnegative rationals, but this doesn't fix it anyway. Because whatever q_1 is, (q_1)/2 is a smaller rational. I'll edit my question to correct this problem. – Carl Morris Sep 26 '12 at 21:37
@Carl: Since you’ve now answered your own question, you should go ahead and post an answer; you’ll have to wait I-forget-how-long, but eventually you’ll be able to accept your own answer. This is perfectly acceptable; indeed, it’s encouraged. – Brian M. Scott Sep 26 '12 at 21:44
Even if you restrict to rationals in any (non-trivial) interval, either open or closed, a small variation of Brian's answer or mine would still give you a contradiction. – Old John Sep 26 '12 at 21:48
up vote 3 down vote accepted

Thanks to Brian M. Scott's and Old John's answers, I now know the answer to my own question, and Brian has encouraged me to post my own answer to the question.

Let $\{q_i\}_{i\in\mathbb{N}}$ be an ordered enumeration of the nonnegative rationals. Clearly, $q_1=0$. By definition, $q_2\neq0$, and $q_2\leq q$ for all rational $q>0$, but $q_2/2$ is rational and $q_2/2 \leq q_2$. However, $q_2 \leq q_2/2$. This implies that $q_2=2q_2$, i.e., $q_2=0$, which is a contradiction. Hence, no such enumeration exists.

share|cite|improve this answer
Excellent; upvoted. – Brian M. Scott Sep 26 '12 at 23:32

You can order by size every finite subset of positive rationals. If you could conclude from every finite subset on the infinite set, then ordering of all positive rationals by size would be possible. Of course this is not possible. For instance there is no smallest positive rational. But this shows that you can not conclude from every finite subset on the infinite set. Just this, however, is required and is done when enumerating the infinite set of rationals.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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