Théorème du point fixe de Kleene

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Théorème de Kleene ni Théorème de récursion de Kleene.

En mathématiques, dans le domaine de la théorie des ordres, le théorème du point fixe de Kleene, s'énonce comme suit :

Soient L un ordre partiel complet, 0 son élément minimum, et f:L\to L une application continue au sens de Scott (en). Alors le plus petit point fixe de f est le sup de la suite croissante suivante :
0\le f(0)\le f^2(0)\le\ldots\le f^n(0)\le\ldots~.

C'est donc un analogue, pour les ordres partiels complets, du théorème de Knaster-Tarski qui, lui, concerne les treillis complets.

Précisons les deux hypothèses de cet énoncé :

  • Un ordre partiel complet est un ensemble partiellement ordonné qui possède un élément minimum, et dont toutes les chaînes ont une borne supérieure.
  • f est continue au sens de Scott si c'est une fonction croissante qui de plus préserve les sup de chaînes. (Le fait qu'elle soit croissante assure a priori qu'elle a un plus petit point fixe, et que la suite ci-dessus est croissante.)