fodor's lemma

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

\kappa

S

\kappa

, and

f:\kappa\rightarrow\kappa

is regressive on

S

(that is,

f(\alpha)<\alpha

for any

\alpha\in S

) then there is some

\gamma

and some stationary

S_0\subseteq S

such that

f(\alpha)=\gamma

for any

\alpha\in S_0

. A proof of Fodor's lemma is as follows: If we let

f^{-1}:\kappa\rightarrow P(S)

be the inverse of

f

S

then Fodor's lemma is equivalent to the claim that for any function such that

\alpha\in f(\kappa)\rightarrow \alpha>\kappa

there is some

\alpha\in S

such that

f^{-1}(\alpha)

is stationary. Then if Fodor's lemma is false, for every

\alpha\in S

there is some club set

C_\alpha

such that

C_\alpha\cap f^{-1}(\alpha)=\emptyset

. Let

C=\Delta_{\alpha<\kappa} C_\alpha

. The club sets are closed under diagonal intersection, so

C

is also club and therefore there is some

\alpha\in S\cap C

. Then

\alpha\in C_\beta

for each

\beta<\alpha

, and so there can be no

\beta<\alpha

such that

\alpha\in f^{-1}(\beta)

, so

f(\alpha)\geq\alpha

References

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 http://www.math.rutgers.edu/~sthomas/book.ps

Word Browser