Intro: I am currently preparing for an exam and I have found this particular question in a previous exam of the same class. It is a 'simple' question where you only have to write the answer without justifying it, i.e. no proof is required, but I'd like to understand the problem better.
Please note: $\omega$ is the set of 'natural numbers' as constructed by the axioms of ZFC. My Professor told us to prefer this notation because it is not possible to show that $\omega = \mathbb{N}$. So for this course it happens to be that: $$\omega = \lbrace 0,1,2,3, \dots \rbrace = \lbrace \emptyset, \lbrace \emptyset \rbrace, \lbrace \emptyset, \lbrace \emptyset \rbrace \rbrace , \dots \rbrace $$
Problem: Consider the function: $$f: \mathcal{P}(\omega) \to \omega \cup \lbrace \omega \rbrace, \ x \mapsto \bigcup \lbrace n \in \omega: n \subset x \rbrace $$ Is $f$ injective, surjective, both?
My solution: It does not surprise me that $f$ cannot be injective, because we have $\emptyset, \lbrace \emptyset \rbrace \in \mathcal{P}(\omega)$ and for both we have $$f(\emptyset) = f( \lbrace \emptyset \rbrace)= \emptyset = 0 \text{ but } \emptyset \neq \lbrace \emptyset\rbrace $$ So $f$ is not injective and therefore not bijective. The solution however suggest that $f$ has to be surjective and I am having trouble understanding that.
For every element $x$ in $$ \omega \cup \lbrace \omega \rbrace = \lbrace 0,1,2,3, \dots , \omega \rbrace $$ I want to find an element $y$ in $\mathcal{P}(\omega)$ such that $f(x)=y$. I can see how that works for all $n \in \omega$ but I also have $\omega \in (\omega \cup \lbrace \omega \rbrace)$ to map and I can't wrap my head around the idea of $$f(?)= \omega $$
It would have made sense to me to say $f( \omega) = \omega$ but that would mean that $\omega \in \omega$ by the definition of $f$ and that is forbidden by the Axiom of regularity.
For each $n\in\omega$ we have $n\subseteq\omega$, so
$$f(\omega)=\bigcup\{n\in\omega:n\subseteq\omega\}=\bigcup\omega=\omega\;.$$
If you’re in doubt about that last step, note that $x\in\bigcup\omega$ iff there is an $n\in\omega$ such that $x\in n$, which is true iff $x\in\omega$. Nothing here requires $\omega$ to be an element of $\omega$, so there’s no violation of regularity.
By the way, non-injectivity also follows immediately from the fact that $|\wp(\omega)|>|\omega\cup\{\omega\}|$.