Fodor's lemma

In mathematics, particularly in set theory, Fodor's lemma states the following:

If κ is a regular, uncountable cardinal, S is a stationary subset of κ, and $f:S\rightarrow\kappa$ is regressive (that is, f(α) < α for any $\alpha\in S$, $\alpha\neq 0$) then there is some γ and some stationary $S_0\subseteq S$ such that f(α) = γ for any $\alpha\in S_0$. In modern parlance, the nonstationary ideal is normal.

Proof

We can assume that $0\notin S$ (by removing 0, if necessary). If Fodor's lemma is false, for every α < κ there is some club set C_α such that $C_\alpha\cap f^{-1}(\alpha)=\emptyset$. Let C = Δ_{α < κ}C_α. The club sets are closed under diagonal intersection, so C is also club and therefore there is some $\alpha\in S\cap C$. Then $\alpha\in C_\beta$ for each β < α, and so there can be no β < α such that $\alpha\in f^{-1}(\beta)$, so $f(\alpha)\geq\alpha$, a contradiction.

The lemma was first proved by the Hungarian set theorist, Géza Fodor in 1956. It is sometimes also called "The Pressing Down Lemma".

Fodor's lemma also holds for Thomas Jech's notion of stationary sets as well as for the general notion of stationary set.

References

• G. Fodor, Eine Bemerkung zur Theorie der regressiven Funktionen, Acta Sci. Math. Szeged, 17(1956), 139-142.
• Karel Hrbacek & Thomas Jech, Introduction to Set Theory, 3rd edition, Chapter 11, Section 3.
• Mark Howard, Applications of Fodor's Lemma to Vaught's Conjecture. Ann. Pure and Appl. Logic 42(1): 1-19 (1989).
• Simon Thomas, The Automorphism Tower Problem. PostScript file at [1]

This article incorporates material from Fodor's lemma on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.