Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$?

share|improve this question
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

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
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
@AndresCaicedo can you please tell why ω injects either into X1=P(X) or at worst into P(X1) even if ω does not inject into X. –  Sushil Jun 25 at 11:33
@Sushil: Given an infinite set $X$ and any $n\in\omega,$ let $\mathcal A_n$ be the set of all $Y\subseteq X$ such that $Y$ has $n$ elements. For example, $\mathcal A_0=\{\emptyset\},$ and $$\mathcal A_1=\bigl\{\{x\}:x\in X\bigr\}.$$ Since each $\mathcal A_n\in\mathcal P(X_1)$ and they are readily distinct, what can we conclude? –  Cameron Buie Jun 25 at 12:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.