# Given an injection $\mathbb{N}\to\mathcal{P}(X)$, how can we construct a surjection $X\to\mathbb{N}$?

I goofed on my earlier post, here Given a surjection $f:\mathbb{N}\to\mathcal{P}(X)$, how can one construct an injection $X\to\mathbb{N}$?

I am trying to show that there is an injection $\mathbb{N}\to\mathcal{P}(X)$ iff there is a surjection $X\to\mathbb{N}$. One direction is easy--if $f:X→\mathbb{N}$ is a surjection, then $g(n)=f^{−1}(n)$ is an injection $\mathbb{N}→\mathcal{P}(X)$. The kicker is, if I have an injection $f:\mathbb{N}→\mathcal{P}(X)$, how can I construct a surjection $X→\mathbb{N}$?

-
Which direction is easy? –  David Mitra May 2 '12 at 1:56
@David: the one that isn't in the title :) –  t.b. May 2 '12 at 1:56
@t.b. Aha! :)${}$ –  David Mitra May 2 '12 at 1:57
If $f:X\to\mathbb{N}$ is a surjection, then $g(n)=f^{-1}(n)$ is an injection $\mathbb{N}\to\mathcal{P}(X)$. The kicker is, if I have an injection $\mathbb{N}\to\mathcal{P}(X)$, how can I construct a surjection $X\to\mathbb{N}$? –  Cameron Buie May 2 '12 at 1:58
@DavidMitra: Yet another thing I forgot to specify. I am working in ZF. It is true that $X$ is necessarily infinite, since $\mathcal{P}(X)$ D-infinite, and so infinite. However, without choice, there needn't be any injection $\mathbb{N}\to X$ or any surjection $X\to\mathbb{N}$ just from this fact. –  Cameron Buie May 2 '12 at 2:30

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:

1. $F(S_0)$ is the intersection of finitely many sets $A_n,$
2. $F(S_0)\ne\emptyset,$ and
3. 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.

-
I hope it is not too intrusive, but you sparked my curiosity: what is that book you mention in the first paragraph going to be about? –  t.b. May 2 '12 at 2:22
Topics on set theory. Sort of an intermediate level text, something you could read after a first course. The current draft centers on three topics: A collection of results on choiceless mathematics; basic (=mostly pre-pcf) cardinal arithmetic; and partition calculus. But the thing keeps growing, so the final version may be rather different. –  Andres Caicedo May 2 '12 at 3:10
Thanks! Books that keep growing, I know exactly what you're talking about... Bon courage and hopefully not too much of Hofstadter's law on the way to the finished product. –  t.b. May 2 '12 at 3:24