Explicit bijection between $\Bbb R$ and permutations of $\Bbb N$
Solution 1:
It's not exactly pretty, but we can do something like:
- 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$
- 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} $$
- 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.
- 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.
- 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$.
Solution 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.