Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Proving $|{\bf R}^{\bf R}|=|2^{\bf R}|$ using the Schroeder-Bernstein Theorem

+2
−0

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

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

2 answers

+2
−0

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.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+1
−0

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.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »