# Using the Cantor-Bernstein theorem

I'm working through Kolmogorov and Fomin's Introductory Real Analysis text, and I came to a question about showing that some sets have the same power as the continuum. I have seen this question posted on here before, but I decided to post this anyways because I have solutions to the 3 parts of the question and am specifically looking for feedback on if I am using the Cantor-Bernstein theorem correctly. I'll just post one of the sets, since the method I used for the other two is identical.

So, the first set to be considered is the set of all $n$-tuples of real numbers, denoted as $N$. Let $f:N\rightarrow [0,1]$ be a function that takes each entry of an $n$-tuple, takes their non-decimal part and interleaves this with the decimal part like so: $(x_1,x_2,x_3,...,x_n) \mapsto 0.r_1r_2r_3...r_nx_{11}x_{21}x_{31}...x_{n1}...x_{ij}$, where $1 \leq i \leq n$ and $1 \leq j < \infty$, with $n$ incrementing by one each time a decimal part would repeat infinitely. In this way, we identify an unique real number in $[0,1]$ with each $n$-tuple.

Now, for the injection from $\mathbb{R} \to N'$. For each real number $x$, let the function $g$ identify $x$ with an unique "degenerate" $n$-tuple of the form $(x,0,0,...,0)$. These degenerate $n$-tuples clearly form a subset $N' \subset N$, and we have the second injection.

Since we have an injection $g$ from $\mathbb{R} \to N'\subset N$ and an injection $f$ from $N\rightarrow [0,1] \subset \mathbb{R}$, by the Cantor-Bernstein theorem, $N \sim \mathbb{R}$.

So, my questions are (1) is my proof correct, (2) is this proper usage of Cantor-Bernstein theorem, and (3) is it conventional to show injectivity of the functions even after defining them explicitly?

Edited to change the definition of the injection from $N\rightarrow [0,1]$ based on suggestions in the comments.

• How exactly are you putting $n$ real numbers, consecutively, in a decimal expansion? – Slade Oct 15 '14 at 8:13
• By their decimal expansions. I should have specified that, should I edit the original post to reflect that? Also, your question has me worried now, is this impossible? – epsilonics Oct 15 '14 at 8:16
• It's going to be difficult if the reals in the n-tuple are irrational: suppose you start with $(\pi, e, ...)$ how does the concatenated decimal appear ? The answer is to interleave the digits in the decimal expansion. – Tom Collinge Oct 15 '14 at 8:46
• @epsilonics This approach can certainly work. One nice trick, if you're trying to construct an injection, is to use a different base. i.e. pick some particular decimal expansion, then map your numbers over in base $11$. – Slade Oct 16 '14 at 8:41
• @epsilonics Oh, I just noticed that bof's solution contains a kind of version of this trick. He takes binary sequences, which you'd usually think to put in base 2, and puts them in base 10. This neatly avoids the issue that two different binary sequences can give the same number in base 2, but always give different ones in base 3 or larger. – Slade Oct 16 '14 at 9:50

Decimal expansions are messy and complicated, especially when you're dealing with arbitrary real numbers. This is not what you asked for, but I'm going to show you how to do it without decimal expansions.

Let $r_1,r_2,r_3,\dots$ be an enumeration of the rational numbers.

For $x\in\mathbb R$ define $f_n(x)=1$ if $r_n\lt x$, and $f_n(x)=0$ otherwise.

The mapping $x\mapsto(f_1(x),f_2(x),f_3(x),\dots)$ is an injection from $\mathbb R$ into $\{0,1\}^\mathbb N$, the set of all infinite binary sequences.

The mapping $(x,y)\mapsto(f_1(x),f_1(y),f_2(x),f_2(y),f_3(x),f_3(y),\dots)$ is an injection from $\mathbb R\times\mathbb R$ into $\{0,1\}^\mathbb N$.

(In a similar way you can define an injection from $\mathbb R^n$ or $\mathbb R^\mathbb N$ into $\{0,1\}^\mathbb N$.)

Finally, $(x,y)\mapsto\frac{f_1(x)}{10}+\frac{f_1(y)}{10^2}+\frac{f_2(x)}{10^3}+\frac{f_2(y)}{10^4}+\frac{f_3(x)}{10^5}+\cdots$ is an injection from $\mathbb R\times\mathbb R$ into $\mathbb R$.

• Thanks for the answer! That's an interesting method, it's going to take some self-convincing to feel like that will generate a unique decimal number for each real in [0,1]. – epsilonics Oct 15 '14 at 18:42
• You're welcome. This is probably a language problem, but I don't understand what you mean by the statement "that will generate a unique decimal number for each real in $[0,1]$." What will do what?? If you can restate that more formally, maybe I can clarify my answer. – bof Oct 15 '14 at 21:29
• I meant that the method you gave would give a one-to-one pairing for each tuple in R^n and a unique real number in [0,1]. Sorry for the confusion, let me know if I'm still not being sensible. – epsilonics Oct 16 '14 at 1:59
• OK, by "each real in $[0,1]$" you meant "each tuple in $\mathbb R^n$. If you don't mind I'll stick to the case $n=2$ because it's easier to write and the general case is similar. I still don't see why you're worried about "uniqueness". Of course the infinite series (on the last line of my answer) converges, the numerators are $0$s and $1$s; and of course a convergent series converges to a unique sum. – bof Oct 16 '14 at 2:31
• I guess you want to see why the map from $\mathbb R^2$ to $\mathbb R$ is injective? (Of course it's not surjective; the injection from $\mathbb R$ to $\mathbb R^2$ is obvious, so we're going to use the Cantor-Bernstein theorem.) The map is a composition:$$(x,y)\to(f_1(x),f_1(y),\dots)\to\frac{f_1(x)}{10^1}+\frac{f_1(y)}{10^2}+\cdots.$$ Do you have doubts about the injectivity of the first map, or the second one, or both of them? – bof Oct 16 '14 at 2:36