3
$\begingroup$

If $A$ is denumerable, is the set of all injective functions $A\to A$ equipotent with $2^A$?

I have proved $\aleph_0^{\aleph_0} = 2^{\aleph_0}$.

  • 1
    [This question](http://math.stackexchange.com/questions/87902/problems-about-countability-related-to-function-spaces/) asks (among other things) the same thing for $A=\mathbb N$; replacing arbitrary infinite countable set by $\mathbb N$ of course does not change the cardinality.2012-05-12

1 Answers 1

9

Let $I$ be the set of such injective functions. Partition $\mathbb{N}$ into countably many disjoint countably infinite sets $N_0,N_1,\ldots$. Every element of $\prod_n N_n$ is an injective function. Clearly, $\prod_n\{0,1\}=2^\mathbb{N}\leq\prod_n N_n\leq I\leq\mathbb{N}^\mathbb{N}\leq 2^\mathbb{N}.$ Since the ordering is antisymmetric and transitive, $|I|=|2^\mathbb{N}|$.