Théorème de Knaster-Tarski

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

Énoncé[modifier | modifier le code]

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

Si est un treillis complet et une application croissante, alors le sous-ensemble ordonné des points fixes de est un treillis complet (donc non vide).

En particulier, a un plus petit et un plus grand point fixe.

Démonstrations[modifier | modifier le code]

La démonstration usuelle[réf. nécessaire] est non constructive[réf. nécessaire]:

Soit l'ensemble des points fixes de . Montrons que dans , toute partie possède une borne supérieure. Pour cela, notons la borne inférieure de l'ensemble . Alors :

  •  ;
  • . En effet, car pour tout , d'une part (car ) et d'autre part  ;
  • . En effet, car (d'après les deux points précédents) et  ;
  • tout point fixe de qui majore appartient à donc est minoré par .

Par conséquent, est la borne supérieure de dans .

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

On pose le plus petit élément de , puis on construit une « fonction » par récursion transfinie comme suit : si est un ordinal quelconque, , et si est un ordinal limite, est la borne supérieure de . D'après le choix de et la croissance de , est croissante. En choisissant un ordinal qui ne s'injecte pas dans (par exemple son ordinal de Hartogs), on voit que ne peut pas être injective et donc il existe tels que . Par croissance de , donc  : on a trouvé un point fixe.

Histoire[modifier | modifier le code]

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 bien après, semble-t-il, sa conception par ces deux mathématiciens amis en Pologne. En fait, Moschovakis (en), 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.

Applications[modifier | modifier le code]

En mathématiques[modifier | modifier le code]

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[modifier | modifier le code]

Les principaux domaines d'applications sont la sémantique des langages de programmation et l'analyse de programme (en) par interprétation abstraite ou model checking, domaines qui se recouvrent fortement.

Bibliographie[modifier | modifier le code]

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