Fodor's lemma explained
In mathematics, particularly in set theory, Fodor's lemma states the following:
If
is a
regular,
uncountable cardinal,
is a
stationary subset of
, and
is regressive (that is,
for any
,
) then there is some
and some stationary
such that
for any
. In modern parlance, the nonstationary ideal is
normal.
The lemma was first proved by the Hungarian set theorist, Géza Fodor in 1956. It is sometimes also called "The Pressing Down Lemma".
Proof
We can assume that
(by removing 0, if necessary).If Fodor's lemma is false, for every
there is some
club set
such that
C\alpha\capf-1(\alpha)=\emptyset
. Let
C=\Delta\alpha<\kappaC\alpha
. The club sets are closed under
diagonal intersection, so
is also club and therefore there is some
. Then
for each
, and so there can be no
such that
, so
, a
contradiction.
Fodor's lemma also holds for Thomas Jech's notion of stationary sets as well as for the general notion of stationary set.
Fodor's lemma for trees
Another related statement, also known as Fodor's lemma (or Pressing-Down-lemma), is the following:
For every non-special tree
and regressive mapping
(that is,
, with respect to the order on
, for every
,
), there is a non-special subtree
on which
is constant.
References
- G. Fodor, Eine Bemerkung zur Theorie der regressiven Funktionen, Acta Sci. Math. Szeged, 17(1956), 139-142 http://pub.acta.hu/acta/showCustomerArticle.action?id=6490&dataObjectType=article&returnAction=showCustomerVolume&sessionDataSetId=6b37d83ce0bc926e&style=.
- 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
- S. Todorcevic, Combinatorial dichotomies in set theory. pdf at http://www.math.toronto.edu/~stevo/dichotomies4.pdf