# On a Surjection

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?

-
Anything’s possible if you have a surjection $f:A\to\wp(A)\setminus A$: a false statement implies every statement! – Brian M. Scott Sep 28 '12 at 8:32
@Brian: The statement isn't false; it just severely restricts the possible sets $A$. – joriki Sep 28 '12 at 8:39
@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). – Asaf Karagila Sep 28 '12 at 8:41
@Asaf, Brian: Sorry, I somehow missed the "infinite" part :-) – joriki Sep 28 '12 at 8:43
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)$. – Andrés Caicedo Sep 28 '12 at 15:49

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

-
@Souvik: First you need to better define what do you mean $\mathcal P(A)\setminus A$. – Asaf Karagila Sep 28 '12 at 9:11
The relative complement of B in A (also called the set-theoretic difference of A and B), denoted by A\B (or A − B), is the set of all elements which are members of A but not members of B,that's what I wanted to mean.I actually asked the question to be able to show by contradiction that such a surjection in fact does not exist,for that I needed that A\D be never empty.It would be really helpful if you plese give some account of the proof that no surjection from A to P(A)\A exists. – Souvik Dey Sep 28 '12 at 9:26
@Souvik: It would be helpful if you explain what you mean by writing $\mathcal P(A)\setminus A$ mean. I know what is set difference, and I know that $A\neq\{A\}$ in general. I also know that $A$ doesn't have to be a subset of $\mathcal P(A)$ in general. So what do you mean when you write that expression? – Asaf Karagila Sep 28 '12 at 9:44
The expression is still properly defined. For example, $\emptyset$ might be an element of $A$ and hence is to be removd from $\mathcal P(A)$. For typical sets (e.g. with its elements considerd as urelements), $\mathcal P(A)$ and $A$ are of course disjoint. Or consider ordinals: Their elements are also subsets hence it might make sense to talk of $\mathcal P(A)\setminus A$. – Hagen von Eitzen Sep 28 '12 at 10:48
@Hagen: Yes. It is well defined and whatnot. But often people write $A$ and they mean $\{A\}$. Yes, it is possible for $A\subseteq\mathcal P(A)$. But it is also possible that $A\cap\mathcal P(A)=\varnothing$. Since this is quite case dependent it seems to me that it is likely the OP means something else. – Asaf Karagila Sep 28 '12 at 12:42

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

-