0
$\begingroup$

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

  • 0
    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.2012-04-29

1 Answers 1

3

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.