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

• This can be proved by contradiction. Take your bijective map and construct a "contradictory" set in power set such that it is absurd that there is a map from $A$. May 15, 2018 at 17:03

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? Apr 8, 2013 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)$. Apr 8, 2013 at 5:42

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

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 \}$. Jul 9, 2014 at 9:00

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

• Copy and paste from your notes, eh? What's chapter 2, and how do we see it? Mar 27, 2017 at 19:46
• I'm inclined to give a +1 for boldness. Mar 27, 2017 at 20:02