Cardinality of a set A is strictly less than the cardinality of the power set of A I am trying to prove the following statement but have trouble  comprehending/going forward with some parts! Here is the statement:


  If $A$ is any set, then  $|A|$ $&lt;$ $|P(A)|$


Here is what I have so far:

We need to show that there is an injection from $A$ to $P(A)$ but not a surjection. 

A natural choice for an injection is the function $ f(x)$ $=$ $\{x \}$, which in plain English, takes any element $x$ (that is in $A$) and sends it to the one-element set $\{x \}$. Thus $f(x)$ is injective!

To show that there is no surjection, for the sake of contradiction, assume there is a surjection. Here is where I start to have trouble. Surjectivity means that every element of the co-domain is mapped to an element of the domain, correct? Consequently, in this particular case, we are "matching" sets (from $P(A)$) to elements (from $A$) right?

If the above is correct, my problem arises here. I am not sure how to prove that $f$ is not surjective. Unfortunately, I am easily confused by notation so please explain in English. 
Thank you in advance!! :)
What you want here is the so-called diagonal argument. The idea is to show that no matter what function $f:A\to\wp(A)$ you look at, you can find a subset $S_f$ of $A$ that is not in the range of $f$. If you can do that, you’ve shown that there is no map of $A$ onto $\wp(A)$ and therefore certainly no bijection from $A$ to $\wp(A)$.

To build the set $S_f$, imagine that you could somehow go through the set $A$ one element at a time. You look at an element $a\in A$, and one of two things must be true: either $a\in f(a)$, or $a\notin f(a)$. (Remember, $f(a)$ is some subset of $A$, so it’s meaningful to ask whether that subset contains $a$.) Since we’re building the set $S_f$ to suit ourselves, we get to decide whether $a\in S_f$ or not, and we’ll decide in exactly the opposite way from the function $f$: if $a\notin f(a)$, we’ll put $a$ into $S_f$, and if $a\in f(a)$, we won’t put $a$ into $S_f$. After we’ve done this for each $a\in A$, our set $S_f$ will contain exactly those $a\in A$ such that $a\notin f(a)$:

$$S_f=\{a\in A:a\notin f(a)\}\;.$$

For each $a\in A$, therefore, the sets $S_f$ and $f(a)$ differ in how they treat $a$: if $a\in f(a)$, then $a\notin S_f$, and if $a\notin f(a)$, then $a\in S_f$.

That’s almost the entire argument: all you have to do to finish it off is explain why this ensures that for $S_f$ is not the set $f(a)$ for any $a\in A$ and why this implies that $S_f$ is not in the range of $f$ and hence that $f$ is not a surjection.
Suppose that we had such a matching. Then for every element a ∈ A, there
is a subset Sa of A matched to it, so that every subset of A occurs as Sa for some a.
We have to show that this is impossible, by producing a set which is missed out.
We follow Bertrand Russell’s idea (see the supplementary material for Chapter
2). Let B consist of all those elements a of A which do not lie in the subset
they label:
B = {a ∈ A : a ∈/ Sa}.
Now, if we have a complete matching, then the subset B must occur in the matching,
that is, B = Sb for some element b ∈ A. But this is impossible. For, if b ∈ Sb,
then by definition b ∈/ B, while if b ∈/ Sb, then b ∈ B; so the sets B and Sb differ
at the element b (one contains it, the other doesn’t), and cannot be equal. So the
proposed matching is not complete