3
$\begingroup$

I was thinking about this question and I have my own thoughts on this, please do let me know if my reasoning is correct.

The question asks if I can pick an $X$ such that this condition is fulfilled for all $Y$.

If the function $f$ is to be surjective, it must mean that every element must be an output of $f$. So if $X$ was countably infinite, this would not be possible, since I can pick $Y$ an uncountably infinite set. So $X$ would have to be uncountably infinite set, but then this set $X$ would not work if $Y$ was the null set, because a function only exists from $f:X \rightarrow \emptyset $ only if $X$ is the null set.

So this statement is false. Is my reasoning correct?

$\endgroup$
  • $\begingroup$ Sometimes question writers forget about the empty set, so they may not want you to use this argument, even though it's perfectly sound. If you're going to answer for credit, then play it safe and give Olivier Roche's Answer. $\endgroup$ – Toby Bartels Oct 14 at 7:21
8
$\begingroup$

There's a straight answer to this question :
For any set $X$, there is no surjection from $X$ onto the power set $\mathcal{P}(X)$.
Proof: Assume for contradiction that $f:X \mapsto \mathcal{P}(X)$ is a surjection.
Consider the subset $Y = \{x \in X \big| x \notin f(x) \}$. Since $f$ is surjective, there is some $x_0 \in X$ such that $f(x_0) = Y$.
But one has $x_0 \in Y \Longleftrightarrow x_0 \notin Y$ by definition of $Y$, a contradiction!

$\endgroup$
3
$\begingroup$

Yes, your reasoning is correct. You could simplify it even: if $X$ is empty, then it cannot surject onto a non-empty set, e.g. $Y = \{1\}$. If $X$ is non-empty, then there is no surjection $X \to \emptyset$ (or even any function).

$\endgroup$
2
$\begingroup$

Yes, although if you allow $Y=\emptyset$, then the cardinality of $X$ is irrelevant as long as $X\ne\emptyset$ (this works even if $X$ is finite).

Another proof of the negative is to choose $Y=\mathcal P(X)$, the power set of $X$ (the set of all subsets of $X$); then Cantor's diagonal argument shows that there is no such surjection.

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