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 and have different cardinalities.
Proof (by contradiction):
Suppose is onto.
We want to find that is not in the image of .
Define
Since is onto, .
Case 1: If , then by definition,
This is a contradiction.
Case 2: If then and so by definition of ,
This is a contradiction.
Thus, we've proved that f is not onto.