Solutions to selected exercises for Week 4

5. Prove that if $\lambda$ is a limit ordinal, then $\text{cf}(\lambda)$ is the least ordinal $\alpha$ such that there is a cofinal function $\alpha \to \lambda$. (If we replaced "cofinal function" with "cofinal increasing function" then this would say something we already know.)

   Solution: Let $\alpha \le \text{cf}(\lambda)$ and let $f: \alpha \to \lambda$ be a cofinal function. We will show that $\alpha = \text{cf}(\lambda)$. Define a function $g: \alpha \to \lambda$ by transfinite recursion: For $\xi \lt \alpha$ let $g(\xi)$ be the least ordinal that is greater than or equal to the strict supremum of $\text{ran} (g \restriction \xi)$ and also greater than or equal to $f(\xi)$. By induction we can show that $g(\xi) \lt \lambda$ using the fact that $\xi \le \alpha \lt \text{cf}(\lambda)$. Moreover the function $g$ is clearly increasing, and it is cofinal in $\lambda$ because because $g(\xi) \ge f(\xi)$ for all $\xi \lt \lambda$ and the function $f$ is cofinal in $\lambda$. Therefore $\text{cf}(\lambda) \le \text{dom}(g) = \alpha$ as desired.