How to find many bijective functions from rationals on $(0,1)$ to rationals on $(0,1)$

Question

Let $S=\{x\in\Bbb Q:\ 0<x<1\}$.

I am trying to find a sequence of bijective functions from $S$ to itself, where each function is strictly increasing. But currently I can only think of $f(x)=x$ which is a trivial example. Intuitively I think there are infinitely many such functions but I am struggling to construct them.

Thanks in advance for any help or hint.

Answer 1

First of all, observe that every such function extends to a continuous bijection between $[0,1]$ and itself. [To see this, first prove that left and right limits exist, for every $x\in [0,1]$, and are equal.]

Example. Another function with this property is $$ f(x)=\left\{\begin{array}{ccc} 2x & \text{if} & x\in [0,1/3], \\ \frac{x+1}{2} & \text{if} & x \in [1/3,1]. \end{array}\right. $$ In general, if $$ q_0=0<q_1<\cdots<q_{n-1}<1=q_n, \quad r_0=0<r_1<\cdots<r_{n-1}<1=r_n $$ are rationals, then the function which is defined as $$ f(q_i)=r_i, \quad i=0,1,\ldots,n, $$ and $f$ is linear in each interval $[q_{i-1},q_i]$, $i=1,\ldots,n$, also satisfies the property is the OP.

Next, consider two strictly increasing sequences of rationals $\{q_n\}$ and $\{r_n\}$, with $q_0=r_0=0$, which tend to 1, i.e., $$ 0=q_0<q_1<\cdots<q_{n-1}<q_{n}\to 1, \\ 0=r_0<r_1<\cdots<r_{n-1}<r_{n}\to 1, $$ and define $f: [0,1]\to[0,1]$, so that $f(q_i)=r_i$, $i\in\mathbb N$, and $f$ linear in each interval $[q_{i-1},q_i]$. Then this $f$ satisfies the property of the OP, and there exist $2^{\aleph_0}$ such functions, which is equal to the cardinality of $C[0,1]$.

Hence the answer is: The cardinality of the functions satisfying the OP is $2^{\aleph_0}$.

Answer 2

There are exactly $\frak c=2^{\aleph_0}$ order-preserving bijections from $\mathbb Q\cap(0,1)$ to itself. There are no more than that many, because there are just $\frak c$ mappings from a countably infinite set to itself. That there are at least $\frak c$ order-automorphisms of $\mathbb Q\cap(0,1)$ can be seen by fixing $\alpha$ and letting $\beta$ vary in the following:

Proposition. For any irrational numbers $\alpha,\beta\in(0,1)$, there are order-preserving bijections $\mathbb Q\cap(0,\alpha)\to\mathbb Q\cap(0,\beta)$ and $\mathbb Q\cap(\alpha,1)\to\mathbb Q\cap(\beta,1)$.

This follows from Cantor's theorem, that any linearly ordered set which is densely ordered and has no least or greatest element is isomorphic to $(\mathbb Q,\lt)$. In case Cantor's theorem is not available, here is an alternative proof of the proposition.

Proof. Let $a_0\lt a_1\lt\cdots$ be a strictly increasing sequence of rational numbers with $a_0=0$ and $a_n\to\alpha$ as $n\to\infty$, and let $b_0\lt b_1\lt\cdots$ be a strictly increasing sequence of rational numbers with $b_0=0$ and $b_n\to\beta$ as $n\to\infty$. For each $n=0,1,2,\dots$, let $f_n:\mathbb Q\cap(a_n,a_{n+1}]\to\mathbb Q\cap(b_n,b_{n+1}]$ be an order-preserving bijection, which can be constructed as a linear function. Then $f=\bigcup_{n=0}^\infty f_n$ is an order-preserving bijection from $\mathbb Q\cap(0,\alpha)$ to $\mathbb Q\cap(0,\beta)$. The construction of an order-preserving bijection from $\mathbb Q\cap(\alpha,1)$ to $\mathbb Q\cap(\beta,1)$ is left as an exercise.

Answer 3

You have a couple of good answers but here is a very low tech intuitive one.

Draw a $1 \times 1$ square. Add some dots (with rational coordinates) in it but with the restriction that if one dot is to the right of another then it is also higher. Connect $(0, 0)$ to the leftmost dot, continue connecting left to right, connect the rightmost dot to $(1, 1)$ and you have a function which does the job.

Just doing this with one dot is sufficient to give you infinitely many solutions.

Answer 4

I'll let $S=\{x\in \mathbb Q: x\in [0,1]\}.$ Observe that the function $(3x)/(2+x)$ is a strictly increasing bijection of $S$ to $S.$ This bijection never equals $x$ in $(0,1).$ (From now on, "bijection" means "strictly increasing bijection".)

If $a<b$ are rationals, we can compose this bijection with the map $x\to (x-a)/(b-a)$ and get a similar bijection of $S[a,b]$ to $S[a,b],$ where $S[a,b]= \{x\in \mathbb Q: x\in [a,b]\}.$

Choose any sequence of rationals $0<q_1 < q_2 <\cdots \to 1.$ These rationals define intervals $I_1=[0,q_1],[q_1,q_2],\dots $

Now let $\mathcal B$ be the set of binary sequences. Let $b=(b_n)\in \mathcal B.$ We define a bijection $f_b:S\to S$ piecewise on each $I_n:$ If $b_n =0,$ set $f_n(x)=x.$ If $b_n=1,$ let $f_b$ be the bijection of $S(I_n)$ to $S(I_n)$ as described above. Finally, set $f_b(1)=1.$ Then $f_b$ is a bijection of $S$ to $S.$

Clearly the map $b\to f_b$ is injective. Conclusion: The cardinality of the set of bijections of $S$ to $S$ is at least that of $\mathcal B,$ which is that of the real line.