The simplest way of proving that $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = c$

What is the simplest way of proving (to a non-mathematician) that the power set of the set of natural numbers has the same cardinality as the set of the real numbers, i.e. how to construct a bijection from $\mathcal{P}(\mathbb{N})$ to $\mathbb{R}$?

Solution 1:

Here's my favourite (most intuitive one I've seen): Define the bijection in three parts

First is easy: take your favourite bijection between $\mathbb{R}$ and $(0,1)$. (Even to a non-mathematician it is intuitively clear that one exists by just "contracting" $\mathbb{R}$, and one example can be give explicitly by $\frac{1}{\pi}arctan(x) +\frac{1}{2}$).

Then by considering the binary expansion of real numbers we almost get a bijection between $(0,1)$ and the set $S$ of infinite binary strings, where the number $0.1001110110010\dots$ corresponds to the string $0.1001110110010\dots$ etc. I say "almost" because the binary strings $100000\dots$ and $01111\dots$ correspond to the same real number $0.10000 \dots = 0.01111\dots$ To a non-mathematician you could say "we can fix these problems because there aren't many stings with repeated $1$'s, compared to the set of ALL binary strings" and move on.
(To a mathematician, this is because a string ending in all $1$'s is determined by its prefix, which has finite length, and mathematicians know that the set of finite binary strings is countable, and furthermore by the diagonalization argument $\mathbb{R}$ is UNcountable. This allows you to modify the natural map $S\rightarrow (0,1)$ into one which is a bijection using the method described at the bottom of this link: https://nrich.maths.org/discus/messages/67613/67678.html?1133563921 But like I said, to a non-mathematician these issues aren't important.)

Finally, another easy one: a binary string $s\in S$ is by definition a sequence of $0$'s and $1$'s, which can technically be defined as simply a function $s:\mathbb{N}\rightarrow\{0,1\}$. Such a function determines a subset $A_s\subset\mathbb{N}$ by "$a\in A_s$ iff $s(a)=1$" and similarly a subset determines a function (we call $s$ the characteristic function of $A_s$ in $\mathbb{N}$). An intuitive way to think of this phenomenon as that a binary string $s$ goes through the elements of $\mathbb{N}$ one-by-one and decides if it is in the set $A_s$ (with a $1$) or not (with a $0$). This correspondance gives the bijection between $S$ and the powerset $\mathcal{P}(\mathbb{N})$.

Combining it all together, we get $\left|\mathbb{R}\right|=\left|(0,1)\right|=\left|S\right|=\left|\mathcal{P}(\mathbb{N})\right|$

P.S. This is the sort of discourse in which the vast majority of people first come to understand this theorem, because this is the context in which it is phrased: sets and functions and clever bijections. If you would prefer a more elementary description then I will paraphrase what Euclid told a general under Alexander the Great: there is no royal road to mathematics. This is as elementary as I can make it without writing an introduction on set theory :)

Solution 2:

If it has to be a bijection I would go for continued fractions (as pointed out by J.D.):

1. State that for every real number there is only one shortest representation of it as a continued fraction ($a_0 \in \mathbb{Z}$, $a_i \in \mathbb{N}-\{0\}$ and if the fraction is finite, $a_{\text{last}} \in \mathbb{N}-\{0,1\}$ ).
2. Then explain that $P(\mathbb{N})$ it the same as infinite sequence of 0s and 1s.
3. Show that infinite sequence of 0s and 1s is the same as sequence of natural numbers of any length (coded in base 1 with ones interleaved by zeros, i.e. 2,3,0,1,0,0,0... = 11 0 111 0 0 1 00000..., finite sequence have finite number of zeros, empty sequence = 11111...).
4. Sequence of natural numbers is a continued fraction:
   • empty sequence is 0;
   • sequence of length 1 should be transformed by any $\mathbb{N} \to \mathbb{Z} -\{0\}$ bijection;
   • if the sequence is of length 2 or greater, transform first term by any $\mathbb{N}\to\mathbb{Z}$ bijection and add $1$ to the rest;
   • if the sequence is finite, increase the last term by additional 1.

This is the simplest bijection I could think of. But probably it doesn't have to be a bijection, in which case the argument is much simpler:

1. For a given set $X$, first sort it.
2. Take first smallest number, if it is odd, the result is negative.
3. Take the second smallest, this will be the integer part of the real.
4. Take the rest (in ascending order) all modulo $10$--this will be the tail of the real.

Going back:

1. Take only reals from $[0,1]$, where $1$ is represented by $0.(9)$,
2. $n \in Y$ if and only if the digit on the $n$-th place is odd.

Edit 1: to simplify a bit the step 4 in the bijection, you could interpret the sequence of natural numbers in a way that the first one tell how many 1s are there on the end of stream.

Edit 2: I missed the case of finite number of zeros in (3), thanks to Marc van Leeuwen for pointing that out. I think that the result after the fix is even nicer than before.

Hope that helps ;-)