I have to prove that given any set, there's no function f : A -> P(A), where P(A) is the power set of A, that is onto.
well, if the set A has n elements, then P(A) will have 2^n elements. therefore, |P(A)| will always be larger than A, and therefore the function f:A -> P(A) cannot be injective and hence cannot be onto. that's the gist of it. write that more formally and it should be fine
EDIT: wait, am i mixing up "onto" with "bijective"?
Ah, Cantor's Theorem.
First note that $\displaystyle A$ and $\displaystyle P(A)$ have different cardinalities.
Proof (by contradiction):
Suppose $\displaystyle f : A \rightarrow P(A)$ is onto.
We want to find $\displaystyle B \in P(A)$ that is not in the image of $\displaystyle A$.
Define $\displaystyle B = {a \in A \ni a \notin f(a)}$
Since $\displaystyle f$ is onto, $\displaystyle \exists a_0 \in A \ni f(a_0) = B$.
Case 1: If $\displaystyle a_0 \in B$, then by definition, $\displaystyle a_0 \in f(a_0) = B$
This is a contradiction.
Case 2: If $\displaystyle a_0 \notin B$ then $\displaystyle a_0 \notin B = f(a_0)$ and so by definition of $\displaystyle B$, $\displaystyle a_0 \in B$
This is a contradiction.
Thus, we've proved that f is not onto. $\displaystyle \square$