3
$\begingroup$

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?

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

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • 5
    $\begingroup$ The last statement requires, of course, the axiom of choice. Not that I refuse it, but… $\endgroup$ – egreg Sep 4 '15 at 11:06
  • $\begingroup$ @egreg: Is the axiom of choice really necessary here? I thought you don't need it because you only choose from singletons. $\endgroup$ – Dominik Sep 4 '15 at 11:10
  • 3
    $\begingroup$ @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. $\endgroup$ – Cameron Buie Sep 4 '15 at 11:15
  • $\begingroup$ @CameronBuie: You are right, I somehow mixed up both directions in my head. For future reference see this thread. $\endgroup$ – Dominik Sep 4 '15 at 11:25
  • $\begingroup$ 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. $\endgroup$ – asdf Apr 25 '18 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.