5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Asaf Karagila Feb 4 '15 at 22:22
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

HINT: Note that $f(A)=\sup A$, and that the codomain of $f$ is $\omega+1$, and not $\omega$ itself.

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