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 $\displaystyle A$ and $\displaystyle P(A)$ have different cardinalities.

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$

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$

Thus, we've proved that f is not onto. $\displaystyle \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"?
$\displaystyle f : A \rightarrow B$ is onto if $\displaystyle \forall b \in B$ $\displaystyle \exists a \in A \ni f(a) = b$

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