A surjection: $\mathcal{P}(\mathbb{N}) \rightarrow [0, 1]$; the reals are uncountable

If $\mathbb{X}\subset \mathbb{N}$ we may define a real number $R(\mathbb{X})$ using binary expansion:

• $R(\phi) = 0$
• $${\textrm{if $\mathbb{X} \ne \phi$, then} \hspace{3pt} R(\mathbb{X}) = \sum_{n \in \mathbb{X}} 2^{-n}}$$.

For example we have:

• $${R(\mathbb{N}) = \sum_{n \in \mathbb{N}} 2^{-n} = \sum_{n \in \ma... ...}\right)^n = \frac{\left(\frac{1}{2}\right)}{1 - \left(\frac{1}{2}\right)} = 1}$$
• $${R(\{1\}) = \sum_{n \in \{1\}} 2^{-1} = \frac{1}{2}}$$
• $${R(\{2, 4\}) = 2^{-2} + 2^{-4} = \frac{1}{4} + \frac{1}{16} = \frac{5}{16}}$$
• $${R(\mathbb{N} - \{1\}) = \sum_{1 < n \in \mathbb{N}} 2^{-n} = \su... ... = \frac{\left(\frac{1}{4}\right)}{1 - \left(\frac{1}{2}\right)} = \frac{1}{2}}$$
• $${ R(\{2k: k \in \mathbb{N}) = \sum_{k \in \mathbb{N}} 2^{-2k} = \... ... = \frac{\left(\frac{1}{4}\right)}{1 - \left(\frac{1}{4}\right)} = \frac{1}{3}}$$
• $${ \textrm{For any positive integer $t$}, \hspace{3pt} R(\{tk: k \... ...left(\frac{1}{2^t}\right)}{1 - \left(\frac{1}{2^t}\right)} = \frac{1}{2^t - 1}}$$.
• For any positive integer $m$, we have:
  $$R(\mathbb{N}_m) = \sum_{k = 1}^m 2^{-k} = 1 - 2^{-m}, \hspace{10p... ...athbb{N}- \mathbb{N}_{m}) = \sum_{k = m + 1}^\infty 2^{-k} = 2^{-m} = R(\{m\}).$$

Here we have used the standard formula for the sum of a geometric series:

$$\sum_{n \in \mathbb{N}} ar^n = \frac{a}{1 - r}, \hspace{3pt} \textrm{provided}\hspace{3pt} \vert r\vert < 1.$$

Next we have:

• For any $\mathbb{X}\subset \mathbb{N}$, we have $0 \le R(\mathbb{X})\le 1$.
  Also $R(\mathbb{X}) = 0$ if and only if $\mathbb{X} = \phi$, whereas $R(\mathbb{X}) = 1$ if and only if $\mathbb{X} = \mathbb{N}$.
• For any subset $\mathbb{X}$ of $\mathbb{N}$, we have $${R(\mathbb{X}) + R(\mathbb{N} - \mathbb{X}) = 1}$$
• For any subsets $\mathbb{X}$ and $\mathbb{Y}$ of $\mathbb{N}$, we have:
  $$R(\mathbb{X}\cup \mathbb{Y}) + R(\mathbb{X}\cap \mathbb{Y}) = R(\mathbb{X}) + R(\mathbb{Y}),$$
  $$R(\mathbb{X}- \mathbb{Y}) + R(\mathbb{Y}- \mathbb{X}) + 2R(\mathbb{X}\cap\mathbb{Y}) = R(\mathbb{X}) + R(\mathbb{Y}).$$

• The set $\mathbb{X}\subset \mathbb{N}$ is a finite set if and only if $\sup(\mathbb{X}) \in \mathbb{N}$ exists, if and only if $R(\mathbb{X}) \ne 1$ and there exists a positive integer $m$ such that $2^mR(\mathbb{X})$ is an integer.
  Here the minimum such integer $m$ is $\sup(\mathbb{X})$.
• When $\mathbb{X}$ is finite, with $\sup(\mathbb{X}) = n$, we define:
  $$\mathbb{X}' = (\mathbb{X}- \{n\})\cup (\mathbb{N}- \mathbb{N}_n)\subset \mathbb{N}.$$
  Then we have:
  $$\mathbb{X}' - \mathbb{X}= \mathbb{N}- \mathbb{N}_n,$$
  $$\mathbb{X}- \mathbb{X}' = \{n\},$$
  $$\mathbb{X}\cap \mathbb{X}' = \mathbb{X}- \{n\}.$$
  In particular, since $\mathbb{X} - \mathbb{X'} \ne \phi$, we have $\mathbb{X} \ne \mathbb{X}'$.
  But then we have:
  $$R(\mathbb{X}) + R(\mathbb{X}') = R(\mathbb{X}- \mathbb{X}') + R(\mathbb{X}' - \mathbb{X}) + 2R(\mathbb{X}\cap\mathbb{X}')$$
  $$= R(\{n\}) + R(\mathbb{N}- \mathbb{N}_n) + 2R(\mathbb{X}- \{n\}) = 2^{-n} + 2^{-n} + 2(R(\mathbb{X}) - 2^{-n}) = 2R(\mathbb{X}).$$
  So $R(\mathbb{X}) = R(\mathbb{X}')$ and yet $\mathbb{X} \ne \mathbb{X}'$.
  So the map $R$ is not injective.

In general, from the theory of binary expansions for real numbers, the map $R$ has the properties:

• $R$ is a well-defined surjective map from $\mathcal{P}(\mathbb{N})$ to the real interval $[0, 1]$.

To prove surjectivity, given the real number $x$ in the interval $(0, 1)$, we construct a sequence of approximations $x_n = R(\mathbb{X}_n)$ where $\mathbb{X}_n \subset \mathbb{N}$ is a finite set, such that $x_n = R(\mathbb{X}_n) \le x < x_n + 2^{-n-1}$ and $\mathbb{X}_n \subset \mathbb{X}_{n + 1}$, for each $n \in\mathbb{N}$.

For example for $x = \frac{1}{5}$ we have:

$$x_1 = R(\mathbb{X}_1) = 0 \le \frac{1}{5} < \frac{1}{2}, \hspace{7pt}\mathbb{X}_1 = \phi,$$

$$x_2 = R(\mathbb{X}_2) = 0 \le \frac{1}{5} < \frac{1}{4}, \hspace{7pt} \mathbb{X}_2 = \phi,$$

$$x_3 = R(\mathbb{X}_3) = \frac{1}{8} = \frac{1}{2^3} \le \frac{1}{5} < \frac{1}{4}, \hspace{7pt} \mathbb{X}_3 = \{3\},$$

$$x_4 = R(\mathbb{X}_4) = \frac{3}{16} = \frac{1}{2^3} + \frac{1}{2^4} \le \frac{1}{5} < \frac{1}{4}, \hspace{7pt} \mathbb{X}_4 = \{3, 4\},$$

$$x_5 = R(\mathbb{X}_5) = \frac{3}{16} = \frac{1}{2^3} + \frac{1}{2^4} \le \frac{1}{5} < \frac{7}{32}, \hspace{7pt} \mathbb{X}_5 = \{3, 4\},$$

$$x_6 = R(\mathbb{X}_6) = \frac{3}{16} = \frac{1}{2^3} + \frac{1}{2^4} < \frac{1}{5} < \frac{13}{64}, \hspace{7pt} \mathbb{X}_6 = \{3, 4\},$$

$$x_7 = R(\mathbb{X}_7) = \frac{25}{128} = \frac{1}{2^3} + \frac{1}... ...}{2^7} < \frac{1}{5} < \frac{13}{64}, \hspace{7pt} \mathbb{X}_5 = \{3, 4, 7\},$$

$$x_8 = R(\mathbb{X}_8) = \frac{51}{256} = \frac{1}{2^3} + \frac{1}... ...^8} < \frac{1}{5} < \frac{13}{64}, \hspace{7pt} \mathbb{X}_5 = \{3, 4, 7, 8\}.$$

Continuing in this vein, we find that:

$$\mathbb{X}= \{3, 4, 7, 8, 11, 12, 15, 16, \dots\} = \{4k - 1: k \in \mathbb{N}\} \cup \{ 4m: m \in \mathbb{N}\}.$$

Check: we have:

$$R(\mathbb{X}) = \sum_{k \in \mathbb{N}} \frac{1}{2^{4k- 1}} + \su... ... \in \mathbb{N}} \frac{1}{2^{4m}} = 3 \sum_{m \in \mathbb{N}} \frac{1}{2^{4m}}$$

$$= 3\sum_{m \in \mathbb{N}}\left( \frac{1}{2^4}\right)^m = 3\sum_{... ...ft(\frac{1}{16}\right)}{1 - \frac{1}{16}} = \frac{3}{16 - 1} = \frac{1}{5} = x.$$

This procedure can be carried out for any real $x$ in $(0, 1)$ and in the limit as $n \rightarrow \infty$ we have $x_n \rightarrow x$ and then $\mathbb{X} = \bigcup_{n = 1}^\infty \mathbb{X}_n$ obeys $R(\mathbb{X}) = x$.

• For $\mathbb{X}$ and $\mathbb{Y}$ subsets of $\mathbb{N}$, with $\mathbb{X} \ne \mathbb{Y}$, we have $R(\mathbb{X}) = R(\mathbb{Y})$ if and only if (exactly) one of the sets $\mathbb{X}$ or $\mathbb{Y}$ is a finite non-empty set:
  • Then if $\mathbb{X}$ is finite and non-empty, we have $\mathbb{Y} = \mathbb{X}'$.
  • Alternatively, if $\mathbb{Y}$ is finite and non-empty, we must have $\mathbb{X} = \mathbb{Y}'$.
• So, given a real number $x \in [0, 1]$, the number of solutions of the equation $R(\mathbb{X}) = x$ with $\mathbb{X}\subset \mathbb{N}$ is:
  • Exactly one, if and only if no solution $\mathbb{X}$ is a finite non-empty set, if and only if $x$ is 0 or $1$ or $2^m x$ is never an integer, for any positive integer $m$.
  • Exactly two, if and only if there is a solution $\mathbb{X}$, which is a finite non-empty set, if and only if $x$ is not 0 or $1$, but $2^m x$ is an integer, for some positive integer $m$, in which case the other solution is the set $\mathbb{X}'$.

Now suppose that the reals form a countable set.
Then the real interval $[0, 1]\subset \mathbb{R}$ must also be countable.
Now the surjective map $R: \mathcal{P}(\mathbb{N})\rightarrow [0, 1]$ gives the formula:

$$\mathcal{P}(\mathbb{N}) = \bigcup_{x \in [0, 1]} R^{-1}(\{x\}).$$

As discussed above, for any $x \in [0, 1]$, the set $R^{-1}(\{x\})$ contains either exactly one element of $\mathcal{P}(\mathbb{N})$, or exactly two elements.
In either case the set $R^{-1}(\{x\})$ is countable.
So if $[0, 1]$ is countable the formula: $\mathcal{P}(\mathbb{N}) = \bigcup_{x \in [0, 1]} R^{-1}(\{x\})$ writes $\mathcal{P}(\mathbb{N})$ as a countable union of countable sets, so $\mathcal{P}(\mathbb{N})$ is countable.
This contradicts Cantor's Power Set Theorem, which says in particular, that the set $\mathcal{P}(\mathbb{N})$ is uncountable, since $\mathbb{N}$ is countably infinite, so $\vert\mathbb{N}\vert < \vert\mathcal{P}(\mathbb{N}\vert$, so $\mathcal{P}(\mathbb{N}))$ is uncountable.
So we have proved that the reals are uncountable and we are done.