Fodor's lemma

In mathematics, particularly in set theory, Fodor's lemma (or the pressing-down lemma) states:

Fodor's lemma—If $κ$ is a regular, uncountable cardinal, $S$ is a stationary subset of $κ$ , and $f : S \to κ$ is regressive (that is, $f (α) < α$ for any $α \in S$ , $α \neq 0$ ) then there is some $γ$ and some stationary $S_{0} \subseteq S$ such that $f (α) = γ$ for any $α \in S_{0}$ .

In modern parlance, the nonstationary ideal is normal. The lemma was first proved by the Hungarian set theorist, Géza Fodor in 1956.

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_{α} \cap f^{- 1} (α) = ∅︀$ . Let $C = Δ_{α < κ} C_{α}$ . The club sets are closed under diagonal intersection, so $C$ is also club and therefore there is some $α \in S \cap C$ . Then $α \in C_{β}$ for each $β < α$ , and so there can be no $β < α$ such that $α \in f^{- 1} (β)$ , so $f (α) \geq α$ , a contradiction.

There is a Fodor's lemma for trees:

Fodor's lemma for trees—For every non-special tree $T$ and regressive mapping $f : T \to T$ (that is, $f (t) < t$ , with respect to the order on $T$ , for every $t \in T$ , $t \neq 0$ ), there is a non-special subtree $S \subseteq T$ on which $f$ is constant.

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

References

Hrbacek, Karel; Jech, Thomas (1999). "Chapter 11, Section 3". Introduction to Set Theory, Revised and Expanded (3rd ed.). Boca Raton: CRC Press. ISBN 9780824779153.
Howard, Mark (March 1989). "Applications of Fodor's lemma to Vaught's conjecture". Annals of Pure and Applied Logic. 42 (1): 1–19. doi:10.1016/0168-0072(89)90063-8.
Preliminary version of an unpublished book: Thomas, Simon. "The Automorphism Tower Problem" (PDF). Rutgers University. Retrieved 2026-04-12.
Todorcevic, Stevo (March 2011). "Combinatorial Dichotomies in Set Theory". The Bulletin of Symbolic Logic. 17 (1): 1–72. doi:10.2178/bsl/1294186662. ISSN 1079-8986.

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

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy projective Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Constructive Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo