Fodor's lemma

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

If <math>\kappa<math> is a regular, uncountable cardinal, <math>S<math> is a stationary subset of <math>\kappa<math>, and <math>f:\kappa\rightarrow\kappa<math> is regressive on <math>S<math> (that is, <math>f(\alpha)<\alpha<math> for any <math>\alpha\in S<math>) then there is some <math>\gamma<math> and some stationary <math>S_0\subseteq S<math> such that <math>f(\alpha)=\gamma<math> for any <math>\alpha\in S_0<math>.

A proof of Fodor's lemma is as follows:

If we let <math>f^{-1}:\kappa\rightarrow P(S)<math> be the inverse of <math>f<math> restricted to <math>S<math> then Fodor's lemma is equivalent to the claim that for any function such that <math>\alpha\in f(\kappa)\rightarrow \alpha>\kappa<math> there is some <math>\alpha\in S<math> such that <math>f^{-1}(\alpha)<math> is stationary.

Then if Fodor's lemma is false, for every <math>\alpha\in S<math> there is some club set <math>C_\alpha<math> such that <math>C_\alpha\cap f^{-1}(\alpha)=\emptyset<math>. Let <math>C=\Delta_{\alpha<\kappa} C_\alpha<math>. The club sets are closed under diagonal intersection, so <math>C<math> is also club and therefore there is some <math>\alpha\in S\cap C<math>. Then <math>\alpha\in C_\beta<math> for each <math>\beta<\alpha<math>, and so there can be no <math>\beta<\alpha<math> such that <math>\alpha\in f^{-1}(\beta)<math>, so <math>f(\alpha)\geq\alpha<math>, a contradiction.

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 [1]

This article incorporates material from Fodor's lemma on PlanetMath, which is licensed under the GFDL.