Is it possible to construct a strictly monotonic sequence of all rational numbers?

Question

I know that the set of all rational numbers is countable, and can be enumerated by a sequence, say $\{a_n\}$. But can we construct a monotonic $\{a_n\}_{n=1}^{\infty}$, e.g. with $a_k<a_{k+1}$? It doesn't seem plausible to me, because then $a_1$ would be the smallest rational number, which clearly can't be any finite number. Am I mistaken?

Answer 1

if $a_k< a_{k+1}$ then $x := \frac{a_{k+1}+a_k}{2}$ is a rational number between those two, so no.

Answer 2

You are not mistaken. Even assuming you want just the non-negative numbers, so that $a_0=0$, you cannot pick $a_1$ correctly because you will have skipped $a_1/2$.

Alternatively, you could allow negative indices (and have $\ldots, a_{-1}, a_0, a_1,\ldots$), which would also solve your "there is no smallest rational number" problem, but it still has the problem that there are rational numbers between any two numbers. Specifically, if the list is complete, we must have some $n$ such that $a_n=0$. But then we necessarily miss $a_{n+1}/2$.

Answer 3

As Arthur already stated, such a numbering cannot start with a finite index, i.e. either your sequence will count from $-\infty$ to $\infty$ or you only count the non-negative rational numbers (i.e. $\mathbb Q^+_0$). And as Thomas showed, a "normal" sequence also won't work since you'll always find a number in between.

However, you can define a sequence of sequences $\{\{a_{nm}\}_{n=-\infty}^\infty\}_{m=1}^\infty$ such that its $\lim_{m\to\infty}$ yields a sequence counting all rational numbers. As an example, consider the typical enumeration sequence of $\mathbb Q$ (see e.g. here) and let $\{a_{nm}\}_n$ be the ordered sequence of the first m rational numbers obtained that way. The thing is, though, you will just end up with $\mathbb R$...

Answer 4

As stated, the answer is no, because the question uses the symbol $<$ which has the implied meaning: The usual ordering of $\mathbb{Q}$ where $\frac{a}{b}<\frac{c}{d}$ iff $ad < bc$ in $\mathbb{Z}$.

But.

As mentioned in another answer, $\mathbb{Q}$ can be well-ordered, i.e. one can define a different order $\prec$ with the property that every nonempty subset of $\mathbb{Q}$ contains a least element with respect to $\prec$. For this ordering, a monotone sequence containing all of the rationals is easy to construct: let $x_1$ be the smallest rational, let $x_2$ be the smallest element of $\mathbb{Q} \setminus \{x_1\}$, etc.

Answer 5

To parallel Thomas's answer with a more obscure one:

If $a_k < a_{k+1}$ and $a_k = \frac{b_k}{c_k}$ then the mediant $x:= \frac{b_k+b_{k+1}}{c_k+c_{k+1}}$ is a rational number between those two, so no.

($b_k$ and $c_k$ are relatively prime/are in lowest terms)

It is elementary but not obvious that the mediant $x$ is between the two (exercise for the reader). The reason this answer is even a thing (Thomas gave a much simpler and easier to understand answer) is because using the mediant we can construct an ordering on the rationals that is countable, and in addition gives all and only the rationals.

The usual proof that the (positive) rationals have equal cardinality to the naturals is by 'dovetailing'. counting along antidiagonals of pairs and then ignoring rationals that have already been seen (ignoring if gcd $\neq 1$). This is somewhat unsatisfying because it doesn't give an explicit bijection with the naturals. To get the implied rational-natural bijection from gcd, see the Stern-Brocot tree for details.