The number of permutations of $\mathbb{N}$

Question

Let $\mathbb{N}!$ be the set of permutations of the natural numbers.

With $\aleph_0 = \text{card}\ \mathbb{N}$ you need two facts of cardinal arithmetic to show that the number of permutations of $ \mathbb{N}$ ($\aleph_0! = \text{card}\ \mathbb{N}!$) equals the cardinality of the continuum ($ 2^{\aleph_0} = \text{card}\ \mathbb{R}$):

1. $\aleph_0\ ! = \aleph_0^{\aleph_0}$
   _{because $\aleph_0 = \aleph_0 -k$ for each $k \in \mathbb{N}$}

2. $\aleph_0^{\aleph_0} = 2^{\aleph_0}$
   _{It's easy to see that $\aleph_0^{\aleph_0} \geq 2^{\aleph_0}$ but why is $\aleph_0^{\aleph_0} \leq 2^{\aleph_0}$? (Find the answer below in user egreg's comment.)}

I wonder if the following proof – which is more constructive – is valid and interesting. (If it's a well-known proof, please give me a hint, I did not find a reference.) It assumes that you have a representation of the natural numbers (as Cantor did in his diagonalization proofs). For the sake of specificity let's choose the binary representation.

Let $\mathcal{N}$ be the set of normal numbers starting with 1, i.e. $n = 0.1d_2d_3d_4d_5\dots$. It is known that $\text{card}\ \mathcal{N} = \text{card}\ \mathbb{R}$. It is also known that each normal number contains every sequence of digits infinitely often.

Now the proof goes like this:

1. There is an injective function from $\mathbb{N}!$ to $\mathcal{N}$ which sends each permutation $\pi$ of $\mathbb{N}$ to the unique number $n(\pi) = 0.\pi(1)\pi(10)\pi(11)\pi(100)\pi(101)\dots$ which is normal.
   _{Added: The last claim ("which is normal") is just an assumption, which makes the proof conditional. Even for the identity permutation $\pi_1$ with $\pi_1[k] = k$ and $n(\pi_1) = 0.1\ 10\ 11\ 100\ 101\dots$ it took a proof of its own to show that $n(\pi_1)$ is normal!}

2. There is an injective function from $\mathcal{N}$ to $\mathbb{N}!$ which sends each normal number $n = 0.1d_2d_3d_4d_5\dots$ to the unique permutation $\pi(n)$ as explained in this example for $n = 0.10101101011\dots$, written more suggestive as $n = 0.10\ 101\ 1010\ 11\dots$:

   • Start with the first digit and go to the right until $d_3 = 1$ which yields $\pi(1)=10$.

   • Do the same with $d_3$: Go to the right until $d_5 = 1$. While the next candidate ($10$) has already been created take one more digit, which yields $\pi(2) = 101$

   • $\pi(3) = 1010$

   • $\pi(4) = 11, \dots$.

This way you will eventually find and create all numbers, since normal numbers contain each sequence of digits infinitely often.

So we have

1. $\text{card}\ \mathbb{N}! \leq \text{card}\ \mathcal{N}$

2. $\text{card}\ \mathcal{N} \leq \text{card}\ \mathbb{N}!$

3. $\text{card}\ \mathcal{N} = \text{card}\ \mathbb{N}!$ (by the Schröder-Bernstein theorem)

4. $\text{card}\ \mathcal{N} = \text{card}\ \mathbb{R}$

from which it follows that $\text{card}\ \mathbb{N}! = \text{card}\ \mathbb{R}$.

It's not surprising to see, that you could define a group on $\mathcal{N}$ by $x \circ y = n(\pi(x) \circ \pi(y))$ (if the above proof was correct). Note that the identity element $e$ of this group is the Champernowne constant $C_2 = 0.11011100101110111\dots = 0.862240\dots$. (Note, that it is not obvious that $C_2$ is a normal number: it had to be proved (1992))

Answer 1

The number you construct in step 2 is not necessarily normal. We can generate a non-normal number of this form explicitly by:

• When $n=2k$ let $\pi(n)$ be $2^k$.
• When $n=2k+1$ is odd, let $\pi(n)$ be the smallest number not yet used that is not a power of $2$.

The length of $\pi(n)$ for even $n$ grows much quicker than the length of $\pi(n)$ for odd $n$, which means that the limiting density of $1$ bits is $0$. However this density must, by definition, be $1/2$ for the number to be normal.

---

Also, the $\pi$ you produce in step 2 is not necessarily surjective, so it may not be a permutation. Even though the binary representation of of the input contains any bit string infinitely many times, it may be that all of its appearances come at a point in the binary expansion where you're not starting a new number (because what comes immediately before it has already been used).

For example you can make an example of this by taking the Champernowne constant and insert an 1 bit each time you would otherwise be about to read out 10 as the next number: $$ 0.1\;\underline{1}10\;11\;\underline{1}100\; \underline{1}101\; 11011\; 11000 \; \underline{1} 1001\; \ldots $$ producing the sequence $$ 1, 6, 3, 12, 13, 27, 24, 25, \ldots $$ which by construction never hits $2$. Since the numbers become longer and longer, the inserted $1$s will eventually be so rare that the limiting densities of anything stays what it ought to be, so the modified number is still normal (in base 2).