Every function f: A $\rightarrow$ P(A) is not surjective

Question

In this case the P(A) is the power set of A.

I want to prove this by contradiction, even though it's easier to say that the power set of A is a bigger infinity, I am not allowed to assume that.

So I want to proceed by contradiction.

This is a proof by contradiction, let us assume that every function is f: A $\rightarrow$ P(A) is surjective, we shall show that this leads to a contradiction. Consider the set S {x $\in$ A : x $\notin$ f(x)}

I am not sure where to go from here any advice?

Answer 1

Since $f$ is surjective there is some $y$ such that $f(y) = S$. Then is $y \in S$?

Answer 2

If $f$ is surjective, there exists $a\in A$ such that $f(a)=S$. Now, if $a\in S$, then $a\not\in f(a)=S$; and if $a\not\in S=f(a)$, then $a\in S$. The contradiction shows that no such $a$ can exist: so $S$ cannot be in the image of $f$, and $f$ is not surjective.

Answer 3

You're almost done!

Let $A$ be a set and $f\colon A\to{\cal P}(A)$ a function. Consider $$S = \{x\in A : x\notin f(x)\} \in {\cal P}(A).$$ If $f$ were surjective, there would exist some $z\in A$ such that $f(z)=S$. One might ask: does $z$ belong to $S$? We have: $$z \in S \iff z\notin f(z) \iff z\notin S$$ a contradiction. Thus, $f$ can not be surjective.