$f: \omega_1 \to \omega_1$. $\forall$ $\alpha$ $\exists$ $\beta > \alpha $ with $f(\beta)=\beta $.

Question

Prove: if $f: \omega_1 \to \omega_1$ is an increasing, continuous, unbounded, function, then $\forall$ $\alpha$ $\exists$ $\beta > \alpha $ with $f(\beta)=\beta $.

Can anyone give me a tip?

Answer 1

The use of quantifiers in the expression ‘$\exists\,\forall\alpha$ a $\beta>\alpha$ with $f(\beta)=\beta$’ really isn’t correct: you mean ‘$\forall\alpha\,\exists\beta>\alpha$ such that $f(\beta)=\beta$’.

HINT: First prove that $f(\alpha)\ge\alpha$ for all $\alpha\in\omega_1$. Now let $\alpha\in\omega_1$ be arbitrary. Let $\alpha_0=\alpha+1$. Given $\alpha_n$ for some $n\in\omega$, let $\alpha_{n+1}=f(\alpha_n)$. Can you see how to use $\langle\alpha_n:n\in\omega\rangle$ to find a $\beta$ with the desired properties?

Answer 2

Here is a slightly more convoluted proof using Fodor's lemma and the machinery of clubs and stationary sets. First let me review some of the definitions, and then we can get down to business.

1. We say that $C\subseteq\omega_1$ is a closed and unbounded set (club) if it is closed in the order topology, and $\sup C=\omega_1$.

2. We say that $S$ is a stationary set if for every club $C$, $S\cap C\neq\varnothing$. For example, every club is a stationary set.

3. Fodor's lemma. Suppose that $S$ is a stationary set and $f\colon S\to\omega_1$ is regressive, that is $f(\alpha)<\alpha$ for every $\alpha\in S$. Then there is some stationary $S'\subseteq S$ such that $f\upharpoonright S'$ is constant.

4. The set $C$ is a club if and only if there exists $f\colon\omega_1\to\omega_1$ which is normal (increasing, unbounded, continuous) and $C=\operatorname{rng}(f)$.

Finally, we can finish the proof.

Let $C$ be the range of $f$, then $C$ is a club. Suppose by contradiction that $\alpha$ is such that for every $\beta>\alpha$ we have $\beta\neq f(\beta)$. Note that $C'=C\setminus\alpha=\{\beta\in C\mid\beta>\alpha\}$ is also closed and unbounded, and therefore stationary.

Consider the function $g\colon C'\to\omega_1$ defined by $g(\beta)=f^{-1}(\beta)$, and I will leave it to you to verify that we can always require that $f$ is injective. I claim that $g(\beta)<\beta$ for every $\beta$ in $C'$.

The reason is that we can prove by transfinite induction that $\gamma\leq f(\gamma)$. Suppose it holds for every $\delta<\gamma$, then $\gamma=\sup\{\delta\mid\delta<\gamma\}\leq\sup\{f(\delta)\mid\delta<\gamma\}=f(\gamma)$ for the case of limit $\gamma$; in the successor case injectivity does the work, since if $\gamma\leq f(\gamma)$ then $\gamma+1\leq f(\gamma+1)$, otherwise $f(\gamma+1)\leq f(\gamma)$ which is a contradiction to $f$ being normal.

So since $\gamma\leq f(\gamma)$ we have that $g(\beta)\leq\beta$. However we assumed, by contradiction, that if $\beta>\alpha$ then there is no equality, and so $g(\beta)<\beta$. So $g$ is regressive on a club, and so it must be constant on a stationary set. However $f$ is injective, so $g$ cannot be constant on any set of more than one element!

And so we have a contradiction to Fodor's lemma. $\square$

---

That been said, the above machinery is very important, but Brian's answer is the "correct" approach for this problem.