1
$\begingroup$

For any set $B$ let $\mathcal{P}(B)$ denote the set of all subsets of $B$.

Let $A$ be an infinite set and suppose there exists a surjection $f : A \mapsto \mathcal{P}(A)\setminus A$. Consider the set $D := \{a : a \in A\ \textrm{but}\ a \notin f(a)\}$. Is it ever possible that the set $A\setminus D$ is empty?

  • 2
    Anything’s possible if you have a surjection $f:A\to\wp(A)\setminus A$: a false statement implies **every** statement!2012-09-28
  • 0
    @Brian: The statement isn't false; it just severely restricts the possible sets $A$.2012-09-28
  • 0
    @joriki: Uhh, it is false. Cantor's theorem shows that if $f\colon A\to\mathcal P(A)$ then it is not surjective. Note that $\mathcal P(A)$ has the same size as $\mathcal P(A)\setminus A$ (even if you parse this as removing all singletons).2012-09-28
  • 0
    @Asaf, Brian: Sorry, I somehow missed the "infinite" part :-)2012-09-28
  • 1
    Even without choice, one can prove that if $A$ is infinite and $n\in\mathbb N$, then the union of $n$ disjoint copies of $A$ is strictly smaller than $\mathcal P(A)$.2012-09-28

2 Answers 2