Fodor's Theorem (Pressing-Down Lemma)

Fodor's theorem is a fundamental result about regressive functions on stationary sets, with wide applications in combinatorial set theory and the study of cardinal arithmetic.

Statement

Theorem7.3Fodor's theorem

Let $\kappa$ be a regular uncountable cardinal and $S \subseteq \kappa$ a stationary set. If $f: S \to \kappa$ is regressive (i.e., $f(\alpha) < \alpha$ for all $\alpha \in S \setminus \{0\}$ ), then there exists $\gamma < \kappa$ such that $f^{-1}(\gamma) = \{\alpha \in S : f(\alpha) = \gamma\}$ is stationary.

Proof

Suppose for contradiction that for every $\gamma < \kappa$ , the set $f^{-1}(\gamma)$ is nonstationary. Then for each $\gamma$ , there exists a club $C_\gamma \subseteq \kappa$ with $C_\gamma \cap f^{-1}(\gamma) = \emptyset$ .

Define $C = \Delta_{\gamma < \kappa} C_\gamma$ , the diagonal intersection:

$C = \{\alpha < \kappa : \alpha \in C_\gamma \text{ for all } \gamma < \alpha\}.$

Claim: $C$ is a club set. Closedness: if $\alpha$ is a limit point of $C$ and $\gamma < \alpha$ , then there are cofinally many $\beta < \alpha$ in $C$ , each satisfying $\beta \in C_\gamma$ (since $\gamma < \beta$ ). So $\alpha$ is a limit point of $C_\gamma$ , hence $\alpha \in C_\gamma$ . This holds for all $\gamma < \alpha$ , so $\alpha \in C$ . Unboundedness: given $\alpha_0 < \kappa$ , define $\alpha_{n+1} = \min(C_{\alpha_n} \setminus \alpha_n)$ (using that each $C_\gamma$ is unbounded). Then $\alpha^* = \sup_n \alpha_n$ satisfies $\alpha^* \in C_\gamma$ for all $\gamma < \alpha^*$ (since for large enough $n$ , $\gamma < \alpha_n$ so $\alpha^* \in C_\gamma$ ).

Since $S$ is stationary, pick $\alpha \in S \cap C$ . Then $f(\alpha) < \alpha$ (regressive), so $\alpha \in C_{f(\alpha)}$ (since $\alpha \in C$ means $\alpha \in C_\gamma$ for all $\gamma < \alpha$ , and $f(\alpha) < \alpha$ ). But $\alpha \in f^{-1}(f(\alpha)) \cap C_{f(\alpha)} = \emptyset$ by choice of $C_{f(\alpha)}$ . Contradiction. $\blacksquare$

■

Applications

ExampleConsequences of Fodor's theorem

Club-guessing: Fodor's theorem is the key tool in Shelah's club-guessing principles, which serve as weak forms of the diamond principle.
Singular cardinal hypothesis at successors: Arguments involving Fodor's theorem on $S^{\aleph_2}_{\omega}$ help establish bounds on $2^{\aleph_1}$ under certain hypotheses.
Non-reflecting stationary sets: Fodor's theorem implies that if $S$ is stationary in $\omega_2$ and every point of $S$ has cofinality $\omega$ , then the "pressing-down" structure of functions on $S$ is highly constrained.

RemarkThe diagonal intersection

The diagonal intersection $\Delta_\gamma C_\gamma = \{\alpha : \alpha \in \bigcap_{\gamma < \alpha} C_\gamma\}$ is the key technical device in the proof. It is the dual operation to the diagonal union $\nabla_\gamma S_\gamma = \{\alpha : \alpha \in S_\gamma \text{ for some } \gamma < \alpha\}$ . The club filter on a regular cardinal is closed under diagonal intersections, making it a normal filter. This normality is equivalent to Fodor's theorem.