Prove that if: $g: \omega_1\rightarrow\omega_1$ then for some $\alpha<\omega_1$: $\forall \beta<\alpha: g(\beta)<\alpha$

Question

Prove that if $g: \omega_1\rightarrow\omega_1$ then for some $0<\alpha<\omega_1$, $\forall \beta<\alpha: g(\beta)< \alpha$

How should I prove this theorem. I don't even know how to start

Answer 1

We generally need to work with the things we have. So what do we have? we have two things:

The first thing we are given are well-orders. Ordinals are well-ordered. And well-orders invite recursion. The second thing, is that we are given $\omega_1$. Why not $\omega$? Why not $\omega+\omega$ or $\omega^3$?

Well, the function $g(n)=n+1$ is a function from $\omega$ to itself, but no $n<\omega$ satisfies this closure property. I leave it to you to find out why $\omega+\omega$, or $\omega^3$, or any countable ordinal, are not going to work either. There will be some function that avoids this condition.

So what is so different about $\omega_1$? Well. Two things, it is uncountable, and its cofinality is uncountable (which in this case means that it is regular). One of these properties should be used, therefore.

---

So let's try the recursion. Start with $\alpha_0=0$, and we should just try to approximate the closure point $\alpha$. What does that mean? Well, it means that we will construct a sequence, such that each ordinal is more and more closed under $g$.

So $\alpha_1$ will be the least ordinal such that $g(\alpha_0)=g(0)<\alpha_1$. This way, we will ensure that $g(0)<\alpha$.

Next, we need to make sure that $g(\beta)<\alpha$ for all $\beta\leq\alpha_1$. So $\alpha_2=\sup\{g(\beta)\mid\beta\leq\alpha_1\}$.

From here, you should be able to continue and define the sequence $\alpha_n$. Finally, take $\alpha=\sup\{\alpha_n\mid n<\omega\}$, and prove that it is a closure point as wanted.

---

So what did we use about $\omega_1$? Not that it is uncountable, as much as it is closed under countable limits. Namely, that its cofinality is uncountable. As an exercise, find a function $g\colon\omega_\omega\to\omega_\omega$ which has no closure point.

Answer 2

The negation of the statement you want to prove is (think about it, it's just standard logic):

$$\forall 0 < \alpha < \omega_1: \exists \beta < \alpha: g(\beta) \ge \alpha$$

So assume the above holds. For definiteness we can define (by well-orderedness) $g(\alpha) = \min \{\beta < \alpha: g(\beta) \ge \alpha\}$.

So $g: \omega_1\setminus\{0\} \to \omega_1$ is a regressive function.

Now apply the pressing down lemma (or Fodor's lemma), to derive a contradiction.