Théorème de Knaster-Tarski

Bronisław Knaster (1893-1980).

Alfred Tarski (1901-1983).

Knaster et Tarski, deux mathématiciens amis en Pologne, ont proposé la première version du théorème en 1928[1]. Le théorème de Knaster-Tarski est aussi appelé simplement théorème de point fixe de Tarski, le théorème ayant été publié par Tarski dans sa forme générale en 1955[2]. En 1955, Anne C. Davis montre une sorte de réciproque[3].

En fait, Moschovakis, dans son livre de théorie des ensembles cité dans la bibliographie, fait remonter ce type de théorème de point fixe à la démonstration par Zermelo de son théorème éponyme, et ne nomme à ce sujet aucun autre mathématicien, sans doute pour éviter la loi de Stigler.

L'énoncé de Knaster-Tarski n'est pas le plus puissant du genre mais il est relativement simple :

Si ${\displaystyle T}$ est un treillis complet et ${\displaystyle f:T\to T}$ une application croissante, alors le sous-ensemble ordonné des points fixes de ${\displaystyle f}$ est un treillis complet (donc non vide).

En particulier, ${\displaystyle f}$ a un plus petit et un plus grand point fixe.

La démonstration usuelle est non constructive:

Soit ${\displaystyle F}$ l'ensemble des points fixes de ${\displaystyle f}$. Montrons que dans ${\displaystyle F}$, toute partie ${\displaystyle G}$ possède une borne supérieure. Pour cela, notons ${\displaystyle m}$ la borne inférieure de l'ensemble ${\displaystyle S:=\{x\in T\mid x\geq G\quad {\text{et}}\quad f(x)\leq x\}}$. Alors :

• ${\displaystyle m\geq G}$ (car ${\displaystyle S\geq G}$) ;
• ${\displaystyle f(m)\leq m}$. En effet, ${\displaystyle f(m)\leq S}$ car pour tout ${\displaystyle x\in S}$, d'une part ${\displaystyle f(m)\leq f(x)}$ (car ${\displaystyle m\leq x}$) et d'autre part ${\displaystyle f(x)\leq x}$ ;
• ${\displaystyle f(m)\geq m}$. En effet, ${\displaystyle f(m)\in S}$ car (d'après les deux points précédents) ${\displaystyle f(m)\geq f(G)=G}$ et ${\displaystyle f(f(m))\leq f(m)}$ ;
• tout point fixe de ${\displaystyle f}$ qui majore ${\displaystyle G}$ appartient à ${\displaystyle S}$ donc est minoré par ${\displaystyle m}$.

Par conséquent, ${\displaystyle m}$ est la borne supérieure de ${\displaystyle G}$ dans ${\displaystyle F}$.

Une seconde démonstration, d'un théorème plus faible, est la suivante : on démontre par récurrence transfinie que ${\displaystyle f}$ a un point fixe.

On pose ${\displaystyle x_{0}=}$ le plus petit élément de ${\displaystyle T}$, puis on construit une « fonction » ${\displaystyle x}$ par récursion transfinie comme suit : si ${\displaystyle \alpha }$ est un ordinal quelconque, ${\displaystyle x_{\alpha +1}:=f(x_{\alpha })}$, et si ${\displaystyle \alpha }$ est un ordinal limite, ${\displaystyle x_{\alpha }}$ est la borne supérieure de ${\displaystyle \{x_{\beta }\mid \beta <\alpha \}}$. D'après le choix de ${\displaystyle x_{0}}$ et la croissance de ${\displaystyle f}$, ${\displaystyle \alpha \mapsto x_{\alpha }}$ est croissante. En choisissant un ordinal qui ne s'injecte pas dans ${\displaystyle T}$ (par exemple son ordinal de Hartogs), on voit que ${\displaystyle \alpha \mapsto x_{\alpha }}$ ne peut pas être injective et donc il existe ${\displaystyle \gamma <\beta }$ tels que ${\displaystyle x_{\gamma }=x_{\beta }}$. Par croissance de ${\displaystyle \alpha \mapsto x_{\alpha }}$, ${\displaystyle x_{\gamma }\leq x_{\gamma +1}\leq x_{\beta }=x_{\gamma }}$ donc ${\displaystyle x_{\gamma }=x_{\gamma +1}=f(x_{\gamma })}$ : on a trouvé un point fixe.

• (en) Charalambos D. Aliprantis et Kim C. Border, Infinite Dimensional Analysis : A Hitchhiker's Guide, Springer, 2007, 3^e éd. (lire en ligne), p. 17-18
• (en) Alfred Tarski, « A lattice-theoretical fixpoint theorem and its applications », Pacific J. Math., vol. 5, n^o 2,‎ 1955, p. 285-309 (lire en ligne)
• (en) Yiannis N. Moschovakis, Notes on Set Theory, Springer, 1994 (lire en ligne)
• B. Knaster, « Un théorème sur les fonctions d'ensembles », Ann. Soc. Polon. Math., vol. 6,‎ 1928, p. 133-134 (lire en ligne) — Knaster expose des résultats obtenus avec Tarski.