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.
Best Answer
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.