Why does the set of all singleton sets not exist?

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?

• Is this homework? – 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."

• Thank you, a very clear explanation. Much appreciated. – yunone Sep 1 '10 at 20:51
• 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. – 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$.

• This, in my opinion, is the "correct" answer to the title question... no fancy functions or regularity needed. Just the union axiom and separation :) – Dylan Wilson Sep 2 '10 at 5:00
• 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. – Arturo Magidin Sep 2 '10 at 18:35
• You would have to add a proof of $\forall x \exists y (\cup x = y)$ – PyRulez Jan 6 '13 at 14:59
• This is the union axiom. Of course I work in ZF (or some tiny fragment). – 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.)

• 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. – yunone Mar 9 '11 at 18:20
• 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 – 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.

• Note however that the question in the statement also holds in ZF-{Regularity}+{Aczel's Anti-Foundation Axiom}, so Regularity is not needed. – Arturo Magidin Sep 2 '10 at 4:46
• You need to put two backslashes before a curly bracket rather than just one; otherwise, the curly bracket does not show up. – Arturo Magidin Sep 2 '10 at 4:53
• @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! – AD. Sep 2 '10 at 5:01