Is Every Set That Maps Surjectively from Omega Countable?

[evinda]

Hello! (Wave)

I am looking at the proof of the following proposition:

Let $X \neq \varnothing$. $X$ is at most countable iff there is a $f: \omega \overset{\text{surjective}}{\rightarrow} X$.

Proof:

"$\Rightarrow$" If $X$ is infinite, then obviously there is a $f: \omega \overset{\text{surjective}}{\rightarrow} X$.

If $X$ is finite then $X \sim n$ for some $n \in \omega, n \neq 0$ since $X \neq \varnothing$.

We define the extension $f$ of $g$ at $\omega$:

$$f(k)=g(k) \text{ for } k<n \\ f(k)=g(0) \text{ for } k \geq n$$

and obviously $f: \omega \overset{\text{surjective}}{\rightarrow} X$
"$\Leftarrow$" We assume that $f: \omega \overset{\text{surjective}}{\rightarrow} X$.

For each $a \in A$ we define $S_a=f^{-1}(\{a\})$.

Since $f: \omega \overset{\text{surjective}}{\rightarrow} X$ the set $S_a$ is nonempty for each $a \in X$.
So there is the $\min S_a$ for each $a \in X$. We define $h(a)=\min S_a$ for all $a \in X$.

For $a \neq b$ with $a,b \in X$ we have $h(a) \neq h(b)$ since $S_a \neq S_b$. So $h: X \overset{1-1}{\rightarrow} \omega$

Thus, $X$ is at most coutable.

I haven't understood why we can define $S_a=f^{-1}(\{a\})$.

We know that if $n \in \omega$ and $x \in X$, it can be $f(n)=x$.

But in this case we take $f(S_a)=\{a\}$.

Do we assume that $\{a\} \in X$ ?

 

[mmwave]

Hello! It seems like you are trying to understand the proof of the proposition, so I will try to explain it to you. First, let's define what $f^{-1}(\{a\})$ means. This notation means the preimage of the set $\{a\}$ under the function $f$. In other words, it is the set of all elements in the domain of $f$ that map to $a$.

Now, in the proof, we are assuming that $f: \omega \rightarrow X$ is a surjective function. This means that for every element $a \in X$, there exists at least one element $n \in \omega$ such that $f(n)=a$. In other words, every element in $X$ has at least one preimage under $f$. This is why we can define $S_a=f^{-1}(\{a\})$ for every $a \in X$.

I hope this explanation helps! Let me know if you have any other questions.