-1

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.

Andrés E. Caicedo
  • 79,201
user3741580
  • 7
  • 5
    "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? – JMoravitz Aug 06 '19 at 13:42
  • 3
    “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”. – spaceisdarkgreen Aug 06 '19 at 14:24
  • “there are a lot of permutations so one of them probably does what we’re looking for” might be a reasonable plausibility argument if we didn’t have a rock solid proof that such a permutation can’t exist. To refute that you need to find a flaw in argument, not come up with much weaker arguments to the contrary. – spaceisdarkgreen Aug 06 '19 at 14:31
  • @spaceisdarkgreen what do you mean there is no first element? If you need one - consider $[0,1]$ interval. – user3741580 Aug 06 '19 at 14:32
  • @user3741580 "what do you mean there is no first element?" You were talking about $\mathbb{Q}$, which does not have a least element. If you want to talk about the set of rationals between $0$ and $1$ inclusive instead, that's a different thing. Regardless that doesn't fix the fundamental problem, that the rationals are dense while the natural numbers are not. – Noah Schweber Aug 06 '19 at 14:33
  • 1
    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. – spaceisdarkgreen Aug 06 '19 at 14:35
  • 2
    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$. – Noah Schweber Aug 06 '19 at 14:37
  • Reference to the absence of the least rational number in $\mathbb{Q}$ nor the fact that rationals are dense and naturals are not does not prove absence of an ordering permutation: rationals are enumerable and there is a total order on them. Permutation may exist, we just can't "write it down" same way we can't technically pick and write down any specific irrational number. – user3741580 Aug 06 '19 at 14:47
  • "And there is A total order on them." Yes, there is. But, that order is not the same order that you are used to using for natural numbers. Reference to the absence of a least rational number in $\Bbb Q$ and reference to the fact that rationals are dense are certainly each enough to prove that no such permutation exists such that $\Bbb Q$ is ordered using the same order as the usual order for the naturals. – JMoravitz Aug 06 '19 at 14:49
  • 1
    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. – eyeballfrog Aug 06 '19 at 14:50
  • No, the permutation cannot exist and it is not just a matter of writing it down. You keep saying the argument is not enough to show this but don’t say why. All you say is that the rationals are enumerable and have a total ordering, as if this somehow means there is an enumeration that agrees with that standard ordering, but this is precisely what the argument proves can’t happen. I think you just do not understand the argument. – spaceisdarkgreen Aug 06 '19 at 16:55
  • I think your error is thinking these permutations must somehow survey all possible orderings on $\mathbb Q.$ That is not the case: they only survey all orderings of type $\omega.$ There are bazzilions of countable order types different from that and the type of the standard ordering of $\mathbb Q$ is an example. – spaceisdarkgreen Aug 06 '19 at 17:08
  • @spaceisdarkgreen, thank you - can you explain last statement?

    I think $\mathbb{Q}$ is of the same type as $\mathbb{N}$.

    Permutation is a point in $\mathbb{N} ^ \mathbb{N}$. Cardinality of $\mathbb{N} ^ \mathbb{N}$ is continuum. Are you saying there is not enough points to represent natural order on $\mathbb{Q}$?

     – user3741580 Aug 06 '19 at 18:11
  • $\mathbb Q$ is the same cardinality as $\mathbb N$, but its standard ordering is not isomorphic to the standard ordering of $\mathbb N$, which is what the density/least element argument show, and is what would be required to enumerate the rationals in their standard order. Permutations just give different possible enumerations, none of which will be in order since no ordering of type $\omega$ will be in order, since the rationals aren’t order isomorphic to the naturals. It doesn’t matter how many of them there are, they are all in the wrong order. – spaceisdarkgreen Aug 06 '19 at 19:03
  • I’m not saying there aren’t “enough”... I’m saying that the number of orderings is irrelevant if they’re all the wrong type. (And you’re not wrong about the fact that there are continuum many orderings of type $\omega$. But there are continuum many of type $\mathbb Q$ as well that are all different. Only those that are type $\omega$ correspond to the order induced by an enumeration $\mathbb N\to \mathbb Q$ or equivalently that plus an additional permutation.) – spaceisdarkgreen Aug 06 '19 at 19:13
  • The most important thing here, I think, is to realize that enumerations are not the same thing as orderings: each enumeration induces an ordering, but orderings are a lot more general. – spaceisdarkgreen Aug 06 '19 at 19:18
  • @spaceisdarkgreen - thanks for the clarification. Your mentioning of $\mathbb{N}$ and $\mathbb{Q}$ not being order-isomorphic - that should be an answer. Thanks again. – user3741580 Aug 06 '19 at 19:26
  • No problem. Keep in mind that “$\mathbb N$ and $\mathbb Q$ are not order isomorphic” is just a fancier way of stating what is concluded and proved by the density and least element arguments. – spaceisdarkgreen Aug 06 '19 at 19:33

1 Answers1

4

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.

eyeballfrog
  • 22,485