# 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

## 5 Answers

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

1
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
Very nice! Thanks! – George S. Nov 14 '10 at 10:05
You would have to add a proof of $\forall x \exists y (\cup x = y)$ – PyRulez Jan 6 at 14:59
This is the union axiom. Of course I work in ZF (or some tiny fragment). – Martin Brandenburg Jan 26 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
– 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 39, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9487513303756714, "perplexity_flag": "head"}