Lemme de Fodor

En mathématiques, et plus particulièrement en théorie des ensembles, le lemme de Fodor énonce ce qui suit :

Si $\kappa$ est un cardinal régulier, indénombrable, $S$ est un sous-ensemble stationnaire de $\kappa$, et $f:S\rightarrow \kappa$ régressive (c'est-à-dire $f(\alpha )<\alpha$ pour toute $\alpha \in S$, $\alpha \neq 0$) alors il existe $\gamma$ et $S_{0}\subseteq S$ stationnaire tel que $f(\alpha )=\gamma$ pour tout $\alpha \in S_{0}$. On dit que l'idéal non stationnaire est normal.

Le lemme a été prouvé pour la première fois par le théoricien hongrois des ensembles, Géza Fodor en 1956.

Démonstration

Nous pouvons supposer que $0\notin S$ (en supprimant 0, si nécessaire). Si le lemme de Fodor est faux, pour tout $\alpha <\kappa$ il y a un club $C_{\alpha }$ tel que $C_{\alpha }\cap f^{-1}(\alpha )=\emptyset$ . Soit $C=\Delta _{\alpha <\kappa }C_{\alpha }$ . Les ensembles de clubs étant fermés sous intersection diagonale, $C$ est aussi club. Il existe donc $\alpha \in S\cap C$. Alors $\alpha \in C_{\beta }$ pour chaque $\beta <\alpha$, et donc il ne peut y avoir $\beta <\alpha$ tel que $\alpha \in f^{-1}(\beta )$, alors $f(\alpha )\geq \alpha$, une contradiction.

Lemme de Fodor pour les arbres

Une autre formulation du lemme de Fodor (ou Pressing-Down-lemma), est la suivante :

Pour tout arbre non spécial $T$ et une application régressive $f:T\rightarrow T$, il existe un sous-arbre non-spécial $S\subset T$ sur lequel $f$ est constante.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fodor's lemma » (voir la liste des auteurs).

• G. Fodor, Eine Bemerkung zur Theorie der regressiven Funktionen, Acta Sci. Math. Szeged , 17 (1956), 139-142 [1].
• Karel Hrbacek & Thomas Jech, Introduction à la théorie des ensembles, 3e édition, chapitre 11, section 3.
• Mark Howard, Applications du lemme de Fodor à la conjecture de Vaught . Ann. Pur et Appl. Logique 42(1): 1-19 (1989).
• Simon Thomas, Le problème de la tour d'automorphisme . Fichier PostScript à [2]
• S. Todorcevic, Dichotomies combinatoires en théorie des ensembles . pdf à [3]