17
$\begingroup$

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?

  • 0
    Is this homework?2010-09-01

5 Answers 5

0

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.

  • 0
    Note however that the question in the statement also holds in ZF-{Regularity}+{Aczel's Anti-Foundation Axiom}, so Regularity is not needed.2010-09-02
  • 0
    You need to put two backslashes before a curly bracket rather than just one; otherwise, the curly bracket does not show up.2010-09-02
  • 0
    @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!2010-09-02
42

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$.

  • 1
    This, in my opinion, is the "correct" answer to the title question... no fancy functions or regularity needed. Just the union axiom and separation :)2010-09-02
  • 4
    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.2010-09-02
  • 0
    You would have to add a proof of $\forall x \exists y (\cup x = y)$2013-01-06
  • 1
    This is the union axiom. Of course I work in ZF (or some tiny fragment).2013-01-26
34

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
    Thank you, a very clear explanation. Much appreciated.2010-09-01
  • 0
    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.2010-09-02
5

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).

3

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.)

  • 0
    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.2011-03-09
  • 0
    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, http://www.dpmms.cam.ac.uk/~tf/church2001.pdf2011-03-15