Théorème de Knaster-Tarski
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
Le théorème de Knaster-Tarski est un théorème de point fixe pour une application monotone d'un treillis complet dans lui-même ; aussi est-il encore appelé théorème de point fixe de Knaster-Tarski ou tout 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, dans son livre de théorie axiomatique 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 (on verra d'ailleurs des affaiblissements des hypothèses en cours de route) 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, ou décroissante, de T dans lui-même, alors l'ensemble des points fixes de N dans T 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, donnée ci-dessous, aussi mais non constructive ; nous allons aussi esquisser une démonstration par récurrence transfinie, nettement plus informative. Ces démonstrations sont présentées surtout parce qu'elles se prêtent à des commentaires intéressants dans une encyclopédie.
Sommaire |
[modifier] Démonstration par l'extérieur
[modifier] Démonstration par l'intérieur
[modifier] Fausses ou vraies applications
[modifier] En théorie du potentiel
[modifier] En économie mathématique
[modifier] En informatique
Les principaux domaines d'applications sont la sémantique des langages de programmation et l'analyse de programme, domaines qui se recouvrent fortement.
[modifier] Le théorème de Moschovakis
[modifier] Bibliographie
- Alfred Tarski : A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, vol. 5 (1955), pp 285-309. http://projecteuclid.org/Dienst/UI/1.0/Journal?authority=euclid.pjm&issue=1103044526
- Yiannis N. Moschovakis : Notes on Set Theory, Springer 1994
