weakening of Fodor's theorem

Question

I need to find a proof of the following statement:

Suppose $f:\omega_1 \rightarrow \omega_1$ such that $f(\alpha)<\alpha$, for every $\alpha$. Then $\exists \beta\in\omega_1$ such that $f^{-1}(\beta)$ is uncountable.

I don't know Fodor's theorem, but I was told that this is a particular case of the theorem. Anyway I can't use it. I also tried to have a look at the proof of that theorem (which unfortunately uses some notions that I have never encountered), but it didn't seem so much helpful. Anyway I have a hint: Suppose not, show that $\exists \alpha$ such that $\forall \beta<\alpha.(f^{-1}(\beta)\subseteq \alpha)$. I really can't see why such an $\alpha$ shouldn't exist, indeed I think that all $\alpha$ should behave in such a way. On the top of that, I can't actually see how I can get to a contradiction now!

I suppose these are really stupid questions, anyway I would be very grateful to anyone who feels like giving me some help.

Answer 1

We should say $f(a)<a$ for $0<a<\omega_1.$ So let $f(0)=0.$

For $x\in \omega_1$ let $f^0(x)=x$ and $f^{n+1}(x)=f( f^n(x) )$ for $n\in \omega.$ The sequence $(f^n(x))_{n\in \omega}$ is decreasing but cannot be strictly decreasing for all $n\in \omega,$ else it would be a strictly decreasing infinite sequence of ordinals. So for some $n$ we have $f^n(x)=f^{n+1}(x)=f(f^n(x)),$ which implies $f^n(x)=0.$

For $x\in \omega_1$ let $g(x)$ be the least $n$ such that $f^n(x)=0.$ For brevity (and less typing) let $G_n=g^{-1}\{n\}.$ We have $$\omega_1=\cup_{n\in \omega}G_n.$$ The Axiom of Choice implies that a countable union of countable sets is countable, so there exists $n$ such that $G_n$ is uncountable. Let $n_0$ be the least such $n.$ We have $n_0>0,$ because $G_0=\{0\}$ is countable. So $n_0-1$ exists.

Observe that $x\in G_{n_0}\iff f(x)\in G_{n_0-1}.$ In other words, $$G_{n_0}=\cup \{f^{-1}\{y\}:y\in G_{n_0-1}\}.$$ By def'n of $n_0,$ the set $G_{n_0-1}$ is countable. So $f^{-1}\{y\}$ cannot be countable for every $y\in G_{n_0-1},$ else $G_{n_0}$ would be a countable union of countable sets.

Therefore $\exists y\in G_{n_0-1}\;(|f^{-1}\{y\}|=\omega_1).$

Remark: This is a weaker result, rather than a special case, of Fodor's Lemma (The Pressing-Down Lemma), which says that for some $y$ the set $f^{-1}\{y\}$ is stationary in $\omega_1,$ which takes a paragraph to define.

Answer 2

Suppose $A_{\beta} = \{\alpha \in \omega_1: f(\alpha) = \beta\}$ is countable for every $\beta \in \omega_1$. Construct an increasing sequence $\gamma_0 = \omega < \gamma_1 < \gamma_2 < \dots < \gamma_n < \dots$ in $\omega_1$ such that for every $n$, for every $\beta < \gamma_n$, $A_{\beta} \subseteq \gamma_{n+1}$. This can be done because each $\gamma_n$ is countable and a countable union of countable sets is countable. Let $\gamma$ be the least ordinal above every $\gamma_n$. Now $f(\gamma) = \beta < \gamma$ so for some $n$, $\beta < \gamma_n$ implying that $\gamma \in A_{\beta} \subseteq \gamma_{n+1}$ which is impossible.