Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

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

share|improve this answer
    
+1 for evincing the idea of the proof. –  LePressentiment Oct 28 '13 at 9:34
add comment

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?

share|improve this answer
    
$T$ can be empty; consider the function $ f : x \to \{ x \} $. –  Neal Lawton Jul 9 at 9:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.