4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$ Sep 20, 2021 at 20:43

4 Answers 4

6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$
    – roxingby
    Sep 20, 2021 at 21:23
  • $\begingroup$ @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. $\endgroup$ Sep 20, 2021 at 21:25
  • $\begingroup$ 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? $\endgroup$
    – roxingby
    Sep 20, 2021 at 21:33
  • 2
    $\begingroup$ @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$. $\endgroup$ Sep 20, 2021 at 21:34
  • 2
    $\begingroup$ 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$. $\endgroup$
    – roxingby
    Sep 20, 2021 at 21:46
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.