# Proof that no set is equinumerous to its power set

I am studying from Enderton's book "Elements of set theory" and I am struggling with the proof that "No set is equinumerous to its power set".

Here is the proof:

Let $$g: A\rightarrow \mathcal{P}A$$; we will construct a subset $$B$$ of $$A$$ that is not in ran $$g$$. Specifically, let $$B = \{x\in A\mid x\notin g(x)\}$$. Then $$B\subseteq A$$, but for each $$x\in A$$, $$x\in B$$ iff $$x\notin g(x)$$. Hence $$B\neq g(x)$$.

I saw on the web another proof that is almost the same and seems a tiny bit clearer, but I am having the same trouble. The doubt is: what prevents us from thinking that $$x\notin g(x)$$ is actually a contradiction, just like $$x\neq x$$, and that therefore $$B=\emptyset$$? This proof seems to assume that there must be an $$x$$ such that $$x\notin g(x)$$, but I don't see where this is coming from.

I am a just starting undergrad student, I am sorry if this question may be a bit naive. Thanks.

• The proof does not assume there exists an $x$ such that $x\notin g(x)$, and indeed $B$ might well be empty. This is not a problem. Consider, for example, the function $g$ that maps $x\in A$ to the singleton set $\left\{x\right\}$. In this case the constructed set $B$ is the empty set, and indeed $\emptyset$ is not in the image of $g$. Sep 20, 2021 at 20:43

Once we define $$B = \{x \in A \mid x \notin g(x)\}$$, the proof then proceeds as follows:

Suppose that $$B$$ is in the range of $$g$$. Then we can take some $$x \in A$$ such that $$g(x) = B$$, by the definition of range.

We will first show that $$x \notin B$$. Suppose for the sake of deriving a contradiction that $$x \in B$$. Then $$x \notin g(x) = B$$ by the definition of $$B$$. This contradicts the claim that $$x \in B$$. Therefore, we have proven that it cannot be true that $$x \in B$$; thus, $$x \notin B$$.

We now know that $$x \notin B = g(x)$$. Therefore, since $$x \in A$$ and $$x \notin g(x)$$, $$x \in B$$ by the definition of $$B$$. But this is a contradiction.

Therefore, our assumption that $$B$$ is in the range of $$g$$ must be incorrect.

Notice that this proof in no way depends on the claim that $$B \neq \emptyset$$. Nowhere do we make any assumption that $$B$$ is not empty.

In fact, there are some cases where $$B$$ is the empty set. Consider the function $$g(x) = \{x\}$$. In that case, $$B = \{x \in A \mid x \notin g(x)\} = \{x \in A \mid x \notin \{x\}\} = \emptyset$$.

• Thanks for the very clear answer, I now understand. As an exercise of nitpicking, and because I cannot answer this question myself, why doesn't the definition of $B$ in this case go against the subset axiom scheme, as we have that for some $x\in A$, $f(x)=B$? Sep 20, 2021 at 21:23
• @roxingby We know that $B$ is well-defined because of the axiom scheme of separation. In general, for any statement $P(x)$, the set $\{x \in A \mid P(x)\}$ will always exist. In this case, $P(x)$ is the statement $x \notin g(x)$. So the definition of $B$ makes sense exactly because of the subset axiom scheme. Sep 20, 2021 at 21:25
• But this is exactly the the thing I am saying, but for the subset axiom scheme the property needs to not reference the set which is building ($B$ in this case). But here, by saying $x\notin g(x)$, for some $x$ we have the property $x\notin g(x)=B$ (because we have defined that there is an $x$ such that $g(x)=B$). Thus, isn't it going against the axiom? Sep 20, 2021 at 21:33
• @roxingby The property does not reference $B$ in any way. The property is simply $x \notin g(x)$. No reference to $B$ is contained in this property. Keep in mind that the $x$ which appears in $\{x \in A \mid x \notin g(x)\}$ has nothing to do formally with the $x$ that appears in "Then we can take some $x \in A$ such that $g(x) = B$". I could have said "Then we can take some $y \in A$ such that $g(y) = B$" and then rewritten the proof using $y$. Sep 20, 2021 at 21:34
• Thanks, now I understand. I also think that one problem in my argument was the fact that we had actually defined $B$ to exist before we assumed that $g(x) =B$ for some $x$. Sep 20, 2021 at 21:46

It's completely possible that $$x \in g(x)$$ for every $$x \in A$$. But if this is the case, then the set $$B$$ is just the empty set $$\emptyset$$, which is a perfectly good element of $$\mathcal{P}A$$ that also doesn't equal $$g(x)$$ for any $$x$$ (because every set $$g(x)$$ contains at least one element, namely $$x$$ itself). So the proof still works.

Try it with an example. E.g., take $$A = \{0, 1, 2\}$$ and $$g(x) = \{2 - x\} \cup \{0\}$$. Then $$2 \not\in g(2)$$, but $$0 \in g(0)$$ and $$1 \in g(1)$$. There is no contradiction there, and the proof correctly reveals that $$\{2\} \not\in \mathrm{ran}(g)$$. Alternatively, if you defined $$h(x) = \{x\}$$, then $$x \in h(x)$$ for every $$x$$, but that's OK, because then the proof correctly gives you that $$\emptyset \not\in \mathrm{ran}(h)$$.

Let $$x\in A$$. You showed that $$x\in B\iff x\notin g(x)$$. This proves that $$B\neq g(x)$$, otherwise we would have $$x\in B\iff x\notin B$$, which makes no sense. Therefore, there exists no $$x\in A$$ such that $$B=g(x)$$, which proves that $$g$$ is not onto. Since the reasoning holds for any map $$g:A\to\mathcal P(A)$$, this shows that there exists no surjection from $$A$$ to $$\mathcal P(A)$$, and therefore those two sets are not equinumerous (in fact this even shows that $$\mathcal P(A)$$ has always stricly bigger cardinality).