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\to \kappa$ régressive (c'est-à-dire $f(\alpha )<\alpha$ pour toute $\alpha \in S$, $\alpha \ne 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 )=\mathrm{\varnothing }$ . Soit $C={\mathrm{\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 )\ge \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\to T$, il existe un sous-arbre non-spécial $S\subset T$ sur lequel $f$ est constante.

Références

• 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]