2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 29, 2021 at 5:25
  • 1
    $\begingroup$ At exactly what point above do you think you used the fact that $X\ne\emptyset$? $\endgroup$ Oct 29, 2021 at 10:43

2 Answers 2

3
$\begingroup$
  • 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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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