15
$\begingroup$

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. :/

$\endgroup$
  • 2
    $\begingroup$ The Schröder–Bernstein theorem does construct one explicitly. It is given, intuitively, by using one of the injections where you can, and the inverse of the other injection where you have to. The subset given by "where you have to" is a bit complicated to describe, but it can be done on one line. $\endgroup$ – Arthur May 28 '18 at 8:58
  • $\begingroup$ Hmm. I see what you mean, but what an unsatisfying answer. Nevertheless, it seems to be one. Why not post it as an answer instead of a comment? I think I've asked the wrong question, because I'd really like to see it done without Schröder–Bernstein, by just defining a mapping in one direction or the other. $\endgroup$ – G Tony Jacobs May 28 '18 at 9:21
  • 1
    $\begingroup$ I see from this old answer that the answer to my question above is yes, assuming choice. $\endgroup$ – Jair Taylor May 29 '18 at 21:09
  • 1
    $\begingroup$ @JairTaylor: More generally it is true when A is a well-orderable infinite set. It is easy to show (in ZF, for arbitrary $A$ with at least 2 elements) that $$ |\mathcal P(A)|\le|S_{A\times A}| \quad\text{and}\quad |S_A|\le|\mathcal P(A\times A)|$$ and when $A$ is infinite well-orderable we have $|A\times A|=|A|$, so $|\mathcal P(A)|=|S_A|$. $\endgroup$ – Henning Makholm May 30 '18 at 19:57
  • 1
    $\begingroup$ @JairTaylor For finite $n$, the Factorial number system is basically equivalent to the "Fisher shuffle" algorithm I described in a deleted answer; that approach turns out to have some problems with ensuring that its results correspond to an actual permutation as opposed to pushing certain numbers out 'infinitely far'. You might be able to make it work, but it's likely to be trickier than you'd think. $\endgroup$ – Steven Stadnicki May 31 '18 at 22:13
6
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ Step 4 here is how you patch the hole in Steven Stadnicki's deleted answer :-) $\endgroup$ – Henning Makholm May 30 '18 at 19:19
  • 1
    $\begingroup$ I think it's fairly pretty, to be honest, but I'm not quite seeing how it's a bijection. In step 5, when we convert a bijection between evens and odds into a permutation "in the obvious way", how does this give us all the permutations? Maybe I'm not seeing what "the obvious way" is, but how would we get, say the identity permutation, from an even-odd bijection? $\endgroup$ – G Tony Jacobs May 30 '18 at 20:00
  • $\begingroup$ Your trick for getting rid of the rationals, in particular, is much nicer than what I was thinking of. I was ready to enumerate algebraic numbers of each degree, and then use those enumerations to map degree $n$ to degree $n+1$. Yours is far cleaner and actually something I could work with. $\endgroup$ – G Tony Jacobs May 30 '18 at 20:01
  • 1
    $\begingroup$ @GTonyJacobs: If $f$ maps odds bijectively to evens, then $g(n)=f(2n+1)/2$ maps $\mathbb N$ bijectively to itself. I hope it is clear that every permutation of $\mathbb N$ arises in this way from exactly one bijection odds$\to$evens? $\endgroup$ – Henning Makholm May 30 '18 at 20:12
  • $\begingroup$ (But in hindsight I can see that this might not be quite obvious if one gets sidetracked into thinking about something like $f\cup f^{-1}$ instead). $\endgroup$ – Henning Makholm May 30 '18 at 20:18
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.