Non-existence of a Surjective Function from a Set to Its Subsets (Cantor's theorem) Show that: Let A be a set and let $P(A)$ be the set of all subsets of $A$. Then there is no surjection $f: A→P(A)$.
Here is what I thought:
if $A=\{a,b\}$ then it has only two elements where $P(A)=\{∅,\{a\},\{b\},\{a,b\}\}$ has 4 elements. Therefore $f:A→P(A)$ cannot be surjective. But I have some problems:
1) How is it possible that any $f$ function to take $\{a\}$ from set $A$ to $\{a,b\}$? Maybe because I am thinking mainly about functions with real values like $f(x)=2x$, I find it a little bit strange that a function to take an element of a set to another set which has more elements. Is it possible?
edit: Now I thought that if $f(x)$ is $\sqrt{x}$, then $f(4)=±2$ which means it took an element from a set to a set which has 2 elements. But still I find it kind of strange to denote $f(\{a\})=\{a,b,c,...\}$
2) How can I construct a explicit proof for this question?
Regards

Look up Cantor's Theorem. There are several versions of this theorem. The basic version is to the effect that there is no bijection between a set $A$ and its power set $P(A)$. One of the proofs goes by showing there is no surjection from $A$ to $P(A)$. What one does is to assume there is, so that for each $a$ there is a subset $f(a)$ in the power set. Then one defines a set $B$ by saying that $x$ is in $B$ if and only if $x$ is NOT in the set $f(x)$. Now you ask: Is $x$ in $B$? If it is, it isn't, and if it isn't then it is... either way you get a contradiction!
