Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Is this homework? –  Aryabhata Sep 1 '10 at 20:40
add comment

5 Answers 5

up vote 20 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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! –  user1119 Nov 14 '10 at 10:05
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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