Théorème de Knaster-Tarski

Modèle:Ébauche Le théorème de Knaster-Tarski est un théorème de point fixe pour une application croissante d'un treillis complet dans lui-même. Il est nommé d'après Bronislaw Knaster et Alfred Tarski.

Histoire

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. 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. En 1955, Anne C. Davis montre une sorte de réciproque.

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.

Énoncé

L'énoncé de Knaster-Tarski n'est pas le plus puissant du genreModèle:C'est-à-dire mais il est relativement simple : Modèle:Énoncé

Démonstrations

La démonstration Modèle:Refnec est Modèle:Refnec:

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

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

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

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

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

Applications

En mathématiques

On peut démontrer le théorème de Cantor-Bernstein en appliquant celui de Knaster-Tarski : voir le § « Deuxième démonstration » de l'article sur ce théorème.

En informatique

Les principaux domaines d'applications sont la sémantique des langages de programmation et l'Modèle:Lien par interprétation abstraite ou model checking, domaines qui se recouvrent fortement.

Bibliographie

• Modèle:Ouvrage
• Modèle:Article
• Modèle:Ouvrage
• Modèle:ArticleModèle:Commentaire biblio SRL