It is not so hard to see that there doesn't exist a surjective function from a set $A$ to $\mathcal{P}(A)$, the power set of $A$. Namely, let us suppose there does exist such a function $f:A\rightarrow\mathcal{P}(A)$. Then, consider the set $X=\{x\in A\mid x\not\in f(x)\}$. Since $f$ is surjective, there exists an $a\in A$ such that $f(a)=X$. This however instantly results in a contradiction.
Now, one would expect a proof of the statement
There doesn't exist an injective function from the power set of a set to the set itself
to be provable in a similar way. However, so far I have not been able to alter above proof to prove this statement, how would one do this?
Best Answer
The usual diagonal argument works fine "in reverse":
Suppose $g:\mathcal P(X)\to X$, and consider $$ A = \{ g(Y)\mid Y\subseteq X, g(Y)\notin Y \} $$ Let $x=g(A)$. If $x\notin A$, then setting $Y=A$ we see that $x\in A$, which is a contradiction. So $x\in A$.
On the other hand $x\in A$ implies that there is an $Y$ such that $g(Y)=x=g(A)$ and $x\notin Y$. Then $A$ and $Y$ are two different sets (one contains $x$, the other doesn't) that both map to $x$, so $g$ is not injective.