Is there any known explicit bijection between these two sets?

I know it can be proved that such bijection exists using two injections and Schröder–Bernstein theorem, but I wanted to know whether some explicit bijection is known. I failed to find any except ones constructed awkwardly from the Schröder–Bernstein theorem.

  • 2
    $\begingroup$ The construction in the proof of Schröder-Bernstein is constructive. So first select two explicit injections and go from there. $\endgroup$ – GEdgar Feb 7 '16 at 21:48
  • $\begingroup$ Note that you can't hope for too nice a bijection: if we give $\mathcal{P}(\mathbb{N})$ the obvious topology, then it's not homeomorphic to $\mathbb{R}$, so no bijection can be continuous. On the other hand, we can find bijections which are continuous except on a countable set. (Also I'm pretty sure this has been asked here before . . .) $\endgroup$ – Noah Schweber Feb 7 '16 at 21:57
  • $\begingroup$ I remember seeing something about using continued fractions here. $\endgroup$ – Omnomnomnom Feb 7 '16 at 21:58
  • $\begingroup$ To the OP: you probably know this already, but anyway, there's a very nice bijection between $\mathcal{P}(\mathbb{N})$ and the Cantor set; see here. $\endgroup$ – goblin Feb 7 '16 at 22:03

First note that the set $\mathcal P_{\text{fin}}(\Bbb N)$ of finite subsets of $\Bbb N_0$ is in bijection with $\Bbb N_0$: $$ \begin{align}\alpha\colon \mathcal P_{\text{fin}}(\Bbb N)&\to \Bbb N\\A&\mapsto \sum_{k\in A}2^k\end{align}$$

Every real number $a\in[0,1)$ as a binary expansion $a=\sum_{k=0}^\infty a_k2^{-k-1} $ with $a_k\in\{0,1\}$. For those cases with two expansions we pick the one ending in zeroes. Now we map $$ \begin{align}\beta\colon [0,1)&\to \mathcal P(\Bbb N)\\a&\mapsto \{\,k\in\Bbb N\mid a_k=0\,\}\end{align}$$ This one fails to be bijective: We leave out precisely the finite subsets of $\Bbb N$. In other words, we have a bijection $$ \beta\colon [0,1)\to\mathcal P(\Bbb N)\setminus \mathcal P_{\text{fin}}(\Bbb N)$$ The rest is glueing and playing Hilbert's Hotel: We have a bijection $$ \begin{align}\gamma\colon \Bbb R&\to (0,\infty)\\x&\mapsto e^x\end{align}$$ and a bijection $$ \begin{align}\delta\colon (0,\infty)&\to [0,\infty)\\x&\mapsto \begin{cases}x-1,&x\in\Bbb N\\x,&\text{otherwise}\end{cases}\end{align}$$ and a bijection $$ \begin{align}\epsilon \colon [0,\infty)&\to [0,1)\\x&\mapsto\begin{cases} \frac1{1+x},&x>0\\0,&x=0\end{cases}\end{align}$$ All in all this gives us a bijection $$ \zeta\colon \Bbb R\stackrel{\beta\circ\epsilon\circ\delta\circ\gamma}\longrightarrow \mathcal P(\Bbb N)\setminus\mathcal P_{\text{fin}}(\Bbb N)$$ To complete the construction we have to hide countably many finite sets by defining for example $$ \begin{align}\eta \colon \Bbb R&\to \mathcal P(\Bbb N)\\x&\mapsto\begin{cases}\alpha^{-1}(x),&x\in\Bbb N\\ \zeta(x-\sqrt 2),&x=n+m\sqrt 2\text{ with }n\in\Bbb N, m\in\Bbb N_{>0}\\ \zeta(x),&\text{otherwise}\end{cases}\end{align}$$


This answer is incomplete, but it at least makes the Schröder-Bernstein a bit nicer.

Firstly, $[0,1)$ bijects with $\mathbb{R}$, by the following bijections:

$h: (0, 1) \to \mathbb{R}$ by $x \mapsto \tan(\frac{\pi}{2} (2x-1))$

$i: [0,1) \to (0,1)$ by $\frac{1}{n} \mapsto \frac{1}{n+1}$, $0 \mapsto \frac{1}{2}$, and $x \mapsto x$ otherwise.

Now, we show bijections with the set $S$ of (possibly countably infinite) sequences of $0$s and $1$s, and with $S'$ which is the subset of $S$ such that no sequence ever ends in infinitely many $1$s.

$f: [0,1) \to S'$ is defined by taking the binary expansion of the input number, where we insist that no expansion never ends in infinitely many $1$s if there is the choice. For example, $$0.011\bar{1} = 0.10\bar{0}$$ so we choose the latter.

$g: \mathcal{P}(\mathbb{N}) \to S$ is defined by $\{ a_1, a_2, \dots \}$ being sent to the sequence which has $1$s in exactly positions $a_1, a_2, \dots$.

Finally, a bijection between $S$ and $S'$ is provided by Schröder-Bernstein, which is improved by the fact that $S'$ is a subset of $S$ so the injection one way is simply inclusion. The injection the other way could be "prepend a 0 if you don't end with infinitely many $1$s; otherwise prepend a 1 and replace all but one of the final infinitely-many 1s with 0s".


You can do this by steps:

  1. There are reasonably nice bijections between $[0,1]$ and $(0,1)$, and between $(0,1)$ and $\Bbb R$. So there is a reasonably nice bijection between $[0,1]$ and $\Bbb R$.

  2. There is an almost bijection between $\mathcal P(\Bbb N)$ and $[0,1]$ using binary expansions: $f(A)=\sum_{n\in A}2^{-n}$ (for simplicity, let's take $0\notin\Bbb N$, otherwise take $2^{-n-1}$ in the sum).

    The injectivity fails because finite and co-finite sets might have the same output. Namely, $\frac12=0.10000\ldots=0.011111\ldots$.

  3. Fix the situation: there is a reasonable bijection between the sets $\{A\subseteq\Bbb N\mid\Bbb N\setminus A\text{ is finite}\}$ and $\{A\subseteq\Bbb N\mid A\text{ or }\Bbb N\setminus A\text{ is finite}\}$.

Now we combine all these together.

Given a set $A$, if it is finite or co-finite, map it to a co-finite set using the reasonably looking bijection from part 3. Then map it to a real number in $[0,1]$ using binary expansion as in part 2. Then map this to a real number in $\Bbb R$ by passing through $(0,1)$.

It ain't pretty. But it's explicit, as all the maps can be written explicitly. The trickiest is the third part, of course, but it's not hard by noting that you can encode "finite" and "co-finite" using $0$ being in the finite set, and then work accordingly. Namely,

$$F(A)=\begin{cases}\{n-1\mid n\in A\setminus\{0\}\} & 0\in A\\ \{n\mid n\notin A\} & 0\notin A\end{cases}$$


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.