# Set Theory and surjective function exercise

Let $E$ a set and $f:E\rightarrow P(E)$ any function. If $$A=\{a\in E:a\notin f(a)\}$$ Prove that $A$ has no preimage under $f$.

-
Try the proof by contradiction but I do not quite understand what the set A – Roiner Segura Cubero Mar 17 '13 at 3:16
This gives a proof of Cantor's theorem: there exists no surjection $A\to P(A)$. – Pedro Tamaroff Mar 17 '13 at 3:29

Suppose $\exists a\in E$, $f(a)=A$. Then, is $a\in f(a)$?

If $a\in f(a)$, that means $a\notin A$, contradicts to $f\in f(a)=A$.

If $a\notin f(a)$, that means $a\in A$.

Thus, such $a$ does not exists i.e. $f(a)$ has no preimage.

-

Assume there is $x \in E$ such that $f(x) = A$. Then either $x \in f(x) = A$, but then $x \notin A$, or $x \notin f(x) = A$, but then $x \in A$. So you get a contradiction.

-