# There exists no injective function from the power set of A to A

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?

• May be it is answered here – GAVD Sep 4 '15 at 10:45
• Indeed, tetori's answer gives the proof, although it still contains some notational errors. – konewka Sep 4 '15 at 10:52
• @konewka What errors? – Git Gud Sep 4 '15 at 10:55
• @GitGud Tetori talks about: "If $R\in R$, then ...", but this should be "If $r(R)\in R$", if I'm not mistaken – konewka Sep 4 '15 at 10:56
• @konewka Agreed. I suggest you point it out to him. – Git Gud Sep 4 '15 at 10:59

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.

Assume there is an injective function $g: \mathcal{P}(X) \to X$ and denote by $M := g(\mathcal{P}(X)) \subset X$ its image. Then this means there is a surjective function $g^{-1}: M \to \mathcal{P}(X)$, which can easily be extended to a surjective function $f: X \to \mathcal{P}(X)$. This is a contradiction to the already stated assertion.

More generally, this has proven: For two sets $A, B$ there exists a surjective function $f: A \to B$ iff there is an injective function $g:B \to A$.

• The last statement requires, of course, the axiom of choice. Not that I refuse it, but… – egreg Sep 4 '15 at 11:06
• @egreg: Is the axiom of choice really necessary here? I thought you don't need it because you only choose from singletons. – Dominik Sep 4 '15 at 11:10
• @Dominik: You don't need it to prove that there is a surjection $A\to B$ if there is an injection $B\to A$. You do need it for the converse. – Cameron Buie Sep 4 '15 at 11:15
• @CameronBuie: You are right, I somehow mixed up both directions in my head. For future reference see this thread. – Dominik Sep 4 '15 at 11:25
• Sorry, to bother you, but isn't it true that if you have injective map $A\rightarrow B$, then you can construct a surjective one $B\rightarrow A$ by looking at $A$'s image under the first one?However, if you start with a surjective map, then you need AC. – asdf Apr 25 '18 at 14:46