Real Numbers and Power Set of Natural Numbers – Analysis

elementary-set-theoryreal-analysis

I have learnt that the cardinality of the power set of the natural numbers is equal to the cardinality of the real numbers. What is the function that gives the one-to-one correspondence between these two sets?

I have also learnt that there exists no set whose cardinality is strictly between the natural numbers and the real numbers. Is there a proof of this or at least some intuitiveness behind it?

Best Answer

It's not quite correct to ask for "the function", because if there is one then there are many. Moreover, explicit bijections are highly overrated. We can write one, but it's much much oh so much easier to use the Cantor-Bernstein theorem, and simply exhibit two injections.

If you do insist on writing an actual bijection, let me identify $\mathcal P(\Bbb N)$ with infinite binary sequences (which is quite standard). Now let me describe the steps. We would like to take a binary sequence to the real number in $[0,1]$ which has this binary string as an expansion. However some numbers, e.g. $\frac12=0.1\bar0_2=0.0\bar1_2$, one sequence with finitely many $1$'s and the other has finitely many $0$'s.

  1. First enumerate all the strings which contain finitely many $0$'s the strings containing finitely many $1$'s. One can show that both sets are countably infinite, one can even enumerate them in a very nice way. Write them as $p_n$ for the $n$-th sequence with finitely many zeros and $q_n$ for the $n$-th sequence with finitely many $1$'s.

    The next step is to take $f\colon2^\Bbb N\to2^\Bbb N$ defined as: $$f(x)=\begin{cases} q_{2k} & x=p_k\\ q_{2k+1} & x=q_k\\ x &\text{otherwise}\end{cases}$$ Easily this is an injection whose range is $2^\Bbb N\setminus\{p_n\mid n\in\Bbb N\}$.

  2. Now map $x\in2^\Bbb N$ to $r\in[0,1)$ such that, $$r=\sum_{n\in\Bbb N}\frac{f(x)}{2^{n}}$$ that is the real number whose binary expansion is $f(x)$. One can show that this is a surjective function, since if a number has a binary expansion then it has one which has infinitely many $0$'s. It is also injective since if a real number one has two different binary expansions then we can show that exactly one of them has finitely many $0$'s and the other finitely many $1$'s. But since we use $f(x)$, this is impossible.

  3. Find a bijection between $[0,1)$ and $\Bbb R$. Usually one does that by first "folding $0$ in" and having a bijection between $[0,1)$ and $(0,1)$ and then using something like $\frac{2x-1}{x(x-1)}$ or a similar function for a bijection with $\Bbb R$.


Using the Cantor-Bernstein theorem is much easier.

  1. First note that that $\Bbb R$ can inject into $\mathcal P(\Bbb Q)$ by mapping $r$ to $\{q\in\Bbb Q\mid q<r\}$. Since $\Bbb Q$ is countable there is a bijection between $\cal P(\Bbb Q)$ and $\cal P(\Bbb N)$. So $\Bbb R$ injects into $\cal P(\Bbb N)$.

  2. Then note that we can map $x\in2^\Bbb N$ to the continued fraction defined by the sequence $x$. Or to a point in $[0,1]$ defined by $\sum\frac{x(n)}{3^{n+1}}$, which we can show is injective in a somewhat easier proof.

Finally, as mentioned the last part is false. From the usual axioms of modern set theory (read: $\sf ZFC$) we cannot prove nor disprove that there are no intermediate cardinalities between $\Bbb N$ and $\Bbb R$. The proof of that is difficult and require a deep understanding of modern [read: axiomatic] set theory, as well logic.

If the last part somehow confused you, perhaps my answer to this question can help, Why is the Continuum Hypothesis (not) true?.