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

1 Answer 1

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

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

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