Théorème de Knaster-Tarski

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Bronisław Knaster
Alfred Tarski

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 ; aussi est-il encore appelé théorème de point fixe de Knaster-Tarski ou simplement 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. L'énoncé de Knaster-Tarski n'est sans doute pas le plus puissant du genre mais a le mérite d'être immédiatement attrayant pour toute personne utilisant des structures d'ordre. Le voici :

Si T est un treillis complet et N une application croissante de T dans lui-même, alors l'ensemble des points fixes de N dans T est non vide, et c'est lui-même un treillis complet. En particulier, N a un plus petit et un plus grand point fixe dans T.

L'énoncé est simple, la démonstration usuelle aussi mais non constructive. Il existe une démonstration par récurrence transfinie, plus informative.

Démonstrations[modifier | modifier le code]

Fausses ou vraies applications[modifier | modifier le code]

En mathématiques[modifier | modifier le code]

On peut démontrer le théorème de Cantor-Bernstein (ou Schröder-Bernstein) en appliquant 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) Alfred Tarski, « A lattice-theoretical fixpoint theorem and its applications », Pacific J. Math. (en), vol. 5, no 2,‎ 1955, p. 285-309 (lire en ligne)
  • (en) Yiannis N. Moschovakis, Notes on Set Theory, Springer, 1994