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

Question

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?

Thank you ahead of time.

Answer 1

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.

Answer 2

"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.

Answer 3

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.

This exercise in the textbook, on the other hand, is specifically, about the usual ordering of numbers (reals and their subsets). And your idea for a proof is perfectly valid. If you make such a list, then there will be a first element in it, but there's no smallest rational number in the usual sense. Or you can also look at any two consecutive numbers in such a (hypothetical) list and demonstrate that there are in fact some other rational numbers in between them.