# Cantor's theorem and the empty set

I understand the standard proof that there exists no surjection $$f: X \to \mathcal{P}(X)$$, but I'm not able to tell whether it deals with the case that $$X = \emptyset$$ or whether I need to rule this out separately.

If I want to prove that $$|X| < |\mathcal{P}(X)|$$, I need to find an injection $$X \hookrightarrow \mathcal{P}(X)$$. In this case, I'm almost certain that I need to rule out the empty set case first. If $$X = \emptyset$$, then the only map $$X \to \mathcal{P}(X)$$ is the empty function with codomain $$\{\emptyset\}$$, which is vacuously injective. Otherwise, I send $$x \mapsto \{x\}$$ for each $$x \in X$$, which is injective.

The proof that no surjection is tougher for me to rule out the case of the empty set.

Suppose $$f: X \to \mathcal{P}(X)$$ is a surjection. Define $$B = \{x \in X \mid x \not \in f(x)\}$$. As $$f$$ is surjective, $$f(a) = B$$ for some $$a \in X$$. But then $$a \in B \iff a \not \in f(a) \iff a \not \in B$$, which is a contradiction.

If $$X$$ is empty, then $$B$$ is empty. I can't find an $$a \in X$$, so that away is ruled out, but this may be a case where the statement is "vacuously" true because the definition of surjectivity starts with "for all."

• It is true: $B$ will be empty. But if $f$ were a surjection, there’d still be an $a \in X = \varnothing$ such that $f(a) = B$. In this special case, this is obviously already absurd. However, nothing prevents us from continuing anyways and using the general argument in this case, too. Oct 29, 2021 at 5:25
• At exactly what point above do you think you used the fact that $X\ne\emptyset$? Oct 29, 2021 at 10:43

• I don't see why you would need to make a special case for an injection $$\emptyset\to \{\emptyset\}$$, because the function $$f:\emptyset\to\{\emptyset\}$$ such that $$f(x)=\{x\}$$ for all $$x\in\emptyset$$ is already the empty map.
• Existence of some $$a\in X$$ such that $$f(a)=\{x\in X\,:\, x\notin f(x)\}$$ comes from the assumption of $$f$$ being surjective. In specific cases this may result in a contradiction by other means in addition to proving that $$a\in f(a)\leftrightarrow a\notin f(a)$$, but the general way is still valid here: the same proof $$\exists f\text{ surjective}\Rightarrow \exists f\text{ surjective},\exists a\in X, (a\in f(a)\leftrightarrow a\notin f(a))$$ works for $$X=\emptyset$$ as well.
The empty set needs no special treatment in any of these arguments. For any set $$X$$, you can define a function $$X\to\mathcal{P}(X)$$ by $$x\mapsto\{x\}$$. If $$X$$ is empty, there are no values of $$x$$ to which this applies, but that is irrelevant; you still have a perfectly well-defined function (which is equal to the empty function).
Similarly, the argument that a surjection cannot exist works perfectly well when $$X$$ is empty. No step of the argument assumes $$X$$ is nonempty. The set $$B$$ can be defined and is a subset of $$X$$, so by definition, surjectivity of $$f$$ says there exists some $$a\in X$$ such that $$f(a)=B$$. This step is valid even if $$X$$ is empty, since you are simply using the assumption that $$f$$ was surjective. (If $$X$$ is empty you immediately can reach a contradiction since there is no $$a\in X$$, but there's nothing wrong with that.)