Proving $|{\bf R}^{\bf R}|=|2^{\bf R}|$ using the Schroeder-Bernstein Theorem
Let $A$ be the set of all functions from ${\bf R}$ to ${\bf R}$ and $B$ the power set of ${\bf R}$. Then $|A|=|B|$.
This is a well-known result in set theory. A quick search on Google returns answers in various places explicitly using cardinal arithmetic.
Question: Can one prove the above result using the Schroeder-Bernstein Theorem?
Remark.
To use Schroeder-Bersnstein, one needs two injections. One easy direction is from $B$ to $A$: any subset of ${\bf R}$ can be identified as a function $f:{\bf R}\to\{0,1\}$. Such identification gives an injection from $B$ to $A$.
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
To apply the Schröder-Bernstein theorem, we need injections in two directions. Given that the Schröder-Bernstein theorem doesn't require the axiom of choice (AC), there's a value in avoiding anything that requires AC (such as the theorem that existence of a surjection from $A$ to $B$ implies the existence of an injection from $B$ to $A$).
I'll construct the two injections explicitly; that way I can be sure to not accidentally use the AC. Note I'll use $\mathcal P(\mathbb R)$ to denote the power set of $\mathbb R$.
An injection $\mathcal P(\mathbb R)\to\mathbb R^{\mathbb R}$ can be given as $$f(A) = x\mapsto\begin{cases} 1 & x\in A\\ 0 & x\notin A \end{cases}$$
For an injection $\mathbb R^{\mathbb R}\to \mathcal P(\mathbb R)$, we start with a bijection $\phi:\mathbb R\to (0,1)$ given by $$\phi(x) = \exp(-\exp (x))$$
Then we define an injection $\iota:(0,1)\to \mathcal P(\mathbb N)$ by writing the number as dyadic fraction (choosing the period-0 representation in case of ambiguity), and then defining $$\iota(x) = \{n\in\mathbb N: \text{the $n$-th digit is 1}\}$$
With those two ingredients, we now can build an injection $\alpha: \mathbb R^{\mathbb R}\to\mathcal P(\mathbb N\times\mathbb R)$ given by $$\alpha(f) = \{(n,x)\in\mathbb N\times\mathbb R: n\in\iota\circ\phi\circ f\}$$
Next, we define the surjection $\sigma:\mathbb R\to\mathbb N\times\mathbb R$ by $$\sigma(x) = \begin{cases} \Big(\Big|\lfloor x\rfloor\Big|,0\Big) & x\in\mathbb Z\\ \Big(\Big|\lfloor x\rfloor\Big|,\ln(-\ln(x-\lfloor x\rfloor))\Big) & \text{otherwise} \end{cases}$$ Finally we define the function $g:\mathbb R^{\mathbb R}\to \mathcal P(\mathbb R)$ as $$g(f) =\{x\in \mathbb R:\sigma(x)\in\alpha(f)\}$$
What remains is to prove that $g$ is indeed an injection. For this, assume $g(f_1) = g(f_2)$. Since $\sigma$ is surjective, this implies $\alpha(f_1) = \alpha(f_2)$, as otherwise there would be some $x$ such that $\sigma(x)$ is in exactly one of $\alpha(f_1)$ and $\alpha(f_2)$. But $\alpha$ in injective by construction, thus $f_1=f_2$.
Since we thus have, by explicit construction, both an injection $\mathcal P(\mathbb R)\to\mathbb R^{\mathbb R}$ and an injection $\mathbb R^{\mathbb R}\to \mathcal P(\mathbb R)$, we now can use Schröder-Bernstein to conclude that there exists a bijection between those sets.
0 comment threads
By definition $\mathbb R^\mathbb R \subset \mathbf 2^{\mathbb R\times\mathbb R}$. So all we need is a surjection $\mathbb R \twoheadrightarrow \mathbb R \times \mathbb R$ of which there are plenty such as space filling curves. If you have a bijection between $\mathbf 2^\mathbb N$ and $\mathbb R$, then a lot of this stuff is easier to do in terms of $\mathbf 2^\mathbb N$. For example, $\mathbf 2^\mathbb N \times \mathbf 2^\mathbb N \cong \mathbf 2^{\mathbb N + \mathbb N} \cong \mathbf 2^\mathbb N$ with the last bijection via the straightforward one showing $\mathbb N \cong \mathbb N + \mathbb N$ (where $+$ represents the disjoint union/coproduct).
That said, you should be able to fairly directly extract a bijection from a proof using cardinal arithmetic. Of course, there's no real reason to apply Schröder-Bernstein at that point.
0 comment threads
0 comment threads