---
tag: 55W1M20Q3F
kind: statement
role: lemma
name: Fodor's lemma
msc: ["03E05", "03E10"]
uses: [6FDYJVG1CK, GWS5QXH7WW, ZCE333FAWC, 0XHDTE5YMZ]
about: [YE6WZR46RQ]
sources:
  - url: https://en.wikipedia.org/wiki/Fodor's_lemma
same_as:
  wikidata: Q1119050
  wikipedia: Fodor's lemma
---

## Statement

Let $\kappa$ be an uncountable [[regular cardinal|ZCE333FAWC]].
Let $S \subseteq \kappa$ be [[stationary|6FDYJVG1CK]] with $0 \notin S$.
Let $f \colon S \to \kappa$ be a [[function|0XHDTE5YMZ]] that is regressive, that is, $f(\alpha) < \alpha$ for each $\alpha \in S$.
Then there is $\gamma < \kappa$ such that the set $\set{\alpha \in S : f(\alpha) = \gamma}$ is stationary in $\kappa$.

## Remarks

The proof is by contradiction.
If each fibre $f^{-1}(\gamma)$ is nonstationary, pick a [[club set|GWS5QXH7WW]] $C_\gamma$ disjoint from it.
The diagonal intersection $D = \set{\alpha < \kappa : \alpha \in \bigcap_{\gamma < \alpha} C_\gamma}$ is club, so it meets $S$ in some ordinal $\alpha$.
Then $\gamma = f(\alpha) < \alpha$ gives $\alpha \in C_\gamma$, which contradicts $f(\alpha) = \gamma$.
Example: on the limit ordinals below $\omega_1$, any function with $f(\alpha) < \alpha$ is constant on a stationary set.
Stationarity is necessary: on the successor ordinals, $f(\beta + 1) = \beta$ is regressive and injective, so all its fibres have one element.
The lemma is also called the pressing-down lemma.

## Explanations

### L1 human

Suppose that to each point of a large set of countable ordinals you assign a smaller ordinal.
Fodor's lemma says that you must then assign the same value to a large set of points.
You cannot keep pushing every point down to a different place.
"Large" here means stationary, the right notion of size for these sets.

### L2 human

Fodor's lemma is the basic tool for working with stationary sets.
It is the infinite analogue of the pigeonhole principle for regressive functions, and it relies on closure of the club filter under diagonal intersections.
It is used in Solovay's splitting theorem for stationary sets and in Silver's theorem on singular cardinals.