Proving $\operatorname{card} \mathbb{R} = \operatorname{card} 2^{\mathbb{N}}$ *without* using Cantor-Schröder-Bernstein theorem?

Question

On math.stackexchange.com and elsewhere proofs of the equality $\operatorname{card} \mathbb{R} = \operatorname{card} 2^{\mathbb{N}}$, or equivalently the equality $\operatorname{card} \mathbb{R} = \operatorname{card} \mathcal{P}(\mathbb{N})$, abound that use the Cantor-Bernstein theorem.

What is a proof that does not use that theorem?

P.S. All the proofs that I previously knew, including those appearing in two undergraduate texts I authored, use CB and prove CB there, too.

Answer 1

Cantor-Schröder-Bernstein is typically used to deal e.g. with ambiguous binary expansions. We can construct an explicit bijection that does not even use binary expansions of real numbers (though writing the full map down is prehaps an arduous task - but you can check that each of the following steps can be made explicit):

First, let $\mathcal P_\infty(\Bbb N)=\{\,A\in\mathcal P(\Bbb N): |A|=\infty\,\}$ and show $$|\mathcal P(\Bbb N)|=|\mathcal P_\infty(\Bbb N)|$$ by playing Hilbert's Hotel with the finite and the cofinite subsets (both are in obvious bijection with $\Bbb N$ per binary expansion)

Next, we find a bijection between $\mathcal P_\infty(\Bbb N)$ and $\Bbb N^{\Bbb N}$ by mapping the infnite ordered set $\{a_0,a_1,a_2,\ldots\}$ to the sequence $a_0,a_1-a_0-1,a_2-a_1-1,a_3-a_2-1,\ldots$

Next, use continued fractions to biject $\Bbb N^{\Bbb N}$ with $(0,\infty)\setminus\Bbb Q$.

So far, we have an explicit bijection $\mathcal P(\Bbb N)\to (0,\infty)\setminus\Bbb Q$. Use a shift-by-one to establish a bijection $\mathcal P(\Bbb N)\to \{\pm1\}\times \mathcal P(\Bbb N)$ and combine with the above to find a bijection $\mathcal P(\Bbb N)\to \Bbb R\setminus\Bbb Q$. Finally, play Hilbert's Hotel again (e.g., using an explicit enumeration of $\Bbb Q$ and $\sqrt 2+\Bbb Q$)

Answer 2

Consider the set of numbers

$\quad B =\displaystyle{ \{\sum_{k=1}^n a_k 2^{-k} \mid n \ge 1 \land a_k \in \{0,1\} \} }$

Now $B \subset [0,1)$ but standard mathematical techniques allow us to insist that

$\quad B \cap (0,1] = \emptyset$

It is left to the OP to construct a bijection between $\Bbb R$ and $B \sqcup (0,1]$.

We now define a function $\Phi$ between $2^\Bbb N$ and $B \sqcup (0,1]$ by taking the sequence $\vec a = (a_n) \in 2^\Bbb N$ and

$\;$If there exist an $N \gt 0$ such that $a_k = 0$ for $k \gt N$ then $\Phi(\vec a) = \displaystyle{ \sum_{k=1}^N a_k 2^{-k}} \in B$,
Else
$\;$$\Phi(\vec a) = \displaystyle{ \sum_{k=1}^\infty a_k 2^{-k}} \in (0,1]$.

It is not difficult to show that $\Phi$ is a well-defined bijective function.

Answer 3

This is my preferred proof, one that avoids the Cantor-Bernstein theorem. It is just a bit different from that in https://math.stackexchange.com/a/4193008/32337.

Denote $\mathbb{N} \setminus \{0\}$ by $\mathbb{N}^{\ast}$. It suffices to show that $\operatorname{card} 2^{\mathbb{N}^{\ast}} = \operatorname{card}(0, 1)$. Let $C$ be the set of binary sequences $(b_{n})_{n \in \mathbb{N}^{\ast}}$ that are eventually constant and let $B = 2^{\mathbb{N}^{\ast}} \setminus C$, the set of those that are not. Since $B$ of $2^{\mathbb{N}^{\ast}}$ is denumerable while the interval $(0, 1)$ is uncountable, a ``Hilbert's hotel'' maneuver shows that $\operatorname{card} \bigl((0, 1) \cup B\bigr) = \operatorname{card} (0, 1)$. Hence it suffices to show that $\operatorname{card} 2^{\mathbb{N}^{\ast}} = \operatorname{card} \bigl((0, 1) \cup B\bigr)$.

From order-completeness of $\mathbb{R}$, for each $x \in (0, 1)$, there is a unique $(x_{n})_{n \in \mathbb{N}^{\ast}} \in B$ for which $x = \sum_{n =1}^{\infty} x_{n}/2^{n}$. Define the map $f \colon 2^{\mathbb{N}^{\ast}} \to (0, 1) \cup B$ as follows: If $b \notin C$, then $f(b) = \sum_{i=1}^{\infty} b_{i}/2^{i}$; but if $b \in B$, then $f(b) = b$. Then $f$ is the desired bijection.