2
$\begingroup$

Does Fodor's lemma fail for countable ordinals?

For the usual statement of Fodor's lemma to make sense, one needs well-behaved notions of club and stationary sets, which fail for countable ordinals, so let me be more precise.

Question: Let $\alpha$ be a countable limit ordinal. Does there exist a weakly increasing, regressive function $f: \alpha \to \alpha$ such that the image of $f$ is cofinal in $\alpha$?

Here "regressive" means "$f(\beta) < \beta$ for all $0 < \beta < \alpha$", and "weakly increasing" means "$f(\beta) \leq f(\gamma)$ for all $\beta \leq \gamma <\alpha$". I'm also interested in the version of the question where $f$ is defined only on limit ordinals $<\alpha$.

Motivation: For me, the biggest significance of Fodor's lemma is the following. Whenever I'm trying to construct something by transfinite induction, and I find myself saying "well, I can't do the construction at this step directly, but if I just go back at this stage and modify the results of a few of the previous steps a little bit, then ..." I immediately stop, because if I keep doing this, then by Fodor's lemma my construction will never "settle down": there will be necessarily be stages of the construction which keep being modified at later and later stages, and the whole thing will never be well-defined. However, if Fodor's lemma fails for countable ordinals, then there's some possibility that a strategy of this form can be successful for constructions which induct only over a countable ordinal. One just needs to take a function $f$ as above, and guarantee that at stage $\beta$, one does not modify anything which came before stage $f(\beta)$.

Improve this question
$\endgroup$
7
  • $\begingroup$ I think your definition still needs some fixing, where is $0$ going to go? I expect this will boil down to whether there is such a function on $\omega$ after fixing the definition $\endgroup$
    – Alessandro Codenotti
    Commented Nov 13, 2020 at 17:19
  • $\begingroup$ Also many countable ordinals don't have cofinal sequences made of limit ordinals at all, so restricting to limit ordinals also seems to have issues $\endgroup$
    – Alessandro Codenotti
    Commented Nov 13, 2020 at 17:21
  • $\begingroup$ @AlessandroCodenotti Thanks, fixed! I don't think this boils down to the case $\alpha = \omega$. In that case we can trivailly take the predecessor function (with an arbitrary value on 0). I agree that the answer will be depend on $\alpha$ in the case where $f$ is defined on limit ordinals only. $\endgroup$
    – Tim Campion
    Commented Nov 13, 2020 at 17:21
  • 5
    $\begingroup$ It really does boil down to $\alpha = \omega$. Fix $\langle \alpha_n\rangle_{n < \omega}$ increasing and cofinal in $\alpha$, and set $f(\alpha_{n+1}) = \alpha_n$ and $f(\beta) = 0$ for all other $\beta < \alpha$. Works whenever $\alpha$ has countable cofinality. $\endgroup$
    – Gabe Goldberg
    Commented Nov 13, 2020 at 17:22
  • 7
    $\begingroup$ How about $f(\alpha)=\alpha_n$ for $\alpha_n<\alpha\leq\alpha_{n+1}$? $\endgroup$
    – Wojowu
    Commented Nov 13, 2020 at 17:40

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .