4
$\begingroup$

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

  • 0
    Which direction is easy?2012-05-02
  • 0
    @David: the one that isn't in the title :)2012-05-02
  • 0
    @t.b. Aha! :)${}$2012-05-02
  • 0
    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}$?2012-05-02
  • 0
    Cameron: please do include the actual question in the body of your posts, not only in the title because many people tend to read only the body attentively.2012-05-02
  • 0
    Apologies. I will edit that now.2012-05-02
  • 0
    Perhaps I'm missing something: could we not argue that $X$ must be infinite and obtain a surjection from this?2012-05-02
  • 1
    @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.2012-05-02

1 Answers 1

9

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 of indices such that for any $k,$ $\bigcap_{i contrary to our assumption. From condition 3., it follows that there is a sequence $m_0 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.

  • 0
    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?2012-05-02
  • 4
    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.2012-05-02
  • 2
    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.2012-05-02
  • 0
    @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.2015-06-25
  • 0
    @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?2015-06-25
  • 0
    @Sushil: It's tempting to say that the $\mathcal A_n$ are pairwise distinct by definition, but this is not so! Rather, they are pairwise *disjoint*, which is not quite enough.2015-06-25
  • 0
    @CameronBuie we define f: N to P(X1) as f(n)=An2015-06-25
  • 0
    @Sushil: Yes, and...?2015-06-25
  • 0
    @CameronBuie sorry I think I didn't get anything. Why you have written "t's tempting to say that the An are pairwise distinct by definition, but this is not so! Rather, they are pairwise disjoint, which is not quite enough" and what are you asking me in the end "and...? –"2015-06-26
  • 0
    @Sushil: The first part ("It's tempting...") was to give you a hint about a key component of the proof. The second part ("and...?") was because I couldn't tell how much about my comments you actually understood.2015-06-26
  • 0
    @CameronBuie I think I didn't get key component. Aren't An pairwise distinct.(Although you have given answer I din't get why). Can you please help?2015-06-26
  • 0
    @Sushil: They *are* pairwise distinct, but the definition alone isn't enough for us to conclude that. All we can conclude from the definition is that $$\mathcal A_m\cap\mathcal A_n=emptyset$$ when $m\ne n.$ However, this *isn't* enough to conclude that $$\mathcal A_m\ne\mathcal A_n$$ whenever $m\ne n.$ Do you see why?2015-06-26
  • 0
    @CameronBuie but if x in Am then it has m elements so it can't be equal to any set containing n elements where n not equal to m. So Aren't Am and An pairwise distinct2015-06-26
  • 0
    @CameronBuie and if Am=An hence these are disjoint. Hence not disjoint implies not equal. Isn't it true? What is problem here?2015-06-26