Fodor's lemma

From Wikipedia, the free encyclopedia

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

If κ is a regular, uncountable cardinal, S is a stationary subset of κ, and f:\kappa\rightarrow\kappa is regressive on S (that is, f(α) < α for any \alpha\in S, \alpha\neq 0) then there is some γ and some stationary S_0\subseteq S such that f(α) = γ for any \alpha\in S_0. In modern parlance, the nonstationary ideal is normal.

A proof of Fodor's lemma is as follows:

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

Then if Fodor's lemma is false, for every \alpha\in S there is some club set Cα such that C_\alpha\cap f^{-1}(\alpha)=\emptyset. Let C = Δα < κCα. 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 β < α, and so there can be no β < α such that \alpha\in f^{-1}(\beta), so f(\alpha)\geq\alpha, a contradiction.

The lemma was first proved by the Hungarian set theorist, Géza Fodor in 1952.

[edit] 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.