The problem comes from Exercise 3.4.6 of Terence Tao's Analysis I. In the book, there is a hint regarding the problem. However, my approach is quiet different from this hint, so I am not sure if my proof is right. Could you please help verify it?
Lemma 3.4.9. Let $X$ be a set. Then the set
$$\{Y : Y\ \text{is a subset of }X\}$$
is a set.
My proof:
(Axioms used)
Axiom 3.6 (Replacement). Let A be a set. For any object $x \in A$, and
any object $y$, suppose we have a statement $P(x, y)$ pertaining to $x$ and
$y$, such that for each $x \in A$ there is at most one y for which $P(x, y)$ is
true. Then there exists a set $\{y : P(x, y)\text{ is true for some }x \in A\}$, such
that for any object $z$,
$$z \in \{y : P(x, y)\text{ is true for some }x \in A\} \Longleftrightarrow
P(x, z)\text{ is true for some }x \in A$$
Axiom 3.10 (Power set axiom). Let $X$ and $Y$ be sets. Then there exists
a set, denoted $Y^X$, which consists of all the functions from $X$ to $Y$ , thus
$f \in Y^X \Longleftrightarrow (f$ is a function with domain $X$ and range $Y$).
According to the power set axiom, we have the set $X^X$. Apply the axiom
of replacement to each element of $X^X$, we construct a set $Z$ such that
$$
\forall x(x \in Z \equiv \exists f(f \in X^X \wedge x = f(X)))
$$
Let $Y = \{\varnothing\} \cup Z$. Now we prove that $Y$ is the set we want. On one hand, for any $S \subseteq X$,
if $S = \varnothing$, then $S \in Y$, as $Y = \{\varnothing\} \cup Z$.
If $S \neq \varnothing$, there exists (Is this assertion right?) a surjective function $g: X \rightarrow S$. $g\in X^X$, and $g(X) = S$, so $S \in Z$, and thus $S \in Y$.
On the other hand, for any $S' \nsubseteq X$, $\exists a(a \in S' \wedge a \notin X)$. To prove that
$S' \notin Y$, we need to show that $\nexists f(f \in X^X \wedge S' = f(X))$. We know that for any function $f: X \rightarrow X$,
$\nexists x(x \in X \wedge f(x) = a)$, so $a \notin f(X)$. Therefore $S' \neq f(X)$, so $S' \notin Y$.
Thus, $Y$ is the set we want. $\square$
Is my proof right?
Best Answer
If you find yourself questioning whether an assertion is correct, that's usually a good sign that you need to prove it in order to assert it. In this case, you are correct that if $S$ is a nonempty subset of $X$, there exists a surjective function $g:X\to S$. However, this is not obvious and is probably something you need to prove for your proof to be complete. (Though of course, how much detail you need to include for your proof to be considered "complete" will depend on the context and your audience.)
Also, you have used more axioms than just the ones you listed: how do you know that if $Z$ is a set, then $\{\emptyset\}\cup Z$ is a set? (Again, depending on context, this may be "trivial" enough that you don't need to say any more.)
Other than that, your proof looks great.