Voir la source de Théorème de Knaster-Tarski

{{ébauche|mathématiques}}
Le '''théorème de Knaster-Tarski''' est un [[Théorèmes de point fixe|théorème de point fixe]] pour une [[Relation d'ordre#Applications croissantes|application croissante]] d'un [[Treillis (ensemble ordonné)#Treillis complet|treillis complet]] dans lui-même. Il est nommé d'après [[Bronisław Knaster|Bronislaw Knaster]] et [[Alfred Tarski]].

== Histoire ==
[[Fichier:Bronislaw Knaster.jpeg|vignette|gauche|[[Bronisław Knaster]] ([[1893 en science|1893]]-[[1980 en science|1980]]).]][[Fichier:AlfredTarski1968.jpeg|droite|vignette|[[Alfred Tarski]] ([[1901 en science|1901]]-[[1983 en science|1983]]).]]
Knaster et Tarski, deux [[mathématicien]]s amis en [[Pologne]], ont proposé la première version du théorème en 1928<ref>{{article|langue=en| auteur=B. Knaster | titre=Un théorème sur les fonctions d'ensembles | journal=Ann. Soc. Polon. Math. | année=1928 | volume=6 | pages=133–134}} With A. Tarski.</ref>. Le [[théorème]] de [[Bronisław Knaster|Knaster]]-[[Alfred Tarski|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<ref>{{article|langue=en| auteur=Alfred Tarski | url=http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103044538 | titre=A lattice-theoretical fixpoint theorem and its applications | journal = Pacific Journal of Mathematics | volume=5:2 | année=1955 | pages=285–309}}</ref>. En 1955, Anne C. Davis montre une sorte de réciproque<ref>{{article|langue=en| auteur=Anne C. Davis | url=http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103044539 | titre=A characterization of complete lattices | journal=Pacific J. Math. | année=1955 | volume=5 | pages=311–319 | doi=10.2140/pjm.1955.5.311}}</ref>.

En fait, [[Yiannis N. Moschovakis|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 [[Ernst Zermelo|Zermelo]] de son [[théorème de Zermelo|théorème éponyme]], et ne nomme à ce sujet aucun autre mathématicien, sans doute pour éviter la [[loi de Stigler]].

{{clr}}

== Énoncé ==
L'énoncé de Knaster-Tarski n'est pas le plus puissant du genre{{C'est-à-dire||date=18 03 2017}} mais il est relativement simple :
{{énoncé|Si <math>T</math> est un treillis complet et <math>f:T\to T</math> une application croissante, alors le sous-ensemble ordonné des [[Point fixe|points fixes]] de <math>f</math> est un treillis complet (donc non vide).

En particulier, <math>f</math> a un plus petit et un plus grand point fixe.}}

== Démonstrations ==
La démonstration {{refnec|date=novembre 2016|usuelle}} est {{refnec|date=octobre 2016|non [[Démonstration constructive|constructive]]}}:

Soit <math>F</math> l'ensemble des points fixes de <math>f</math>. Montrons que dans <math>F</math>, toute partie <math>G</math> possède une [[borne supérieure]]. Pour cela, notons <math>m</math> la borne inférieure de l'ensemble <math>S:=\{x\in T\mid x\ge G\quad\text{et}\quad f(x)\le x\}</math>. Alors :
* <math>m\ge G</math> (car <math>S\ge G</math>) ;
* <math>f(m)\le m</math>. En effet, <math>f(m)\le S</math> car pour tout <math>x\in S</math>, d'une part <math>f(m)\le f(x)</math> (car <math>m\le x</math>) et d'autre part <math>f(x)\le x</math> ;
* <math>f(m)\ge m</math>. En effet, <math>f(m)\in S</math> car (d'après les deux points précédents) <math>f(m)\ge f(G)=G</math> et <math>f(f(m))\le f(m)</math> ;
* tout point fixe de <math>f</math> qui majore <math>G</math> appartient à <math>S</math> donc est minoré par <math>m</math>.
Par conséquent, <math>m</math> est la borne supérieure de <math>G</math> dans <math>F</math>.

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

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

== Applications ==
<!--Vraies ou fausses applications-->
=== En mathématiques ===
On peut démontrer le [[théorème de Cantor-Bernstein]] en appliquant celui de Knaster-Tarski : voir le § « [[Théorème de Cantor-Bernstein#Deuxième démonstration|Deuxième démonstration]] » de l'article sur ce théorème.
<!--=== En théorie du potentiel ===
=== En économie mathématique ===-->

=== En informatique ===
Les principaux domaines d'applications sont la [[sémantique des langages de programmation]] et l'{{Lien|langue=en|trad=Program analysis (computer science)|fr=analyse de programme}} par [[interprétation abstraite]] ou [[model checking]], domaines qui se recouvrent fortement.
<!--
== Le théorème de Moschovakis ==
-->
== Notes et références ==
{{Références}}

== Bibliographie ==
* {{Ouvrage|langue=en|auteur1=[[Charalambos D. Aliprantis]]|auteur2=Kim C. Border|titre=Infinite Dimensional Analysis|sous-titre=A Hitchhiker's Guide|éditeur=[[Springer Verlag|Springer]]|année=2007|numéro d'édition=3|passage=17-18|isbn=|lire en ligne={{Google Livres|4hIq6ExH7NoC|page=17}}}}
* {{article|lang=en|prénom=Alfred|nom=Tarski|url=http://projecteuclid.org/Dienst/UI/1.0/Journal?authority=euclid.pjm&issue=1103044526|titre=A lattice-theoretical fixpoint theorem and its applications|revue=[[Liste des journaux scientifiques en mathématiques|Pacific J. Math.]]|volume=5|numéro=2|année=1955|p.=285-309}}
* {{Ouvrage|langue=en|auteur1=Yiannis N. Moschovakis|titre=Notes on Set Theory|éditeur=Springer|année=1994|isbn=|lire en ligne={{Google Livres|ndx0_6VCypcC|page=100}}}}
* {{article| auteur=B. Knaster | titre=Un théorème sur les fonctions d'ensembles | journal=Ann. Soc. Polon. Math. | année=1928 | volume=6 | pages=133-134 | url = http://cybra.lodz.pl/Content/6198/AnnSocPolMathe_t.VI_1927.pdf }}{{Commentaire biblio SRL|Knaster expose des résultats obtenus avec Tarski.}}

{{Portail|mathématiques}}

[[Catégorie:Théorème de mathématiques|Knaster]]
[[Catégorie:Théorie des ordres]]