Skip to main content
5 of 7
added 636 characters in body
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

OK, third time's the charm, hopefully:

First, a lemma:

Fix an arbitrary successor ordinal $\beta$ and a nondecreasing regressive map $f$ with domain $\beta-\{0\}$. Then there is a nondecreasing regressive map $d_f$ with the same domain such that $f\le d_f$ and $d_f$ takes on only finitely many values.

The proof is by induction on $\beta$. The base case $\beta=2$ is trivial, as is the successor-of-a-successor case.

Now suppose the proof holds for all non-limit $\gamma<\lambda+1$ for $\lambda$ a limit, and take $\beta=\lambda+1$. Fix some successor ordinal $\chi$ with $\chi<\lambda$ and $\chi>f(\lambda)$; such a $\chi$ must exist since $\lambda$ is limit and $f$ is regressive.

But now consider the map $F=f\upharpoonright \chi$. Since $\lambda$ is limit and $\chi<\lambda$ is a successor ordinal, we may apply the induction hypothesis to get a $d_{F}$. But now consider the map $d_f$ with domain $\lambda-\{0\}$ extending $d_{F}$ and taking on the value $max\{f(\lambda), d_F(\epsilon)\}$ (where $\epsilon+1=\chi$) on all inputs $\theta$ with $\chi<\theta \le\lambda$. This function has the desired properties - in particular, it is regressive by choice of $\chi$ - so we are done. QED


Now, to answer the actual question: fix a nondecreasing regressive $f$ defined on $\omega_1-\{0\}$. By Fodor's lemma + nondecreasingness, $f$ is eventually constant; fix some countable successor ordinal $\alpha$ such that for all $\beta>\alpha$, $f(\beta)=f(\alpha)=\gamma$.

Apply the lemma to $f\upharpoonright \alpha$ to get a function $d_0$; now extend $d_0$ to a function $d$ defined on all of $\omega_1-\{0\}$ by setting $d(\theta)=max\{f(\alpha), d_0(\epsilon)\}$ (where $\epsilon+1=\alpha$) for all $\theta\ge\alpha$.

Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331