Permutation of the rational numbers

This article page is a stub, please help by expanding it.

---

A permutation of the rational numbers is a bijection (one-to-one and onto mapping) from the ordered (in ascending order) set of rational numbers $\scriptstyle \mathbb {Q} \,$ to a differently (if it is not the identity permutation) ordered (either well-ordered, thus an ordering since denumerable, or not well-ordered) set of rational numbers.

The identity permutation of the rational numbers gives an ordered set which is not well-ordered (thus not allowed in the OEIS) since

• A rational number has no predecessor;
• A rational number has no successor;
• There is no first rational number.

To be admissible in the OEIS, a permutation of the rational numbers must have a one-to-one and onto correspondence with the set of positive integers (denumerable). By discovering such an ordering of the positive rational numbers, Cantor proved the denumerability of the positive rational numbers, and thus of the rationals.

From the Cantor ordering of positive rational numbers (Cf. A020652(n) / A020653(n), n ≥ 1)

{1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 5/1, 1/6, 2/5, 3/4, 4/3, 5/2, 6/1, 1/7, 3/5, 5/3, 7/1, ...}

one may obtain the following ordering of rational numbers

{0/1, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 1/4, -1/4, 2/3, -2/3, 3/2, -3/2, 4/1, -4/1, 1/5, -1/5, 5/1, -5/1, 1/6, -1/6, 2/5, -2/5, 3/4, -3/4, 4/3, -4/3, 5/2, -5/2, 6/1, -6/1, 1/7, -1/7, 3/5, -3/5, 5/3, -5/3, 7/1, -7/1, ...}

giving the sequence of numerators (Cf. A??????(0) = 0, A??????(n) = (-1)^(n+1) * A020652(floor((n+1)/2)), n ≥ 1)

{0, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 2, -2, 3, -3, 4, -4, 1, -1, 5, -5, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6, 1, -1, 3, -3, 5, -5, 7, -7, ...}

and denominators (Cf. A??????(0) = 1, A??????(n) = A020653(floor((n+1)/2)), n ≥ 1)

{1, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 4, 4, 3, 3, 2, 2, 1, 1, 5, 5, 1, 1, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 7, 7, 5, 5, 3, 3, 1, 1, ...}

Sequences like these are known to be permutations (furthermore, they are orderings since denumerable) because they were so defined. Certain sequences arise in other problems and are proved to be permutations (and orderings if denumerable). Others are conjectured to be permutations, until a repeated term can be found (counterexample), while nothing short of a proof can exclude the possibility of non appearance of a term.

However, any well-defined bijection (i.e. permutation) of rational numbers can be recorded in OEIS as a signature permutation for bijections of rational numbers, based on any one-to-one and onto mapping between rationals and natural numbers, like for example Cantor ordering of positive rational numbers mentioned above, or more elegantly and efficiently (computing-wise), via Stern-Brocot tree or any of its variants.

Permutation of the rational numbers

See orderings of rational numbers for denumerable permutations of the rational numbers.

Permutation of the nonnegative rational numbers

See orderings of nonnegative rational numbers for denumerable permutations of the nonnegative rational numbers.

Examples

The examples are necessarily denumerable (orderings), otherwise they would not be in the OEIS!

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).

{0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, ...}

a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly once [Stern; Calkin and Wilf]

Permutation of the positive rational numbers

See orderings of positive rational numbers for denumerable permutations of the positive rational numbers.

Order-preserving permutations of the rational numbers

An important subgroup of permutations of the rational numbers is the group of order-preserving permutations of the rational numbers. It consists of those permutations $\scriptstyle p\,$ of the rational numbers which respect the original order of any two rationals $\scriptstyle r,\,s\,\in \,\mathbb {Q} \,$, that is, $\scriptstyle r\,\leq \,s\,\iff \,p(r)\,\leq \,p(s)\,$. It is one of the oligomorphic permutation groups.

In contrast to the set of integers $\scriptstyle \mathbb {Z} \,$, where the only order-preserving permutations are translations (with a constant integer term), i.e.

$p(z)\,:\,z\,\rightarrow \,z+b,\quad b\,\in \,\mathbb {Z} ,\,$

the rational numbers, since $\scriptstyle \mathbb {Q} \,$ is a dense set, admit many other kinds of order-preserving [i.e. strictly increasing (first derivative positive or zero at discrete inflexion points) one-to-one and onto algebraic] maps $\scriptstyle \mathbb {Q} \,\to \,\mathbb {Q} \,$. For example, a linear map $\scriptstyle \mathbb {Q} \,\to \,\mathbb {Q} \,$ ($\scriptstyle a\,=\,1\,$ giving the previous case)

$p(q)\,:\,q\,\rightarrow \,aq+b,\quad a\,\in \,\mathbb {Q} _{+},\,b\,\in \,\mathbb {Q} ,\,$

is an order-preserving permutation of the rational numbers, and [somewhat] more generally, so does

$p(q)\,:\,q\,\rightarrow \,\left(\sum _{i=1}^{n}a_{2i-1}\,q^{2i-1}\right)+a_{0},\quad a_{i}\in \mathbb {Q} _{+}\,\cup \,\{0\}{\text{ for }}i\geq 1,\,\sum _{i=1}^{n}a_{i}\neq 0,\,a_{0}\in \mathbb {Q} ,\,n\in \mathbb {Z} _{+}.\,$

Also, a piecewise function such as

$f(x)={\begin{cases}{\frac {x}{(1-x)}}&{\mbox{if }}x<{\frac {1}{2}}\,,\\3-{\frac {1}{x}}&{\mbox{if }}{\frac {1}{2}}\leq x<1\,,\\x+1&{\mbox{if }}x\geq 1\,,\\\end{cases}}$

which is induced when a simple binary tree rotation is applied to a Stern-Brocot tree (or just to the positive side of it, if an extended Stern-Brocot tree covering the whole $\scriptstyle \mathbb {Q} \,$ is used, see A057114).

Permutation of the rational numbers (conjectured)

(...)

Permutation of the rational numbers (open problem)

(...)

See also

• Permutation of the algebraic numbers
  • Orderings of algebraic numbers
• Permutation of the rational numbers
  • Orderings of rational numbers
• Permutation of the nonnegative rational numbers
  • Orderings of nonnegative rational numbers
• Permutation of the positive rational numbers
  • Orderings of positive rational numbers
• Permutation of the integers
  • Orderings of integers
• Permutation of the nonnegative integers
  • Orderings of nonnegative integers
• Permutation of the positive integers
  • Orderings of positive integers