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))

  • 1
    $\aleph_0^{\aleph_0}\le(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\aleph_0}=2^{\aleph_0}$. – egreg Sep 14 at 12:34

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).

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.