Proposition: For a set $X$ and its power set $P(X)$, any function $f\colon P(X)\to X$ has at least two sets $A\neq B\subseteq X$ such that $f(A)=f(B)$.

I can see how this would be true if $X$ is a finite set, since $|P(X)|\gt |X|$, so by the pidgeonhole principle, at least two of the elements in $P(X)$ would have to map to the same element.

Does this proposition still hold for $X$ an infinite set? And if so, how does this show that the set of all singleton sets cannot exist?

  • $\begingroup$ Is this homework? $\endgroup$ – Aryabhata Sep 1 '10 at 20:40

If you had a function $f\colon P(X)\to X$ such that $f(A)=f(B)\Rightarrow A=B$, then $f$ would be one-to-one, which would imply $|P(X)|\leq |X|$; since $|X|\lt |P(X)|$ holds by Cantor's Theorem, that would give you $|P(X)|\lt|P(X)|$, which is impossible. This argument does not use finiteness of $X$, so it holds for $X$ infinite as well.

Suppose that the collection of all singletons is a set $X$. Define a map $f\colon P(X)\to X$ by $f(A) = \{A\}$; this is well defined, since $\{A\}$ is a singleton. If $A\neq B$, then $\{A\}\neq\{B\}$, so $f$ would be one-to-one. Since, by the proposition, this is impossible, we conclude that our assumption that the collection of all singletons is a set must be false. Thus, there is no "set of all singletons."

  • 1
    $\begingroup$ Thank you, a very clear explanation. Much appreciated. $\endgroup$ – yunone Sep 1 '10 at 20:51
  • $\begingroup$ Don't forget to accept an answer if you are satisfied; doesn't have to be mine, but if you are essentially "done" here, you might want to pick one and accept it. $\endgroup$ – Arturo Magidin Sep 2 '10 at 18:41

If $x$ is a set containing all singletons, $\cup x$ is a set containing all sets, which leads to Russel's paradox. Thus, in $ZF$ there is no such $x$.

  • 2
    $\begingroup$ This, in my opinion, is the "correct" answer to the title question... no fancy functions or regularity needed. Just the union axiom and separation :) $\endgroup$ – Dylan Wilson Sep 2 '10 at 5:00
  • 4
    $\begingroup$ There are a lot of ways; but the poser specifically asked how the result quoted (no injective functions $P(X)\to X$) could be used to establish that there is no set of all singletons, so presumably a direct application of the result is what was sought here. $\endgroup$ – Arturo Magidin Sep 2 '10 at 18:35
  • $\begingroup$ You would have to add a proof of $\forall x \exists y (\cup x = y)$ $\endgroup$ – PyRulez Jan 6 '13 at 14:59
  • 1
    $\begingroup$ This is the union axiom. Of course I work in ZF (or some tiny fragment). $\endgroup$ – Martin Brandenburg Jan 26 '13 at 22:09

If you accept that the collection of all sets (denoted by $V$ usually) is not a set (but in fact a proper class) then if you look at the function $f(x) = \{ x \}$ it is 1-1 from $V$ into the sets of all singletons, thus resulting that $V$ would be a set, in contradiction to the fact that it is in fact a proper class.

But of course you'd have to accept that $V$ is a proper class as well, this is simpler and follows by the argument given in Arturo's answer (that the power-set of $V$ would be of the same cardinality).


Your presupposition is incorrect; there are a number of set theories (some of them provably equiconsistent with ZF) in which the set of all singletons exists; see Limiting set theory using symmetry, or Forster’s Oxford Logic Guide on the subject. (Disclaimer: Forster discusses my work in the book, so I’m hardly unbiased, but it is the standard work.)

  • $\begingroup$ So if they are equiconsistent, does that mean the set of all singletons does indeed exist in ZF? I was only referring to ZF in my question. $\endgroup$ – yunone Mar 9 '11 at 18:20
  • $\begingroup$ No, “equiconsistent” just means that if ZF is consistent, so are the theories in question, e.g., Church's Set Theory with a Universal Set. The most accessible reference is probably Forster’s article on it, dpmms.cam.ac.uk/~tf/church2001.pdf $\endgroup$ – Flash Sheridan Mar 15 '11 at 3:53

The question in the title is a consequence of the axiom of regularity. In fact If there was such a set $X$, then $\{X\}\in X$. But obviously we always have $X\in\{X\}$. Hence, we would be able to construct an infinite downward chain of sets which contradicts the axiom of regularity.

  • $\begingroup$ Note however that the question in the statement also holds in ZF-{Regularity}+{Aczel's Anti-Foundation Axiom}, so Regularity is not needed. $\endgroup$ – Arturo Magidin Sep 2 '10 at 4:46
  • $\begingroup$ You need to put two backslashes before a curly bracket rather than just one; otherwise, the curly bracket does not show up. $\endgroup$ – Arturo Magidin Sep 2 '10 at 4:53
  • $\begingroup$ @Arturo Magidin: This is really crazy :D I am certain I was able to TeX curly braises a couple of days ago...or wasn't I?? Thanks! $\endgroup$ – AD. Sep 2 '10 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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