Cardinality of a set of real numbers

Question

Is there a way to prove $|ℝ|=|P(\omega)|$? Will it help to show ℝ is uncountable?

Answer 1

Yes, there is a way, and yes, it helps proving that $\Bbb R$ is uncountable.

First, why it helps: Cantor's theorem says that for any set $A$, we have $|A|\lneq |P(A)|$. This means that if we do prove the result, we get $|\omega|\lneq |P(\omega)|=|\Bbb R|$.

As for the result itself, the most immediate route would be to construct a bijection. However, the Cantor-Bernstein-Schröder theorem says that if we can construct an injection either way, then we may use those to construct a bijection. Therefore I will just construct an injection either way, and leave the bijection to the theorem. The $0.111\ldots = 1$ (in binary) problem makes explicitly constructing a bijection cumbersome.

First, two intermediate bijections. A bijection between $P(\omega)$ and the set $2^{\aleph_0}$ of infinite binary sequences (sequences of $0$ and $1$): Take a subset $A\subseteq \omega$. Then the corresponding binary sequence $(a_n)_n$ is given by $a_n = 1$ if $n\in A$, and $a_n = 0$ if $n\notin A$. You should check that this is indeed a bijection. Also, I assume you know that there are bijections between the interval $[0, 1)$ and $\Bbb R$.

Now we can work with comparing $2^{\aleph_0}$ to $[0,1)$ instead. First, and injection $[0,1)\to 2^{\aleph_0}$. Take a number $x\in [0,1)$ and express it in binary. If you have a choice in how to do it (i.e. if $x$ has a finite binary expansion), choose the finite expansion and pad with infinite zeroes at the end. That binary expansion (if we lose the $0.$ at the start) is an infinite sequence of $0$ and $1$, and is therefore easily interpretable as an element of $2^{\aleph_0}$.

As for an injection the other way, take an infinite sequence of $0$ and $1$, put $0.$ in front of it, and interpret it as a real number in ternary.

We now have an injection either way, and therefore it is possible to construct a bijection between $[0,1)$ and $2^{\aleph_0}$, which we compose with the above bijections to get a bijection between $\Bbb R$ and $P(\omega)$, proving that $|\Bbb R| = |P(\omega)|$.