# 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

-
Saying that $f(x) = \sqrt{x}$ in your edit is not the same as saying that $f(4) = \pm 2$. A function always produces one output for any accepted input. – user21820 Jan 19 '15 at 16:12

Cantor's theorem states:

Suppose that $A$ is a set and $f\colon A\to\mathcal P(A)$ is any function, then $f$ is not surjective.

The proof is quite simple, and constructive!

Proof. Suppose that $f\colon A\to\mathcal P(A)$ is a function, we define $D=\{a\in A\mid a\notin f(a)\}$. This is a good definition, since $f(a)$ is a subset of $A$, and $a$ is an element of $A$, we can ask whether or not $a\in f(a)$. So $D$ is the set of those elements of $A$ which do not have this property.

Of course that $D\in\mathcal P(A)$ since it is clearly a subset of $A$. We will show that $f(a)\neq D$ for all $a\in A$.

1. If $a\in D$, then $a\notin f(a)$. So $f(a)\neq D$, since $a\in D$ and $a\notin f(a)$.
2. If $a\notin D$ then $a\in f(a)$. By the same argument, again $f(a)\neq D$.

Either way, $D\neq f(a)$ for all $a\in A$. Therefore $f$ is not surjective. $\square$

Note that for different functions we have different $D$'s. It is possible that $D=A$ (e.g. if $f(a)=\varnothing$ for all $a$), or it could be $\varnothing$ (e.g. if $f(a)=\{a\}$ for all $a$). However regardless to its value it will not be in the range of $f$.

-
How does f(a) is subset of A ,shouldn't it be subset of P(A) ? – Taylor Ted Jul 8 '15 at 7:12
I didnot understand the proof .Can you explain with example ? – Taylor Ted Jul 8 '15 at 7:33
Also does f(a) consists of elements of power set of A ? – Taylor Ted Jul 8 '15 at 7:35
Could you please explain your post with an example? This post, is in its current version, is really difficult for me to comprehend. Thank you! – Gaurang Tandon Dec 5 '15 at 5:58

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!

-