Explicit bijection between $\Bbb R$ and permutations of $\Bbb N$

Question

The set of permutations of the natural numbers has the cardinality of the continuum. I've got injections in both directions, no problem. The Schröder–Bernstein theorem tells us that this implies the existence of a bijection. I'm wondering if it's possible to construct one explicitly.

(In what follows, I'm using the convention that $0\not\in\Bbb N$. This obviously doesn't change anything, cardinality-wise.)

---

For $\Bbb R\to S_\Bbb N$, we note that every real number is the limit of some rearrangement of the alternating harmonic series. If $\alpha\in\Bbb R$, we start with positive terms: $1+\frac13+\frac15+\cdots$, until we obtain a partial sum greater than $\alpha$. We then add negative terms until our partial sum is less than $\alpha$, then we switch back to the positive terms, starting with the first unused one, etc.

In this way, we construct a series, and if we take the absolute values of the reciprocals of the terms of it, we have a permutation of $\Bbb N$. This mapping is not onto, because many permutations of the series converge to $\alpha$ - all we have to do is "overshoot" at some point, and then continue converging to $\alpha$ as usual. (More trivially, we only get permutations with $\sigma(1)=1$ using this particular construction.)

---

In the other direction, if we have a permutation $\sigma\in S_\Bbb N$, we can write the continued fraction $[\sigma(1);\sigma(2),\sigma(3),\ldots]$. This actually injects $S_\Bbb N$ into $\Bbb R\setminus\Bbb Q$, because non-terminating continued fractions represent irrational numbers. Thus, this mapping is not onto; it is not even onto the irrationals.For example, no permutation of $\Bbb N$ maps in this way to any quadratic irrational, or to $e$, or to any other irrational whose c.f. expansion has repeated terms.

---

So, those injections are fun and all, but finding an explicit bijection seems hard. Clearly, a bijection between $S_\Bbb N$ and any interval would suffice, because there are standard, elementary ways to construct bijections between $\Bbb R$ and any interval.

I have Googled in vain for a solution, and I don't believe this question is a duplicate. I will be happy for a hint or a full solution, or an explanation of why such an explicit construction is impossible.

Full disclosure: someone online claimed that this is "not hard", but refused to explain how, other than mentioning the Cauchy sequence construction of the reals. I don't see how that's useful, and I think he's mistaken or bluffing. I'm not too proud to admit I'm stumped. :/

Answer 1

It's not exactly pretty, but we can do something like:

1. Get rid of the rationals by mapping $q+n\sqrt2$ to $q+(n+1)\sqrt2$ for every $q\in\mathbb Q$ and $n\in\mathbb N_0$
2. Map the irrationals to the irrationals in $(0,1)$ by standard techniques, e.g. by $$ x\mapsto\begin{cases} 1/(2+x) & \text{for }x>0 \\ 1-1/(2-x) & \text{for }x<0 \end{cases} $$
3. Write each irrational in $(0,1)$ as a continued fraction. Ignoring the leading $0$ in each continued fraction, they become all the infinite sequences of positive integers.
4. Now convert each infinite sequence of positive integers to a bijection between the odd naturals and the even naturals by the "back-and-forth" technique. This construction proceeds in steps, by alternating between
   • Take a number $n$ from the sequence and map the first odd natural that has not yet been paired, with the $n$th even natural that has not yet been paired.
   • Take a number $m$ from the sequence and map the $m$th odd natural that has not yet been paired, with the first even natural that has not yet been paired.
5. Finally convert each bijection $f$ from odds and evens (which was only about odds and evens in order to make the previous step easier to describe) to a permutation of $\mathbb N$, namely $n\mapsto f(2n+1)/2$.

Answer 2

I'm using the convention that $\mathbb{N}$ includes $0$. This is important when it comes to indexing: the earliest term of a sequence will be called the $0$th, not the $1$st.

I'll give an explicit bijection between $S_\mathbb{N}$ and the set of infinite sequences of natural numbers. It's well-known how to get from this to $\mathbb{R}$. This definitely isn't fun to work with, but it illustrates (what I think is) a nice idea which comes up a lot in logic: constructions via requirements and recording information. Although right now it's really just one way of cooking up a bijection "by brute force," down the road it will become a fundamental technique, and personally I think it captures one of the main "flavors" of the subject.

The first idea is to specify a permutation $\pi$ by a "back-and-forth" process. The terms in the sequence corresponding to $\pi$ will denote facts about $\pi$. The second idea will be to record only "non-redundant" information, and this is how we'll get surjectivity.

Specifically, we define the following list of questions:

• $Q_{2i}$: "What is $\pi(i)$?"

• $Q_{2i+1}$: "What is $\pi^{-1}(i)$?"

As written, this gives us an obvious way to assign a sequence of naturals to a given permutation (let the $n$th term be the answer to $Q_n$). However, this assignment is far from surjective. To fix this, we'll want to "thin" the process. We observe that answers to earlier questions constrain the answers to later questions. This can happen in two ways:

• Removing specific values: If we know that the answer to $Q_0$ is $3$, then we know that the answer to $Q_2$ can't be $3$.

• Completely answering the question: If we know the answer to $Q_0$ is $3$ then we automatically know that the answer for $Q_{2\cdot 3+1}$ is $0$.

The key observation now is the following:

Based on (consistent) answers to $Q_m$ for $m<n$, either there are infinitely many possible consistent answers to $Q_n$ or the answer to $Q_n$ is completely determined from the information so far.

This tells us how we'll build our sequence $f_\pi$ assigned to a permutation $\pi$:

For the $n$th term, we look at the next still-open question on our list, and write the order of the answer from among the "legal" values.

---

Here's an example:

Take $\pi$ to be the permutation switching $2k$ and $2k+1$ for each $k$.

• $0$th term of $f_\pi$: Our first question is $Q_0$. Since we have no data so far, this is an "open" question. $\pi(0)=1$; this is the $1$st possible value based on the information so far (remember: our indexing starts at $0$, not $1$). So the $0$th term of $f_\pi$ is $1$.

• $1$st term of $f_\pi$: Our next question is $Q_1$, and it remains open based on the information we have so far. $\pi^{-1}(0)=1$; this is the $0$th possible value based on the information so far, since "$\pi^{-1}(0)=0$" is clearly impossible given the previous step. So the $1$st term of $f_\pi$ is $0$.

• $2$nd term of $f_\pi$: Our next question is $Q_2$, but this is not open due to our answer to $Q_1$. Similarly, $Q_3$ isn't open anymore because of our answer to $Q_0$. So the next open question is $Q_4$ ("where does $\pi$ send $2$?"), and the answer ("$3$") is the $1$st of the values which appear legal at this stage. So the $2$nd term of $f_\pi$ is $1$.

• In general, it's easy to see that $$f_\pi=1,0,1,0,1,0,...$$

---

And here's an example in the opposite direction:

Take $f$ to be the sequence $0,1,2,3,...$ (= the identity sequence). What permutation $\pi$ does it correspond to?

• Well, the $0$th term of $f$ has to be $\pi$'s answer to $Q_0$; so we know that $\pi(0)=0$.

• Based on that, $Q_1$ isn't open anymore, so the $1$st term of $f$ must be $\pi$'s answer to $Q_2$ ("where does $\pi$ send $1$?"). Since the $1$st term of $f$ is $1$, and $0$ is already spoken for, we know $\pi(1)=2$.

• Now $Q_3$ is still open. The possible $\pi$-preimages for $1$ are everything except $0$ and $1$. Since the next term of $f$ is $2$, we know that $\pi^{-1}(1)=4$ (since at this stage $2$ would be the $0$th possible value and $3$ would be the $1$st possible value for $\pi^{-1}(1)$)

• And so on.