# 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!! :)

-

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.

-
Thank you for your answer! I feel as though this is a stupid question, but how can $a$ not be an element of $f(a)$ ? Can you please provide an example of this? – nicefella Apr 8 '13 at 5:35
@nicefella: Let $A=\{0,1\}$, and define $f:A\to\wp(A)$ by $f(0)=\{1\}$ and $f(1)=\varnothing$, for instance. Then $0\notin\{1\}=f(0)$, and certainly $1\notin\varnothing=f(1)$. – Brian M. Scott Apr 8 '13 at 5:42
Thank you so much!! – nicefella Apr 8 '13 at 5:53
@nicefella: You’re very welcome. – Brian M. Scott Apr 8 '13 at 5:54

The idea is to prove that any mapping from $A$ to $P(A)$ will miss certain subsets of $A$. Consider any mapping, say $\phi$ from $A$ to $P(A)$. Now look at the set $B$ defined as follows. $$B = \{a \in A: a \notin \phi(a)\}$$ Clearly, $B \in P(A)$. Now can we find $b \in A$ such that $\phi(b) = B$?

-
+1 for evincing the idea of the proof. – Timere Oct 28 '13 at 9:34

Hint: Assume you have a surjection, consider the set $$T:x\not \in f(x)$$ and claim that $T$ is not empty. How does this help?

-
$T$ can be empty; consider the function $f : x \to \{ x \}$. – Neal Lawton Jul 9 '14 at 9:00