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 vignette|gauche|Bronisław Knaster (1893-1980).droite|vignette|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 With A. Tarski.. 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 genre mais il est relativement simple :

Démonstrations La démonstration est :

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

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' par interprétation abstraite ou model checking, domaines qui se recouvrent fortement.

Notes et références

Bibliographie

Knaster Catégorie:Théorie des ordres