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.

Here is a proof that a set $A$ cannot be bijected to $P(A)$.

Suppose $f:A↔P(A)$ is a bijection

$$W:= \{a \in A \mid a \notin f(a)\}, $$ so for any $a$, $$a \in W\text{ iff }a \notin f(a)\;.$$ $f$ is a bijection, so $W=f(a_0)$ for some $a_0 \in A$.

$$a\in f(a_0)\text{ iff }a \notin f(a)$$

This last line is a contradiction.

What does $a \in W\text{ iff }a \notin f(a)$ mean? I understand that $f(a)$ is a set, but why is it important that $a$ is not in the set $f(a)$?

share|improve this question
    
iff means "if and only if" –  Alex Becker Apr 29 '12 at 18:17
    
The final line should say that for any $a\in A$, $a\in f(a_0)\text{ iff }a\notin f(a_0)$; that’s the actual contradiction. Each $a\in A$ belongs to the set $f(a_0)$ if, and only if, it does not belong to that set, which is clearly absurd. –  Brian M. Scott Apr 29 '12 at 18:24

1 Answer 1

up vote 3 down vote accepted

If $a_0\in W$, then by definition $a_0\notin f(a_0)$. But by assumption, $f(a_0)=W$. So $a_0\in W$ if and only if $a_0\notin W$, and that is a contradiction; we are saying something is true if and only if it is false.

Note. I don't like giving this proof by contradiction; I prefer to give it as a direct proof: if $f\colon A\to \mathcal{P}(A)$, then $f$ is not onto. We do this by showing that no element maps to the set $W$. The proof that no element maps to $W$ (and so $f$ is not onto) is:

If $a\in f(a)$, then $a\notin W$, so $f(a)\neq W$ (since one of $f(a)$ and $W$ contains $a$ and the other does not).

If $a\notin f(a)$, then $a\in W$, so again, $f(a)\neq W$ (one of $f(a)$ and $W$ contains $a$, but the other does not).

Either way, $f(a)\neq W$; as this holds for all $a\in A$, it follows that $W$ is not in the image of $f$, so $f$ is not onto. $\Box$


I also find that it is instructive to see how this works with some specific sets.

Say $A=\{0,1,2\}$, so $$\mathcal{P}(A) = \Bigl\{\varnothing, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\}\Bigr\}.$$

Let's take some functions $A\to\mathcal{P}(A)$, and see what we get. Say, $f_1,f_2,f_3\colon A\to\mathcal{P}(A)$ given by $$\begin{align*} f_1(0) &=\varnothing, & f_1(1) &= \{1\}, & f_1(2) &= \{0,1,2\}\\ f_2(0) &=\{0,1,2\}, & f_2(1) &=\{2\}, & f_2(2) &= \{2\},\\ f_3(0) &= \{0\}, & f_3(1)&=\{1,2\}, &f_3(2) &=\{1,2\} \end{align*}$$

Then $$\begin{align*} W_1 &= \{a\in A\mid a\notin f_1(a)\}\\ &= \{0\};\\ W_2 &= \{a\in A\mid a\notin f_2(a)\}\\ &= \{1\};\\ W_3 &=\{a\in A\mid a\notin f_3(a)\}\\ &=\varnothing. \end{align*}$$ To see this, for instance, note that $f_1(0)=\varnothing$ and $0\notin\varnothing$, so $0\in W_1$; but $f_1(1) = \{1\}$, and $1\in\{1\}$, so $1\notin W_1$. And $f_1(2)=\{0,1,2\}$, and $2\in \{0,1,2\}$, so $2\notin W_1$>

Now notice that $W_1=\{0\}$ is not in the image of $f_1$ (which consists precisely of $\varnothing$, $\{1\}$, and $\{0,1,2\}$); $W_2 = \{1\}$ is not in the image of $f_2$; and $W_3=\varnothing$ is not in the image of $f_3$.

Of course, with finite sets we can use simple counting arguments, but this idea goes through to the infinite case. These finite examples just show you how $W$ is constructed.

share|improve this answer

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.