What is the cardianlity of: $$ A = \left\{ f:\mathbb{N}\to\mathbb{R} : \text{f is injective} \right\} $$

Trying to prove it using Cantor–Bernstein–Schroeder theorem, I have the obvious side: $$A \subseteq f:\mathbb{N}\to\mathbb{R}$$

Hence, $$\left|A\right| \le \aleph$$

I need to find an injection from a set with cardinality of $\aleph$ to $A$, but couldn't think of a proper one. It's tricky.

Any idea?



HINT: Prove that $\{f\in A\mid\operatorname{range}(f)\subseteq\Bbb N\}$ has size $\aleph$.

  • 1
    $\begingroup$ Or just ask it the other way round (injections N -> R). $\endgroup$ – Martin Brandenburg Sep 8 '14 at 17:19
  • $\begingroup$ Right. I'll claim it was a typo! $\endgroup$ – Elimination Sep 8 '14 at 17:19
  • 1
    $\begingroup$ @Elimination: Alright, a different hint, then. $\endgroup$ – Asaf Karagila Sep 8 '14 at 17:26
  • $\begingroup$ Can I get an hint for the hint? :) $\endgroup$ – Elimination Sep 8 '14 at 17:37
  • $\begingroup$ @Elimination: Certainly. For every infinite set $D\subseteq\Bbb N$ consider the function which fixes pointwise $\Bbb N\setminus D$, partitions $D$ into pairs and switches all those pairs. $\endgroup$ – Asaf Karagila Sep 8 '14 at 17:40

For each $a\in(0,1)$ we'll define a function $f(n) = a+n$. $f$ is clearly in $\mathbb{N}\to\mathbb{R}$ and since it's monotone it is also injective. Moreover, if $a_1\ne a_2$ then $f_1(n) \ne f_2(n)$.

Hence, the set of all functions described is subset of $A$ and it's cardinality is $\left|\left(0,1\right)\right| = \aleph$

  • $\begingroup$ Yeah, that's also works. (Simpler than my hint; although proving that the set of injections from $\Bbb N$ to itself has size $\aleph$ gives you more information.) $\endgroup$ – Asaf Karagila Sep 8 '14 at 17:30

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.