1. ## Power Set

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.

2. Originally Posted by seerTneerGevoLI
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"?

3. Originally Posted by seerTneerGevoLI
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.
Ah, Cantor's Theorem.

First note that $A$ and $P(A)$ have different cardinalities.

Suppose $f : A \rightarrow P(A)$ is onto.
We want to find $B \in P(A)$ that is not in the image of $A$.

Define $B = {a \in A \ni a \notin f(a)}$
Since $f$ is onto, $\exists a_0 \in A \ni f(a_0) = B$.

Case 1: If $a_0 \in B$, then by definition, $a_0 \in f(a_0) = B$

Case 2: If $a_0 \notin B$ then $a_0 \notin B = f(a_0)$ and so by definition of $B$, $a_0 \in B$

Thus, we've proved that f is not onto. $\square$

4. Originally Posted by Jhevon
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"?
$f : A \rightarrow B$ is onto if $\forall b \in B$ $\exists a \in A \ni f(a) = b$

5. Originally Posted by AfterShock
$f : A \rightarrow B$ is onto if $\forall b \in B$ $\exists a \in A \ni f(a) = b$
yes, i remember now. it's all coming back to me. thanks