# Show that it is impossible to list the rational numbers in increasing order

This is problem #6 from Section 1.2 of Ash's Real Variables With Basic Metric Space Topology.

I am asked to show that it is impossible to list the rational numbers in increasing order.

While I know it is possible to list a finite subset of the rational numbers in increasing order, I was wondering if the reason for the impossibility in this case is because there is no least element of $\mathbb{Q}$?

I mean, it's possible to impose an ordering on $\mathbb{Q}$ (correct me if I'm wrong, but it seems possible to compare any two rationals).

But the set $\mathbb{Q}$ is of course, a subset of itself, and the Well-Ordering Principle says that a set $S$ is Well-Ordered only if any subset of $S$ contains a minimal element. Since $\mathbb{Q}$ does not contain a minimal element, it does not appear that it is a Well-Ordered set.

Is this the correct idea as to why it's impossible? If not, could somebody explain to me what the correct idea is and a strategy for proving it?

• suppose there are succesive rationals $p, q$ so that $p<q$. Then by density, there is a rational $r$ such that $p<r<q,$ which is a contradiction, because $p$ and $q$ were assumed to be successive. Feb 9, 2017 at 16:46
• "perhaps it's even possible to list any proper subset of the rationals in increasing order because any such subset will have a least element" Really? What's the least element of $(0, 1)\cap\mathbb{Q}$? Feb 9, 2017 at 16:46
• Your argument works, but it might not be what the problem was shooting for, for two reasons. You would generally ask a question like this before the Well-Ordering Principle has been shown, so unless you prove it, you can't use that. More to the point, there does not exist an order preserving map of$\Bbb Q\cap (0,1) \mapsto \Bbb Z$ and the desired proof ought also to show that fact. Feb 9, 2017 at 16:47
• @MarkFischler actually, we have already been shown the Well-Ordering Principle. In order to show that the nonexistence of an order preserving map of $\mathbb{Q}\cap (0,1) \mapsto \mathbb{Z}$, do I first need to show any kind of bijection between $\mathbb{Q}$ and $\mathbb{Q}\cap(0,1)$?
– user100463
Feb 9, 2017 at 16:52
• @chilangoincomprendido: instead of saying "by density", it is simpler to just let $r=(p+q)/2$. Feb 9, 2017 at 17:09

There are many ways to prove that this is impossible. As you rightly suggest, there is no least rational number, so as soon as you declare one rational number to be the first on your list, all the rational numbers lying below it cannot appear on the list.

Supposing you allow your list to be infinite in both directions (i.e. in order-preserving bijection with $\mathbb{Z}$), it is still impossible, but the argument using least elements no longer works. To prove that this is still impossible, you can use the fact that $\mathbb{Z}$ is not dense, but $\mathbb{Q}$ is. Indeed, suppose $q,r \in \mathbb{Q}$ appear in positions $0$ and $1$ in the list. Then $q<r$, since the list is written in increasing order; but then $q < \frac{q+r}{2} < r$, so $\frac{q+r}{2}$ must appear between $0$ and $1$ on the list, which is evidently impossible.

"I am asked to show that it is impossible to list the rational numbers in increasing order. "

It may not have been explicitely stated but it is implicitely assumed that "order" in this sense is the order we've all known and loved since elementary school where $n < n+1$ and $a > 0; b < c \implies ab < ac$ etc.

"I was wondering if the reason for the impossibility in this case is because there is no least element of Q? "

Well, yes, to have a list a list must have a first element. And for each item in the list there must be a distinct next item that immediately follows it. Both of those are impossible if the rationals are ordered with the order we know and love.

"I mean, it's possible to impose an ordering on Q (correct me if I'm wrong, but it seems possible to compare any two rationals)"

Well, obviously. The order we know and love if $a > b$ if $a - b > 0$ or $m/n > p/q$ if $mq >pn$. That's not "imposed". We were given that and we've been using it since we learned to count.

But we can also impose a different order if we want to. More on that later.

"But the set Q is of course, a subset of itself, and the Well-Ordering Principle says that a set S is Well-Ordered only if any subset of S contains a minimal element. Since Q does not contain a minimal element, it does not appear that it is a Well-Ordered set."

Precisely. $\mathbb Q$ is not a well-order set when using the order that we know and love. And the fact that $\mathbb Q$ has no least element demonstrates that (as does that no element has an immediate successor.

"Is this the correct idea as to why it's impossible?"

Yes. You have done it. You are done. Go home and have a cup of cocoa.

....

So ... what's the issue?

I imagine that you have heard by the Well-Ordering Principle that $\mathbb Q$ IS a well-ordered set. That is true. But this is refering to a different method of ordering than the one we know and love.

All countable sets can be listed (not necessarily be size but by other criteria) and we can call the order they are listed in a well-ordering order.

If we used the "diagonal" listing of rationals. (1/1, 1/2, 2/1, 1/3, [omit 2/2] 3/2, 1/4, 2/3, 3/2, 1/4, 1/5, [omit 2/4],[omit 3/3][omit 4/2] 5/1, etc.) And define ordering as:

$r < t$ if $r$ appears on the list before $t$.

Then we'd have $1 < 1/2 < 2 < 1/3 < 3/2 < 1/4 < 2/3 .....$. This ordering, which we all know and hate, and which has nothing to do with size, but only has to do with running through a diagonal and/or making a list, is a well-ordering.

But it is not the order we know and love.

Which is not well-ordered.

That's all.

......

Oh, wait. That's not all. The uncountable reals according to the axiom of choice (equivalent to the Well-Ordering Principle when extending to uncountable sets) will have a well-ordering. If it does (the Axiom of Choice is an axiom, not a theorem, and can not be proven) no-one knows what it is. I may be wrong, but I believe that just as the Axiom of choice can not be proven, we also know the well-ordering of the reals can not be found.

But the rationals are countable so that is a different issue.

I think you're confusing different orderings with each other. Yes, the Well Ordering Principle says that any set, including $\mathbb{Q}$, can be well-ordered — but that won't be the same usual ordering of numbers. "Increasing" with respect to that new ordering will not be the same thing as with respect to the usual "less or equal" relation for numbers.