0
$\begingroup$

This question already has an answer here:

Rational numbers are in 1-1 correspondence with natural numbers. For example, let's consider enumeration mentioned in wikipedia: https://en.wikipedia.org/wiki/Rational_number#Properties (https://en.wikipedia.org/wiki/File:Diagonal_argument.svg)

The above mentioned enumeration makes a sequence: $q_1, q_2, ...$. In other words, $q$ is a function form $\mathbb{N}$ to $\mathbb{Q}$.

Function $q$ is not monotone (i.e. - neither descending nor ascending): it is not necessarily true that for every $i$ $q(i) < q(i+1)$.

At the same time, there exist unique total order on all rational numbers. Because of that I wonder, is there (or why isn't there) a permutation $p: \mathbb{N} \xrightarrow{} \mathbb{N}$ such that $q\circ p$ becomes monotone: $$q_{p_1} < q_{p_2} < ... $$ If such permutation does not exist - why?

Please note, I understand the controversy that if such order would existed, there would have been infinite number of other rationals in between of two subsequent rationals.

Edit: Thanks for the reference to a similar question, I just don't think explanation there is evident enough. It is even more puzzling, because the number of permutation has a next level of cardinality (continuum) and yet - in such a rich set there is no single permutation that will bring order. Or maybe there is?

Edit 2: The initial question was mainly about existence of a permutation. Whether such permutation is incomprehensible to write down or does not exist at all. If it does not exist - why and what can be concluded from that.

$\endgroup$

marked as duplicate by JMoravitz, Lee Mosher, Lord Shark the Unknown, Don Thousand, Noah Schweber Aug 6 at 14:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ "Please note, I understand the controversy that if such an order would existed..." Why is that not a satisfactory explanation of why it is not possible? $\endgroup$ – JMoravitz Aug 6 at 13:42
  • 2
    $\begingroup$ “Or maybe there is?” No there is not. Why is the explanation not evident enough? I really don’t know what could be more evident than “there is no least rational but there must be a first element on the list”. $\endgroup$ – spaceisdarkgreen Aug 6 at 14:24
  • 1
    $\begingroup$ But we are enumerating all of the rationals (or if not you have not made that clear in your explanation) and there is no first element of all of the rationals. If you instead want to do this with an enumeration of $\mathbb Q\cap [0,1]$ then the argument about least elements will not work but the density argument still will. $\endgroup$ – spaceisdarkgreen Aug 6 at 14:35
  • 2
    $\begingroup$ Inasmuch as this isn't a duplicate, it's unclear - you haven't explained what's not "evident enough" about the self-evident fact that the density of the rationals precludes such a permutation. If you can explain the issue there might be a good question here but I think as written currently it's not possible to answer in a different manner than the linked duplicate. (Similarly, "the number of permutation has [cardinality continuum, but] there is no single permutation that will bring order" isn't clear either - there are lots of reals between $0$ and $1$, but none of them are bigger than $17$. $\endgroup$ – Noah Schweber Aug 6 at 14:37
  • 1
    $\begingroup$ Restriction to $\mathbb Q \cap [0,1)$ still fails the least element argument. $0$ has to come first, and then the rest of the enumeration is of $\mathbb Q \cap (0,1)$, which also has no least element. $\endgroup$ – eyeballfrog Aug 6 at 14:50
3
$\begingroup$

The rationals are dense, which means that for any rationals $p,q$, there is a rational $r$ with $p < r < q$. So, for any enumeration of rationals $q_i$, there is an index $j$ with $q_1 < q_j < q_2$, and thus the enumeration cannot be strictly increasing.

Alternatively, the result also follows from the fact that $\mathbb Q$ has no least element, so any enumeration must include an element smaller than the first one.

$\endgroup$

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