Set Theory – Bijection Between the Reals and Permutations of Natural Numbers

elementary-set-theorysequences-and-series

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?

Best Answer

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.

Related Question