# I am missing some point about Cantor's Theorem

I don't get the argumentation of Cantor's theorem proof. I must have gone wrong or misunderstood something somewhere so I will try to explain my reasoning below.

Theorem (Cantor) Let $$f$$ be a map from set $$A$$ to its power set $$\mathcal{P}(A)$$. Then $$f : A \to \mathcal{P}(A)$$ is not surjective. As a consequence, $$\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A))$$ holds for any set $$A$$

The theorem is straightforward enough, we need to show that $$f$$ is not surjective, meaning that there is some element $$y \in \mathcal{P}(A)$$ such that there is no $$x \in A$$ such that $$y = f(x)$$. The proof is where I run into trouble.

Proof Consider the set $$B=\{x \in A \mid x \notin f(x)\}$$. Suppose to the contrary that $$f$$ is surjective. Then there exists $$\xi\in A$$ such that $$f(\xi)=B$$. But by construction, $$\xi \in B \iff \xi \notin f(\xi)= B$$. This is a contradiction. Thus, $$f$$ cannot be surjective. On the other hand, $$g : A \to \mathcal{P}(A)$$ defined by $$x \mapsto \{x\}$$ is an injective map. Consequently, we must have $$\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A))$$. $$\tag*{\blacksquare}$$

I do not understand the third sentence in the proof. It says that "if $$f$$ is surjective, then there exists some $$\xi \in A$$ such that $$f(\xi) = B$$".

I do not see why such a $$\xi$$ must exist if $$f$$ is surjective. because consider the injective/surjective mapping of $$f: A \mapsto C$$ where $$f$$ is the identity function and $$A$$ and $$C$$ both contain the same single element. There exists no $$\xi \in A$$ such that $$f(\xi)$$ = B and $$f$$ is surjective. Have I misunderstood something? How can I rectify my above statements with the logic of the proof?

• $f$ is a function with codomain the powerset, and $B$ belongs to the powerset - so if $f$ is surjective, $B$ must lie in the image of $f$. There is no claim that $B$ lies in the image of any surjective function between any two sets... Jun 28 at 9:26
• The $B$ is the $y$ that you said one needed to find. Jun 28 at 19:41
• The function $x \mapsto \{x\}$ is not surjective onto the powerset of its domain. Jun 28 at 22:18

You are forgetting the fact that $$f$$ is surjective onto the power set of $$A$$. If $$A$$ is a singleton then power set of $$A$$ is not a sigleton. It contains the empty set also.
Existence of $$\xi$$ in the proof is the very definition of surjectivity.