# 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. – Chris Eagle Feb 11 '13 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. – Todd Wilcox Feb 11 '13 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. – Todd Wilcox Feb 12 '13 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. – Brian M. Scott Feb 12 '13 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? – Todd Wilcox Feb 12 '13 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 ... – Brian M. Scott Feb 12 '13 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. – Brian M. Scott Feb 12 '13 at 2:35

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.

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? – Todd Wilcox Feb 11 '13 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$? – Todd Wilcox Feb 11 '13 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}$. – Chris Eagle Feb 11 '13 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. – Todd Wilcox Feb 11 '13 at 20:12
• Where does Wikipedia claim that $2^{\aleph_0}=\aleph_1$? – Chris Eagle Feb 11 '13 at 20:17