# Is $f: \mathcal{P}(\omega) \to \omega \cup \lbrace \omega \rbrace, \ x \mapsto \bigcup \lbrace n \in \omega: n \subset x \rbrace$ surjective?

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.

• This is not as much about natural numbers as it is about ordinals. You could ask this question replacing $\omega$ by any ordinal. Namely, if $\alpha$ is an ordinal consider $f\colon\mathcal P(\alpha)\to\alpha+1$ defined by $f(A)=\bigcup A$, which in turn (as my hint suggests) equals to $\sup A$. – Asaf Karagila Feb 4 '15 at 22:22

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\}|$.
HINT: Note that $f(A)=\sup A$, and that the codomain of $f$ is $\omega+1$, and not $\omega$ itself.