# proof detail concerning bijection between a set and its power set

Theorem: If $X$ is a set, then $X$ is not equivalent to its power set.

Proof: suppose for a contradiction that $f:X\to P(X)$ is a bijection. Define $B:=\{x \in X, x\not\in f(x)\}$. Because $f$ is surjective (onto), there is a $b$ in $X$ with $B=f(b)$. Now $b$ in $B$ would imply $b$ in $B=f(b)$. By definition of $B$, this would mean that $b$ is not an element of $f(b)=B$. Thus we infer $b$ is not an element of $B$. But then $b$ is not an element of $B=f(b)$, which by definition of $B$ forces $b$ in $B$, a contradiction.

I understood this proof until he reached the part that says "Now $b$ in $B$ would imply $b$ in $B=f(b)$..."

This seems problematic to me because the assumption $b$ in $B$ seems unwarranted. Since $B$ is a subset of $X$ it makes sense if we had $b$ in $B$ and then arrived at $b$ in $X$ but the reverse does not seem like a valid step and I'm left wondering if the resulting contradiction that arised came simply from the assumption $b$ is in $B$ and therefore only means that $b$ is not not an element of $B$, And that this has no bearing on the bijection part of the argument. In fact I dont even see how this connects to the part of the argument that used the onto property of bijectiveness.

You start with $X$ and with $f$. Now you define $B$, and you say that $b\in X$ is such that $f(b)=B$.

Since $B$ is a subset of $X$ and $b$ is an element of $X$, it has to be that either $b\in B$ or $b\notin B$. Deriving $b\in X$ from $b\in B$ is meaningless, it tells us nothing new. But asking whether or not $b$ is also an element of $B$ or not, that is progress! So we have two cases:

1. If $b\in B$, then $b\in f(b)$. Then by definition of $B$, $b\notin B$. So this can't be.
2. If $b\notin B$, then $b\notin f(b)$. Then by definition of $B$, $b\in B$. Again, this cannot be.

So it is impossible that there is some $b\in X$ such that $f(b)=\{x\in X\mid x\notin f(x)\}$.

• Dumb question question but is $b\in B$ the same thing as $b\in B = f(b)$? because $b\in f(b)$ seems to forbidden since the property of a function requires is to be well defined. Otherwise your answer was exactly what I was looking for! – skyfire Jan 30 '15 at 23:47
• Yes, the point is that we assume that $f(b)=B$. So we divide into two parts, one of which has to be true, either $b\in B$ or $b\notin B$. Since either case leads to a contradiction, it must be the case that there is no $b$ such that $f(b)=B$. – Asaf Karagila Jan 30 '15 at 23:49
• Ok makes sense. Seems obvious now, thank you for the help! – skyfire Jan 30 '15 at 23:51
• Tis my pleasure! – Asaf Karagila Jan 30 '15 at 23:51