elementary set theory - 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|$ $<$ $|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!! :)

Answer

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.