Proof that no set is equinumerous to its power set

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

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

Answer 4

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).