Cardinality and bijections

Question

i am following a course in axomatic set theory. We are talking about bijections, injections, Schröder-Bernstein-theorem, etc. at this moment. I want to make te following exercises:

• Prove: $\mathbb{R}\approx\mathbb{N}^{\mathbb{N}}$
• Prove: $\mathbb{R}^{\mathbb{N}}\approx\mathbb{R}^{\mathbb{Q}}\approx\mathbb{R}$
• Prove: $\{f\in\mathbb{R}^{\mathbb{R}}:f \text{ is continuous}\}\approx\mathbb{R}$

Can someone give hints about the constructions of the two injections to apply Schröder-Bernstein-theorem of a construction of a bijection or the idea to make such a construction?! I like this manner of mathematical thinking but i can not get a idea of this. Some inspirations? Some ideas??

Thank you very much :)

P.S.: We should not conclude this results with computations of cardinality but with bijections etc.!

Answer 1

Some extended HINTS: Every real number $x$ can be written uniquely in the form $$x=n+\sum_{k\ge 1}\frac{d_k}{10^k}\;,$$ where $n$ is an integer, each $d_k\in\{0,1,\ldots,9\}$, and $\{k\in\Bbb Z^+:d_k\ne 0\}$ is infinite. (If $x>0$, this is just the non-terminating decimal expansion of $x$. It represents $0$ as $-1+0.\overline9$, and you should think about how it represents negative $x$.) The map

$$\Bbb R\to\Bbb N^\Bbb N:x\mapsto\langle n,d_1,d_2,d_3,\ldots\rangle$$

is therefore an injection.

The slick way to get an injection from $\Bbb N^{\Bbb N}$ to $\Bbb R$ is to use continued fractions. The continued fractions $[a_1,a_2,a_3,\ldots]$ with all $a_k>0$ are precisely the irrational numbers in $(0,1)$, each of which has a unique continued fraction expansion, so the map that takes the sequence $\langle n_0,n_1,n_2,\ldots\rangle\in\Bbb N^{\Bbb N}$ to the continued fraction $[n_0+1,n_1+1,n_2+1,\ldots]$ is an injection. (My $\Bbb N$ includes $0$, so I have to add $1$ to each $n_k$ to ensure that I get a positive integer.)

There are other ways to do it.

Given $\sigma=\langle n_k:k\in\Bbb N\rangle$, let $m_0=n_0$ and $m_{k+1}=m_k+n_{k+1}+1$ for each $k\in\Bbb N$, and let $\widehat\sigma=\langle m_k:k\in\Bbb N\rangle$; the map $\sigma\mapsto\widehat\sigma$ is injective, and $\widehat\sigma$ is a strictly increasing sequence. Now let

$$x_\sigma=\sum_{k\in\Bbb N}\frac1{3^{m_k}}\;,$$

and show that the map $\sigma\mapsto x_\sigma$ is injective. This isn’t hard if you remember that

$$\sum_{k>m}\frac1{3^k}=\frac{\frac1{3^{m+1}}}{1-\frac13}=\frac1{2\cdot3^m}<\frac1{3^m}\;.$$

Once you have $\Bbb R\approx\Bbb N^{\Bbb N}$, show that $\Bbb R^{\Bbb N}\approx\left(\Bbb N^{\Bbb N}\right)^{\Bbb N}\approx\Bbb N^{\Bbb N\times\Bbb N}$, and use show that if $B\approx C$, then $A^B\approx A^C$; this will give you the second part.

For the last part, one injection can come from the observation that constant functions are continuous. The other is most easily derived from the fact that if $f,g:\Bbb R\to\Bbb R$ are continuous, and $f\upharpoonright\Bbb Q=g\upharpoonright\Bbb Q$, then $f=g$.

Answer 2

Take a real and write it as $n.d_1d_2\dots$ (decimal expansion -- endless 9's not allowed -- like $0.999\dots = 1$ -- so the expansion is unique). Map this to $(n,d_1,d_2,\dots)$. This gives an injection from $\mathbb{R}$ to $\mathbb{N}^{\mathbb{N}}$.

To get an injection the other way, consider $(n_1,n_2,\dots)$. Express $n_i$ as a binary string (no leading zeros) call this ${\bf b}_i$ (if $n_i$ then leave ${\bf b}_i$ empty). Then write $0.{\bf b}_1 \,2\, {\bf b}_2 \,2\, {\bf b}_3 \dots$ [so for example: $(3,8,0,5,\dots)$ goes to $0.1121000221012\dots$ (decimal expansion). By uniqueness of the decimal expansion you've got an injection into $\mathbb{R}$.

By Cantor-Shroder-Bernstein you've got $\mathbb{N}^{\mathbb{N}} \approx \mathbb{R}$.

The second line follows from: $\mathbb{R}^{\mathbb{N}} \approx (\mathbb{N}^{\mathbb{N}})^{\mathbb{N}} \approx \mathbb{N}^{\mathbb{N} \times \mathbb{N}} \approx \mathbb{N}^\mathbb{N} \approx \mathbb{R}$ since $\mathbb{N} \times \mathbb{N} \approx \mathbb{N}$. Also, $\mathbb{Q} \approx \mathbb{N}$ so that one follows as well.

The last one follows from the fact that continuous functions are determined by their values on a dense set (for example $\mathbb{Q}$) so it's cardinality is the same as $\mathbb{R}^\mathbb{Q}$.