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?

  • 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

1

Note that there is no such surjection, the set $D$ is a set which is not in the range of $f$. That is its purpose. It is possible that $D=A$, it is possible that it is empty as well.

For example let $A=\mathbb N$ and consider the map $f(n)=\{k\mid k>n\}$. Clearly $n\notin f(n)$ for all $n$.

  • 0
    @Asaf: Yeah righ$t$ , $t$ha$t$'s true.2012-10-04
1

Well, in ZFC such a surjection cannot exist, because $|P(A)|>|A|$, and if $|A|\ge\aleph_0$ (that is, $A$ is infinite), then $|P(A)\setminus A| = |P(A)|$ still $>|A|$. (however you mean $P(A)\setminus A$ - probably via the canonical embedding $a\mapsto\{a\}$). Whilst, if there is a surjection $A\to B$, then $|A|\ge|B|$.

On the other hand, there are set theories, e.g. Quine's New Foundation, where Russell's paradox is resolved not by the bigness of the sets, and there there exists the set of everything, say $\Omega$, and there $P(\Omega)$ is contained in $\Omega$. Well, $A=\Omega$ is still not a good choice because $P(A)\setminus A=\emptyset$, but it may make some sense what you ask...