Is f a injective function for the function below

Question

I have a question, suppose we have $f:\omega_{1}^* \to \omega_{1}$ satisfies $f(\alpha)<\alpha$, with $\omega_{1}^*=\{\lambda\in \omega_{1} :\lambda \,\text{limit} \}$ can $f$ be injective?

My guess is yes but I don't really know how to approach the problem

Answer 1

$f$ cannot be injective. In fact it is constant on a set of size $\aleph_{1}$.

As Asaf already pointed out in the comments, this is due to Fodor's lemma: $\omega_1^*$ is a stationary subset of $\omega_1$ (since clearly every club $C \subseteq \omega_1$ contains a limit ordinal - in fact the limit points $C' \subseteq C$ forms a smaller club consisting entirely of limit ordinals). Now, because $f$ is decreasing on a stationary subset of $\omega_1$, Fodor's lemma immediately implies that $f$ is constant on a stationary subset of $\omega_1$ and thus it is stationary on a subset of size $\aleph_1$ of $\omega_1$. In particular $f$ is not injective.

Answer 2

We can also answer this without the Pressing-Down Lemma (Fodor's Lemma) because $\omega_1^*$ is closed and unbounded (c.l.u.b., or "club") in the $\epsilon$-order topology on $\omega_1.$

Extend the domain of $f$ to $\omega_1$ by letting $f(y)=\sup (y\cap \omega_1^*)$ for $y\in \omega_1\setminus \omega_1^*.$ Then $f(0)=0$ and $f(x)<x$ for all $0<x<\omega_1.$

For each $x$ there is a least finite $H(x)\in \{0\}\cup \Bbb N$ such that $f^{H(x)}(x)=0.$ Otherwise $(f^n(x))_{n\in \Bbb N}$ would be an infinite strictly decreasing sequence of ordinals.

Let $S(n)=H^{-1}\{n\}.$ We have $\omega_1=\cup_{n\in \{0\}\cup \Bbb N\{\infty}S(n)$ so some $S(n)$ is uncountable. Let $n_1$ be the least $n$ such that $S(n)$ is uncountable. We have $n_1>0$ because $S(0)=\{0\}.$ So $f$ maps $S(n_1)$ to the countable set $S(n_1-1).$ Therefore $\exists x\in S(n_1-1)\;(|f^{-1}\{x\}|=\omega_1).$

Now $(f^{-1}\{x\})\cap \omega_1^*$ is uncountable because $(f^{-1}\{x\}) \setminus \omega_1^*$ is only countable....

....because if $x'$ is the least (or any) member of $\omega_1^*$ that is greater than $x,$ then $x'<y\in \omega_1\setminus \omega_1^*\implies f(y)\geq x'>x,$ so $\sup \;(f^{-1}\{x\})\setminus \omega_1^* \leq x'.$

BTW. If we substitute an uncountable non-closed set $C$ for $\omega_1^*$, this does not work because the extension of $f$ to the domain $\omega_1,$ as defined above, will have $f(y)=y$ for some $y>0.$

I remember Prof. William Weiss talking about this in class: The post office has a machine that sorts letters by moving each letters from higher-numbered slots to lower-numbered slots. This worked until there was a letter in every slot numbered less than $\omega_1$ and the machine jams because uncountably many letters have to go into one slot....