6
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ $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... $\endgroup$ Jun 28, 2022 at 9:26
  • $\begingroup$ The $B$ is the $y$ that you said one needed to find. $\endgroup$
    – Carsten S
    Jun 28, 2022 at 19:41
  • $\begingroup$ The function $x \mapsto \{x\}$ is not surjective onto the powerset of its domain. $\endgroup$
    – BrianO
    Jun 28, 2022 at 22:18

1 Answer 1

12
$\begingroup$

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 singleton. It contains the empty set $\Phi$ also.

Existence of $\xi$ in the proof is the very definition of surjectivity.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .