Function from $\omega_1$ to $\omega$: $\exists n\in\omega~(\cup f^{-1}(n)=\omega_1)$

57 Views Asked by At

Let $f:\omega_1\to\omega.$ Why must there exist $n\in\omega$ such that $\cup f^{-1}(n)=\omega_1?$ Why must there exist $m\in\omega$ such that $\cap f^{-1}(m)=0?$

This problem seems related to cofinality. The two parts seem related, and perhaps once we prove one part it will be clear how to prove the other part. I first conjectured that $f$ has to be bounded, but that's (very) false; for example, the function $$f:\omega_1\to\omega:x\mapsto\begin{cases}x&\text{if }x<\omega,\\0&\text{else}\end{cases}$$ is unbounded. In addition, I conjectured that taking $m=f(0)+1$ might work for the second part, but I got lost/confused as I was trying to prove that and also I suspect that it doesn't actually work.

1

There are 1 best solutions below

4
On BEST ANSWER

The sets $f^{-1}[\{n\}]$ partition $\omega_1$ into countably many parts. The union of countably many countable parts would be countable, so at least one of those parts must be uncountable. That is, there must be an $n\in\omega$ such that $f^{-1}[\{n\}]$ is uncountable and hence cofinal in $\omega_1$. But $f^{-1}[\{n\}]\subseteq f^{-1}[n+1]$, so $f^{-1}[n+1]$ is cofinal in $\omega_1$, and its union is therefore $\omega_1$.

For the second part of the question, let $n=f(0)$; then $$0\in f^{-1}[\{n\}]\subseteq f^{-1}[n+1]\;,$$ so $\bigcap f^{-1}[n+1]=0$.