4
$\begingroup$

In an introductory course on axiomatic set theory, I am asked whether $\Bbb {R^R}$ is equinumerous to the set of all surjective functions in $\Bbb{R^R}$ (say $\mathcal S$). Because of the evocative nature of the question, I assume this to be true. However, I have not been able to prove it.

Using Schroeder-Bernstein, we would need to find an injection from $\Bbb{R^R}\rightarrow\mathcal S$, but I don't have the slightest idea how we could get this. In a similar question involving $\Bbb N$ instead of $\Bbb R$, this could be done (quite) easily since we could speak about sequences, but that won't help here.

$\endgroup$
2
  • $\begingroup$ Finding an injection from $\mathcal{S}$ to $\Bbb{R}^\Bbb{R}$ is easy - just consider the inclusion map. I guess that you means the reverse. $\endgroup$
    – Hanul Jeon
    Oct 20, 2015 at 10:37
  • $\begingroup$ Sorry, you are absolutely correct, I will edit it $\endgroup$
    – konewka
    Oct 20, 2015 at 10:38

2 Answers 2

7
$\begingroup$

For given function $f:\Bbb{R}\to\Bbb{R}$, define $$\phi_f (x) = \begin{cases} \tan (\pi x/2) & \text{if }-1<x<1 \\ f(\tan(\pi (x-2)/2)) & \text{if }1<x<3 \\ 0 & \text{otherwise}\end{cases}.$$ You can check that the map $f\mapsto \phi_f$ is one-to-one. Also, $\phi_f$ is a surjection to $\Bbb{R}$.

$\endgroup$
4
  • $\begingroup$ Can this also be expanded so that $\phi_f$ is a bijection? $\endgroup$
    – konewka
    Oct 20, 2015 at 11:26
  • $\begingroup$ @konewka Did you mean a function $\phi_f \in \Bbb{R}^\Bbb{R}$ or the function maps $f$ to $\phi_f$? $\endgroup$
    – Hanul Jeon
    Oct 20, 2015 at 11:29
  • $\begingroup$ The function $\phi_f$, so in my original question, replacing $\mathcal S$ by the set of bijective functions. Or would those two not be equinumerous? $\endgroup$
    – konewka
    Oct 20, 2015 at 11:30
  • $\begingroup$ @konewka You may construct it. The set of all bijection from the reals to itself is equinumerous to $\Bbb{R}^\Bbb{R}$, but I didn't get how to construct the bijection explicitly. $\endgroup$
    – Hanul Jeon
    Oct 20, 2015 at 12:14
3
$\begingroup$

It suffices to divide $\mathbb R$ into two sets $A$ and $B$ such that $|A|=|B|=|\mathbb R|$.

This means you have some bijection $\varphi$ from $A$ to $B$. I.e., you have pairs $a\in A$ and $\varphi(a)\in B$

Using these two subsets you can construct bijections $\mathbb R\to\mathbb R$ by choosing some pairs, which you swap, and letting other elements in place.

More formally, if $C\subseteq A$, then we can define $f\colon\mathbb R\to\mathbb R$ as $$ f(x)= \begin{cases} \varphi(x) & x\in C, \\ \varphi^{-1}(x) & x\in \varphi[C], \\ x & \text{otherwise}. \end{cases} $$

In this way we get a different bijection from $\mathbb R$ to $\mathbb R$ for every subsets of $A$. So there is at least as many bijections from $\mathbb R$ to $\mathbb R$ as the number of subsets of $A$, which is $2^{\mathfrak c}$.

If we denote by $\mathcal S$ the set of all surjections and $\mathcal B$ the set of all bijections (from $\mathbb R$ to $\mathbb R$), we have $$2^{\mathfrak c} \le |\mathcal B| \le |\mathcal S| \le |\mathbb R^{\mathbb R}|=\mathfrak c^{\mathfrak c}=2^{\mathfrak c}.$$


You can also have a look at this post on MO, which deals with bijections on arbitrary set: Cardinality of the permutations of an infinite set. In fact, Robin Chapman's answer posted there gives basically the same argument as I gave above. It should be mentioned that if we do the same argument for arbitrary set, we would use Axiom of Choice to get the decomposition $X=A\cup B$ such that $|X|=|A|=|B|$. Some details about role of AC here are give in Andreas Blass' answer to the same post.

There were also several posts about cardinality of the set of all bijections from $\mathbb N$ to $\mathbb N$. Some of the arguments given there can be used also for $\mathbb R$:

And you could find other similar questions.

Remark on use of Axiom of Choice. In connection with another question on this site, it might be also interesting whether we can do this in ZF. It's not difficult to see that we might replace $\mathbb R$ with $\mathbb R\setminus\{0\}$. (Since we can write down an explicit bijection between $\mathbb R$ and $\mathbb R\setminus\{0\}$.) If we choose $A=(0,\infty)$, $B=(-\infty,0)$ and $\varphi(x)=-x$, then the above construction gives an explicit bijection $f\colon \mathbb R\setminus\{0\} \to \mathbb R\setminus\{0\}$ for every $C\subseteq A$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.