Aller au contenu

Théorème de Knaster-Tarski

Un article de Wikipédia, l'encyclopédie libre.

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.

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[C'est-à-dire ?] 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 :

  • (car ) ;
  • . 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.

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.

Notes et références

[modifier | modifier le code]
  1. (en) B. Knaster, « Un théorème sur les fonctions d'ensembles », Ann. Soc. Polon. Math., vol. 6,‎ , p. 133–134 With A. Tarski.
  2. (en) Alfred Tarski, « A lattice-theoretical fixpoint theorem and its applications », Pacific Journal of Mathematics, vol. 5:2,‎ , p. 285–309 (lire en ligne)
  3. (en) Anne C. Davis, « A characterization of complete lattices », Pacific J. Math., vol. 5,‎ , p. 311–319 (DOI 10.2140/pjm.1955.5.311, lire en ligne)

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.