# 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}$?

-
en.wikipedia.org/wiki/Continued_fraction –  user2468 Mar 10 '12 at 20:52
It all depends on how mathematical this non-mathematician is. For the less mathematical I honestly think the simplest way would involve using Cantor–Bernstein–Schroeder and phrasing the two halves as "there are no more reals than sets of naturals" and vice versa. I think CBS is a theorem that a non-mathematician could be convinced of without too much difficulty; not with anything that would approach mathematical rigour, mind you. Avoiding CBS seems to involve nitty-gritty details that would make the average non-mathematician glassy-eyed, and the heart of the ideas might become lost. –  Arthur Fischer Mar 10 '12 at 22:24
@Jan: I am a set theorist. It's not that my research focuses on finding "roots of polynomials" and whatnot. In particular I deal in my M.Sc. with behavior of cardinals in the absence of the axiom of choice. I always enjoy trying explaining those to people, especially other barflies at the local pub. It is very baffling to people that there are different sizes of infinity. It is equally baffling when you see it for the first time with the full definitions and proofs, people telling you otherwise are likely to lack the actual understanding - and further discussion is just further confusing. –  Asaf Karagila Mar 10 '12 at 23:49
@Jan Some theorems admit a "proof by picture," where you a give a convincing proof-sketch without actually writing anything down, but most theorems do not have proofs that fall under this category. Something like "There is a bijection between $\mathbb{R}$ and the set of all subsets of $\mathbb{N}$" will almost certainly involve at least a few steps and some non-trivial terminology. That doesn't mean it's complicated (it's just the composition of a few "nice" bijections), it's just not as basic as most ideas encountered in high school. –  you Mar 10 '12 at 23:51
@Jan: Diagonal arguments are good for showing that certain things cannot exist (or in rare and subtle cases that things which do exist cannot have certain properties, like the Gödel sentence having a proof). However here you must show that a bijection does exist, so a diagonal argument won't be of avail. Also for technical reasons (as ordered sets $\mathbb R$ and $\mathcal{P}(\mathbb N)$ have fundamentally different properties), such a bijection cannot be entirely "smooth". Which explains what an effortless proof is not possible. –  Marc van Leeuwen Mar 11 '12 at 12:08

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

-
Binary expansion doesn't give a bijection, though, because of the repeating nines problem. (Repeating ones in this case, I suppose.) –  Steven Taschuk Mar 10 '12 at 21:03
Nuts, you're right. Do you know of a way to modify it into a bijection, or do we need to invoke Schroeder-Bernstein somewhere? (thus making it a proof for non-non-mathematicians) –  you Mar 10 '12 at 21:05
Update: I found a discussion of the issue here: nrich.maths.org/discus/messages/67613/67678.html?1133563921 When I get a chance, I'll add the necessary fix to my post –  you Mar 10 '12 at 21:14
Shouldn't the first bijection by $\frac{1}{\pi} \arctan(x) + \frac12$? –  Patrick Mar 10 '12 at 21:38
(cont.) If someone understands just those arguments he did not understand what the axiom of choice was. Let alone the axiom of determinacy which is flat out a technical axiom, and you cannot explain what it is without first explaining what it determines and why it is needed. As a result of all these questions I grow tired of the internet telling people of advanced results which they want to fully understand right away without sitting through books and courses and studying for years, months or even days. $${}$$ Sorry for the rant in the comments... :-) –  Asaf Karagila Mar 11 '12 at 1:45

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

-
Your step $3$ doesn't work if the bit sequence contains only finitely many zeros; you could make it code for a finite sequence of natural numbers (exactly as many as there are zeros) in that case (which actually is an advantage since continued fractions can be finite; however note that finite continued fractions are two for one rational value). Maybe this is what you say in point 4 ("ends with infinite stream of zeros") but it is not clear which sequence you mean, and if it's the bit sequence, then an infinite stream of ones is special. –  Marc van Leeuwen Mar 11 '12 at 12:36
@dtldarek: Just what does it mean that "P(N) it the same as infinite sequence of 0s and 1s"? How can I picture this in the simplest possible way? Thanks, J. –  Jan Mar 11 '12 at 19:06
@Jan: That $\mathcal P(\mathbb N)$ is in bijection with infinite sequences of $0$s and $1$s is immediate: term $i$ of the sequence is $1$ if $i$ is in your chosen subset of $\mathbb N$, and it is $0$ if not. I'm surprised you should ask, since it would seem that the diagonal argument showing that $\mathcal P(\mathbb N)$ is uncountable already uses this image (or one very close to it). –  Marc van Leeuwen Mar 12 '12 at 7:59
@Marc van Leeuwen: Thank U, Marc, now I get it. But will Your surprise be any lesser, when I explain that for the proof of the uncountability of P(N) it was perfectly enough for me to understand that, say, the set of all the "outer" (not-contained) representations of P(N) in N cannot have an adquate representation in N? Thanks again, Jan. –  Jan Mar 12 '12 at 11:40
@MarcvanLeeuwen Indeed my step 3 didn't work, I fixed that up. I know that there are two representations of every rational as a continued fraction, thus I worked with shortest representations--those never end with $1$ (in fact somehow I forgot to add +1 to the last term one more time, but that's just my own carelessness). Thank you very much for your comment! –  dtldarek Mar 12 '12 at 18:12

Here is a bijection inspired by the one given by dtldarek, but I've tried to reformulate as non-technical as possible. Instead of continued fractions, I make use of the related Stern-Brocot tree (or better, one with root $0$ and completed with a reflected image added to its left so as to cover the negative numbers as well as the positive numbers).

But I won't need a technical description of it. In fact I can do with any tree labelled by rational numbers (or one could even allow arbitrary real numbers), with the following properties:

• For any node labelled by a number $y$, the labels $x$ of all nodes in the left subtree below it have $x<y$, and the labels $z$ of all nodes in the right subtree below it have $z>y$.
• If at this node $y$ node one goes to the left child, and then keeps going from a node to its right child indefinitely, one gets a sequence of (increasing) labels $x$ that converges to $y$.
• If at this node $y$ node one goes to the right child, and then keep going from a node to its left child indefinitely, one gets a sequence of (decreasing) labels $z$ that converges to $y$.
• If from the root node one descends to the left (resp. right) child indefinitely, the decreasing (resp. increasing) sequence of labels obtained diverges to $-\infty$ (resp. to $+\infty$).

These properties guarantee that the (countable) set of all labels forms a dense subset of the real numbers (the set of all rationals in the case of the symmetrized Stern-Brocot tree), and that for any real number $r$ that do not occur in the tree, one has a unique a infinite path whose labels converge to $r$, which can be found by using the tree as a binary search tree: when at a label $y$, descend to the left subtree if $r<y$ and to the right subtree if $r>y$. Note that since $r$ is not itself a label this is well defined, and the infinite path so obtained will not beyond some point continue to go in one same direction indefinitely, in other words, it keeps on (ultimately) changing direction, forever.

Now the basic idea is to use, given a subset $S$ of $\mathbb N$, the presence/absence of succesive numbers to determine the direction of descent in the tree; say go left at step $i$ if $i\notin S$ and right if $i\in S$. Except for the two extreme possibilities, the labels along the infinite path obtained converge, and taking their limit almost defines a bijection to the real numbers (with $\{-\infty,\infty\}$ added to it for the diverging extremes).

However the map is not injective: all numbers that occur as a label $y$ are the limit for $2$ different paths, both passing though the node labelled $y$: one that descends to the left child of $y$ and then to the right forever, and another that descends to the right child of $y$ and then left forever. This defect, as well as the diverging extremes, can almost be repaired by the following rule: for those paths that beyond some point continue indefinitely in the same direction (these correspond to subsets of $\mathbb N$ that are either finite or the complement of a finite set), stop after the last move in the opposite direction, and take as image the label of the node reached. This change removes the two infinite paths whose labels converged to $y$, and replaces it by the unique path that was of the form: descend to $y$, change direction there and after that never change direction any more.

The one tiny defect that remains is that for the two extreme paths, our rule stipulates to truncate after the last step in the opposite direction, which step does not exist: the natural thing to do here is to remove all steps, and map to the label of the root of the tree ($0$ for the symmetrized Stern-Brocot tree). The two subsets that "collide" here are the empty set and all of $\mathbb N$. To repair this I start by modifying $\mathcal{P}(\mathbb N)$ so as to "tuck away" (make disappear) the empty set. The following rule does this: for all finite initial segments, i.e. subset of the form $\{i\in\mathbb N\mid i<n\}$ for some $n\in\mathbb N$ (which includes the empty set for $n=0$), add to it the minimal element $n$ originally absent form it. This maps $\mathcal{P}(\mathbb N)$ bijectively to $\mathcal{P}(\mathbb N)\setminus\{\emptyset\}$, and after this transformation one can use the map described above, which now is a bijection to $\mathbb R$. Oof!

-
Interesting argument. I wouldn't exactly call it non-technical though :P It seems to require that you understand what it means for $\mathbb{Q}$ to be dense in $\mathbb{R}$, which most lay-people don't –  you Mar 11 '12 at 15:48
@you: If a layperson doesn't understand that real numbers can be approximated arbitrarily well by rationals, but that it takes (in general) infinitely many of then to pick out a specific real number, then there is no point in explaining why the reals are uncountable. –  Marc van Leeuwen Mar 11 '12 at 17:53
@ Marc van Leeuwen: Oooof, indeed! I would say that this description realy is helpfull, although it took me just over 3 hours at least to get some feel for it. Thank you, Jan –  Jan Mar 11 '12 at 19:15

For this answer, use $\{1,2,\ldots\}=\mathbb{N}$.

A. For each positive real $x\in (0,1]$ there is a unique infinite subset $A$ of $\mathbb{N}$ such that $x = \sum_A 2^{-p}$.

(To find numbers in $A$ one could start with some $p$ so that $2^{-p}$ is at least half the distance to $x$, but not $x$ itself. Then continue with that idea for each remaining distance.)

B. Every infinite subset of $\mathbb{N}$ corresponds to an element of $(0,1]$ in this way.

(Have them imagine adding up all those $2^{-p}$'s and appeal to their intuitive sense of convergence of an increasing bounded series.)

C. Now just use $f(x) = \tan(\pi x - \frac\pi2)$ which takes $(0,1)$ onto $\mathbb{R}$ (and don't worry about the endpoint $1$). This shows that the infinite subsets of $\mathbb{N}$ are equinumerous with $\mathbb{R}$.

(One could explain it by stretching $(0,1)$ out until it "becomes" $\mathbb{R}$.)

D. As the collection of finite subsets of $\mathbb{N}$ is countable, this completes the proof.

(Wave hands and say something like "finite sets are smaller than infinite sets" ;)

-
The "stretching" of (o,1) into R is realy a perfect example of just what I had in mind when I asked for an explanation for non-mathematicians. But I then one can also imagine that "Sigmas" and the "2s to the power of -p" isn't exactly the language I+m used to... Thank U, J. –  Jan Mar 11 '12 at 1:35
The uniqueness in point A (which is in fact "decimal" expansion in base $2$) fails, because of the "repeating nines" phenomenon: the sets $\{1\}$ and its complement $\{2,3,4\ldots\}$ both determine the number $\frac12$ for instance. This phenomenon complicates every "expansion" based construction in a nasty way. –  Marc van Leeuwen Mar 11 '12 at 12:50
@Marc - That's why i required that $A$ be infinite. Then there's no problem. –  Patrick Mar 11 '12 at 14:10

Here's my attempt to make the steps as mathematically non-threatening as possible, even at the expense of elegance:

We start from any real number, and wish to transform it into an unique set of natural numbers, such that every subset of $\mathbb N$ is hit exactly once.

Step 1: Squeeze the real line into the half-open interval between $0$ and $1$:

• If the number was $0$, then it stays unchanged.
• If the number was a positive integer $n$, then replace it with $\frac 1{2n}$.
• If the number was a positive non-integer, say $+x$, then replace it with $\frac1{2(x+1)}$.
• If the number was negative, say $-y$, then replace it with $\frac12 + \frac1{2(y+1)}$.

(This is not a particularly nice way to do this, mathematically speaking, but it is easier to understand than many slicker alternatives).

Pause. Satisfy yourself that every number between 0 (inclusive) and 1 (exclusive) is hit exactly once.

Step 2: Write down the decimal fraction for the number. It will start by "0." followed by a countably infinite sequence of decimals. If you can represent the number exactly with finitely many digits, top it up with infinite repeating 0s that the back end. Don't use representations that end in infinitely many '9's.

(There's a considerable amount of mathematical sophistication being swept under the rug in this step, but I'm assuming you're intuitively familiar with decimal fractions, and know that $0.999... = 1$).

Step 3: Remove the initial 0..

Pause. Satisfy yourself that every infinite sequence of digits is hit exactly once, except that sequences that end in infinite repeated 9s are not hit.

Step 4: Encode the digits as ones and zeroes, using a table such as

0 becomes 0000    5 becomes 0101
1 becomes 0001    6 becomes 0110
2 becomes 0010    7 becomes 0111
3 becomes 0011    8 becomes 10
4 becomes 0100    9 becomes 11


The precise details of the encoding are not important, except to note that if we encode any sequence of digits in this way, we don't need to keep around any separators between successive digits. You can reconstruct the digits without them, because the first bit of an encoded digit determines whether it's a 4-bit or a 2-bit encoding. Furthermore, a sequence that ends in infinite repeating 9s (but only such sequences) would map to a sequence ending in infinite repeating 1s.

Pause. Satisfy yourself that every infinite sequence of digits is hit exactly once, except that sequences that end in infinite repeated 1s are not hit.

Step 5: Get the sequences that end in infinite repeated 1s included, by this rule:

• If the sequence already has infinitely many 1s (which must be interspersed with infinitely many 0s in some pattern or non-pattern), then leave it as it is.
• If the sequence only has finitely many 1s, and it starts with a 0, then chop off the initial 0 and leave it otherwise as it is.
• If the sequence only has finitely many 1s and starts with an 1, then chop off the initial 1, and flip every remaining element in the sequence from 1 to 0 or vice versa.

Pause. Satisfy yourself that every infinite sequence of zeroes or ones is hit exactly once, no exceptions.

Step 6: Take the subset of $\mathbb N$ consisting of the positions in the sequence where an 1 is found.

Satisfy yourself that every subset of $\mathbb N$ is hit exactly once.

-