Question
What is the cardinality of the set of injective functions from $\mathbb{N}$ to $\mathcal P \mathbb{N}$?
Attempt
If we denote the desired set as $I$, then we can find an upper bound by dropping the requirement for injectivity as follows:
$$|I| \leq |\mathcal P \mathbb{N}|^{|\mathbb{N}|} = (2^{\aleph _0})^{\aleph _0} = 2^{\aleph _0}$$
However, I am struggling to find a suitable lower bound. It is quite easy to show that the set must be greater than or equal to $\aleph _0$ by constructing a function that maps natural numbers to sets containing only themselves. Although, I need to construct an injection from $\mathcal P \mathbb{N}$ into $I$ in order to show that $2^{\aleph _0}$ is also a lower bound.
After this point, we can simply invoke Cantor-Schrdoder-Bernstein Theorem, to conclude that $|I| = 2 ^{\aleph _0}$.
I have read that the following is an injective map that provides the desired lower bound:
$$ g(X) = n \mapsto \begin{cases}
\text{ {$n+1$}} & \text{if $n \in X$} \\
\text{ {$0,\space n+1$}} & \text{if $n \not \in X$}
\end{cases}$$
However, I am hoping for a more intuitive solution that I could construct myself (if the above solution can be explained in an intuitive way, then I am also happy for that to be provided as a valid solution to the question). This was a former exam problem, so I was hoping to be able to understand the solution in a way that will allow me to construct functions of my own in similar examples.
I would be grateful for any assistance here.
Best Answer
First, construct an injection $f:\mathbb N\to\mathcal P(\mathcal N)$. Let $a_n=f(n)$ and let $A=\{a_n:n\in\mathbb N\}$.
For each $x\in\mathcal P(\mathbb N)$ we shall define an injection $h_x:\mathbb N\to\mathcal P(\mathbb N)$ such that $h_x(1)=x$, thus showing that the set of injections from $\mathbb N$ to $\mathcal P(\mathbb N)$ has cardinality at least as great as the cardinality of $\mathcal P(\mathbb N)$.
If $x=a_1$ let $h_x=f$.
If $x\notin A$ let $h_x(1)=x$ and $h_x(n)=a_n$ for $n\ne1$.
If $x=a_k\in A\setminus\{a_1\}$ let $h_x(1)=x$, $h_x(k)=a_1$, and $h_x(n)=a_n$ for $n\notin\{1,k\}$.