3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ You could always make one injection each way and use that to explicitly construct a bijection, rather than relying on the theorem to tell you there is one. Which is to say, use the proof of the CSB theorem. $\endgroup$
    – Arthur
    Commented Jul 6, 2021 at 22:00
  • $\begingroup$ What have you tried? It is a bit fiddly, but you can use binary or decimal expansions to prove this using an ad hoc construction of a bijection between $\Bbb{R} \sqcup \Bbb{N}$ and $\Bbb{R}$ to handle the countable set of numbers that have two distinct expansions. I think this approach is conceptually worse than using the CSB theorem $\endgroup$
    – Rob Arthan
    Commented Jul 6, 2021 at 22:13
  • $\begingroup$ @RobArthan: I find attractive the idea of dissecting $\mathbb{R}$ into a sequence of subinervals and reassembling the pieces into $\mathbb{R} \setminus C$ with $C$ a denumerable set. Actually, dissecting $(0, 1)$ and reassembling the pieces into $(0, 1) \setminus D$ with $D$ denumerable subset of the interval. And then combining the obvious bijection from the binary sequences not having tails of all 0s to the reals with a bijection from the remaining binary sequences. (I'll try writing down all the details and then post the answer if I can before somebody else beats me to it.) $\endgroup$
    – murray
    Commented Jul 7, 2021 at 0:54

3 Answers 3

3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ To the step of using continued fractions I say "ouch!". I think that's a lot "worse" than applying CSB, whereas I'm looking for something that, while surely not as short and sweet as a proof using CSB, at least is pretty simple. $\endgroup$
    – murray
    Commented Jul 6, 2021 at 22:45
  • 2
    $\begingroup$ @murray: so, I ask again, what have you tried? Continued fractions are beautiful and natural, much more so than the arbitrary functions that show up in the Cantor-Schröder-Bernstein theorem. Please show us that you have done some work on your problem. $\endgroup$
    – Rob Arthan
    Commented Jul 6, 2021 at 23:37
  • 3
    $\begingroup$ You do have to write down a formula, one way or another, for your desired bijection. What do you imagine such a simple formula would be, that would input a real number and output a subset of $\mathbb N$? $\endgroup$
    – Lee Mosher
    Commented Jul 7, 2021 at 0:03
  • 1
    $\begingroup$ Arnold Miller's book begins with an argument for bijecting $\mathbb N^{\mathbb N}$ and the irrationals that avoids continued fractions. $\endgroup$ Commented Jul 7, 2021 at 2:02
  • $\begingroup$ @AndrésE.Caicedo: there are many Arnold Millers. Please quote the title of the book you are citing. $\endgroup$
    – Rob Arthan
    Commented Jul 8, 2021 at 23:58
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Should the bijection I'm to construct not be between $\mathbb{R}$ and $B \sqcup [0, 1)$? And is it not a bit simpler to use $(0, 1)$ rather than $[0, 1)$? $\endgroup$
    – murray
    Commented Jul 11, 2021 at 15:00
  • $\begingroup$ There are many reasonable ways to go about defining a bijection. I took my cue from Rob Arthan's comment and wanted something that minimized the amount of fiddling around - I didn't want a kludge presentation. Aesthetically, I liked the idea of mapping the $0$ (binary) sequence to the number zero and the $1$ sequence to the number one and everything else in-between. It turned out in the presentation that the $0$ sequence is mapped to $0 \in B$ (finite expansions go $B$) and the $1$ sequence is s mapped to $1 \in (0,1]$ (infinite expansions go there). $\quad$ Post your solution also! $\endgroup$ Commented Jul 11, 2021 at 15:32
  • $\begingroup$ Also, as a response to your comment, I changed my answer by fiddling around with the interval endpoints. It should make more sense now. $\endgroup$ Commented Jul 11, 2021 at 15:41
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .