# Fodor's lemma

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

If ${\displaystyle \kappa }$ is a regular, uncountable cardinal, ${\displaystyle S}$ is a stationary subset of ${\displaystyle \kappa }$, and ${\displaystyle f:S\rightarrow \kappa }$ is regressive (that is, ${\displaystyle f(\alpha )<\alpha }$ for any ${\displaystyle \alpha \in S}$, ${\displaystyle \alpha \neq 0}$) then there is some ${\displaystyle \gamma }$ and some stationary ${\displaystyle S_{0}\subseteq S}$ such that ${\displaystyle f(\alpha )=\gamma }$ for any ${\displaystyle \alpha \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. It is sometimes also called "The Pressing Down Lemma".

## Proof

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.

## Fodor's lemma for trees

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), 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.

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