Given an injection $\mathbb{N}\to\mathcal{P}(X)$, how can we construct a surjection $X\to\mathbb{N}$?
This result is somewhat tricky. Here is a proof, taken from a book I'm working on. I'll use $\omega$ for ${\mathbb N}$. We show that if $\omega$ injects in ${\mathcal P}(X)$, then $\omega$ is the surjective image of $X$. (Note the nice corollary that then we have in fact that ${\mathcal P}(\omega)$ injects into ${\mathcal P}(X)$.)
The result is due to Kuratowski. I follow the proof as presented in a footnote in pages 94, 95 of Alfred Tarski, "Sur les ensembles finis", Fundamenta Mathematicae 6 (1924), 45–95.
Let $S_0=\{A_n:n\in\omega\}$ be a countable collection of distinct subsets of $X$. It suffices to show that there is a countable infinite collection of non-empty pairwise disjoint subsets of $\bigcup_n A_n.$ This is certainly the case if there is an infinite descending chain $B_0\supsetneq B_1\supsetneq \dots$ where each $B_i$ is the intersection of finitely many sets $A_n$. Suppose that this is not the case. We claim that there must exist a set $F(S_0)$ such that:
- $F(S_0)$ is the intersection of finitely many sets $A_n,$
- $F(S_0)\ne\emptyset,$ and
- For all $n,$ either $F(S_0)\subseteq A_n$ or $F(S_0)\cap A_n=\emptyset.$
In effect, if no such set $F(S_0)$ exists, an easy induction produces a sequence $n_0<n_1<\dots$ of indices such that for any $k,$ $\bigcap_{i<k}A_{n_i}\supsetneq\bigcap_{i\le k}A_{n_i},$ contrary to our assumption. From condition 3., it follows that there is a sequence $m_0<m_1<\dots$ such that either $F(S_0)\subsetneq A_{m_i}$ for all $i$, or $F(S_0)\cap A_{m_i}=\emptyset$ for all $i$. Let $S_1=\{A_i':i<\omega\},$ where $A_i'=A_{m_i}\setminus F(S_0)$ for each $i.$ Then $S_1$ is a countable collection of nonempty sets, all of them disjoint from $F(S_0).$ We can then iterate the procedure above, and either find a descending sequence $B_0\supsetneq B_1\supsetneq\dots$ of subsets of $\bigcup S_1,$ or a set $F(S_1)$ satisfying conditions 1-3 with respect to the sets $A_i'.$ Continue this way inductively. Either at some stage some such decreasing sequence of sets $B_i$ is obtained, and we are done, or else, we have built a sequence $\{F(S_i):i<\omega\}$ of nonempty pairwise disjoint subsets of $\bigcup_nA_n,$ and again we are done.
For clarity, let me emphasize that the result is of course immediate if we invoke the axiom of choice, and that what makes it interesting is that we can avoid its use. Kuratowski's result is an instance of a curious phenomenon: Quite a few results that hold in the presence of choice have "choiceless counterparts", typically a few power sets away. In this instance: Under choice, a set $X$ is infinite iff $\omega$ injects into $X$. Without choice, it is possible that $X$ is infinite and yet $\omega$ does not inject into $X$. However, in this case $\omega$ injects either into $X_1={\mathcal P}(X)$ or at worst into ${\mathcal P}(X_1)$, and we are in the setting of this problem.