# Bijection between the reals and the set of permutations of the natural numbers?

In analysis today we talked about re-arrangements of sequences, and one student asked how many re-arrangements there are of a given sequence. We were able to very quickly create a one-to-one function from the reals to the set of permutations on $\mathbb{N}$ by simply noting that for any real number, there is a re-arrangement of a conditionally convergent series that converges to that number.

What we were not easily able to do was either prove that function was onto, or create an injection from the permutations on $\mathbb{N}$ back to the reals. So we know the number of re-arrangements is at least the cardinality of the reals, can we show it is exactly the same as the cardinality of the reals?

• You don't just know that the number of rearrangements is "at least uncountable", you know it is at least the cardinality of the reals. For some reason a lot of people seem to say one when they mean the other. Feb 11, 2013 at 19:04
• Oh, I just learned that it's not yet proved whether the reals have the "smallest" uncountable cardinality or not. I've edited the question accordingly. In the defense of all those who mix up the two phrases: I could swear someone equated the two in the past, but maybe I misinterpreted a statement like the reals are the smallest uncountable field or something like that. Feb 11, 2013 at 19:40

Here you’ll find a proof that the infinite continued fractions with $0$ integer part are precisely the irrationals in $(0,1)$. The map

$$\left(\Bbb Z^+\right)^{\Bbb Z^+}\to(0,1):a\mapsto[0;a_1,a_2,a_3,\dots]$$

is therefore an injection.

• I'm not advanced enough to firmly link that with my question - but let me take a shot at it: $(\mathbb{Z}^+)^{\mathbb{Z}^+}$ is the set of all functions from $\mathbb{N}$ to $\mathbb{N}$? Then.. ummm.. $a$ is a particular function? And... I'm not used to seeing a semicolon in math. Is that supposed to be interval notation on the far right? I can't tell if my question is too easy or too complex to get an answer that I can understand. Feb 12, 2013 at 1:56
• @Todd: My $\Bbb N$ includes $0$, which is why I used $\Bbb Z^+$, but yes, $\left(\Bbb Z^+\right)^{\Bbb Z^+}$ is the set of functions from $\Bbb Z^+$ to $\Bbb Z^+$. Yes, $a$ is a particular function, though I’m writing $a(k)$ as $a_k$. No, that’s not interval notation; that’s standard notation for a continued fraction, as used at the link that I gave. Feb 12, 2013 at 2:02
• I think I'm very close. $a\in (\mathbb{Z}^+)^{\mathbb{Z}^+}$ and $a_1, a_2, a_3,\ldots$ is an explicit list of the range of $a$. Then we have $\phi:(\mathbb{Z}^+)^{\mathbb{Z}^+} \rightarrow (0,1)$ where $\phi(a)=[0;a_1,a_2,a_3,\ldots]$. And $\phi$ is an injection because if $\phi(a)$ and $\phi(b)$ represent the same continued fraction, then $a=b$ must be true. So the cardinality of the permutations on $\mathbb{N}$ must be both greater than or equal to and less than or equal to the cardinality of the reals, and therefore they are equal. Did I understand correctly? Feb 12, 2013 at 2:17
• @Todd: Close. $\langle a_1,a_2,\dots\rangle$ is the function $a$: a function with domain $\Bbb Z^+$ is just a sequence. I did not require the functions to be permutations, so there may be repetitions. However, the set of permutations of $\Bbb Z^+$ is a subset of $\left(\Bbb Z^+\right)^{\Bbb Z^+}$, so an injection from $\left(\Bbb Z^+\right)^{\Bbb Z^+}$ to $\Bbb R$ automatically gives one from the set of permutations of $\Bbb Z^+$ to $\Bbb R$. The map $\varphi$ is injective because every irrational in $(0,1)$ has a unique continued fraction expansion, so two different sequences ... Feb 12, 2013 at 2:35
• ... give two different continued fractions which must represent different irrationals. The rest is fine: this gives an injection from permutations of $\Bbb Z^+$ to $\Bbb R$, and you already had one in the other direction. The result now follows from the Schröder-Bernstein theorem. Feb 12, 2013 at 2:35

The number of permutations of $\Bbb{N}$ is at most the number of functions from $\Bbb N$ to $\Bbb N$, which is $\aleph_0^{\aleph_0}$. But $\aleph_0^{\aleph_0} \le (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0 \cdot \aleph_0}=2^{\aleph_0}$.

• Thanks. I know $\aleph_0$ is the cardinality of the natural numbers, otherwise I don't know that notation. Also, can you direct me to a proof of your answer? Feb 11, 2013 at 19:08
• Ok, I understand your cardinal arithmetic now. But I have one question: $2^{\aleph_0}=\mathfrak{c}$ or $2^{\aleph_0}=\aleph_1$ or $2^{\aleph_0}=\mathfrak{c}=\aleph_1$? Feb 11, 2013 at 19:51
• $2^{\aleph_0}$ is the cardinality of the powerset of $\Bbb N$, which is the same as the cardinality of the reals, and is also called $\mathfrak{c}$. Feb 11, 2013 at 20:02
• Ok, Wikipedia confusingly says in one place that $2^{\aleph_0}=\mathfrak{c}$ and in another place it says $2^{\aleph_0}=\aleph_1$. I'm going to upvote your answer since it was certainly educational and wait to see if I can get a more straightforward answer about an actual bijection before I accept anything. Feb 11, 2013 at 20:12
• Where does Wikipedia claim that $2^{\aleph_0}=\aleph_1$? Feb 11, 2013 at 20:17

I have just done this as an exercise in my introductory Set Theory text.

Let $( a_1, a_2, \dots )$ be a permutation of $\mathbb N$.

For each $a_i$, form a string of $(a_i-1)$ zeros followed by a $1$. Call this string $s_i$. For example, if $a_i = 5$, then $s_i = 00001$.

Define a mapping $f : (a_1, a_2, \dots ) \mapsto 0.s_1s_2s_3\dots$, where $0.s_1s_2\dots$ is the concatenation of the strings $s_i$.

Then $f$ gives the desired injection when $0.s_1s_2\dots$ is read as the binary expansion of $x \in [0,1]$. The injection going the other way can be obtained as per your OP.

Edit : Come to think of it, you don't need to view the image as a binary expansion. It works equally well as a decimal expansion.