1
$\begingroup$

As specified here, the cardinality of the set of bijective functions on $\mathbb{N}$ is precisely $2^{\aleph_0}$. I was wondering if one can prove a parallel result regarding the bijective function on $\mathbb{R}$ (or maybe even the injective functions from $\mathbb{R}\mapsto \mathbb{R}$).

I tried to think about an injective function from the set of all $\mathbb{R}\mapsto \mathbb{R}$ functions to the set of injective or bijective functions, but I quickly ran out of ideas. Are the two sets even from the same cardinality?

Note: I included the real-analysis tag because I was thinking that maybe for this specific question a relatively complex construction using real functions might be necessary.

$\endgroup$

2 Answers 2

3
$\begingroup$

For each $x>0$ pick $\epsilon_x\in\{-1,1\}$ and define $f(x)=\epsilon_{|x|}x$ for $x\ne0$ and $f(0)=0$. Then $f\circ f$ is the identity, so $f$ is a bijection. This way we get $|\mathscr{P}(\Bbb R)|$ bijections from $\Bbb R$ to $\Bbb R$. There are only $|\mathscr{P}(\Bbb R)|$ functions from $\Bbb R$ to $\Bbb R$, so that's the cardinality of the set of bijections.

$\endgroup$
2
  • 1
    $\begingroup$ This is wonderfully slick. $\endgroup$
    – Lubin
    Oct 19, 2018 at 18:08
  • $\begingroup$ Why there are $|\mathscr{P}(\Bbb R)|$ bijections $\Bbb R$ to $\Bbb R$ ? $\endgroup$
    – Algo
    Sep 10, 2021 at 21:00
1
$\begingroup$

Upper bound is cardinality of general function $R \to R$: $R^R=2^R$; lower bound is $2^R=R$ as well (by consider each slot $x>0$ as having $x, -x$ two choices and that $f(-x)=-f(x)$; easy to verify each combination of such choices is bijection).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .