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)\}$.

  • 1
    $\begingroup$ 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! $\endgroup$ – skyfire Jan 30 '15 at 23:47
  • $\begingroup$ 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$. $\endgroup$ – Asaf Karagila Jan 30 '15 at 23:49
  • $\begingroup$ Ok makes sense. Seems obvious now, thank you for the help! $\endgroup$ – skyfire Jan 30 '15 at 23:51
  • 1
    $\begingroup$ Tis my pleasure! $\endgroup$ – Asaf Karagila Jan 30 '15 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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