Fodor's lemma

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

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

Another related statement, also known as Fodor's lemma (or Pressing-Down-lemma), is the following:

For every non-special tree ${\displaystyle T}$ and regressive mapping ${\displaystyle f:T\rightarrow T}$ (that is, ${\displaystyle f(t)<t}$, with respect to the order on ${\displaystyle T}$, for every ${\displaystyle t\in T}$), there is a non-special subtree ${\displaystyle S\subset T}$ on which ${\displaystyle f}$ is constant.

• 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
• S. Todorcevic, Combinatorial dichotomies in set theory. pdf at

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