Théorème 1Structures d'ordre

Théorème du point fixe de Knaster-Tarski

Énoncé

Soit $E$ un treillis complet et $\varphi : E \to E$ une application croissante. Alors $\varphi$ a un plus grand point fixe, qui est $\sup\{x \in E : x \leqslant \varphi(x)\}$ , et un plus petit point fixe.

Démonstration

Soit $S = \{x \in E : x \leqslant \varphi(x)\}$ et $s = \sup S$ . Pour $x \in S$ , on a $x \leqslant s$ , donc, par croissance, $x \leqslant \varphi(x) \leqslant \varphi(s) :$ $\varphi(s)$ majore $S$ , d'où $s \leqslant \varphi(s)$ .

Par croissance encore, $\varphi(s) \leqslant \varphi(\varphi(s))$ , donc $\varphi(s) \in S$ et $\varphi(s) \leqslant s$ . Ainsi $\varphi(s) = s$ . Tout point fixe $p$ appartient à $S$ , donc $p \leqslant s$ .

Ici

E = \mathcal P(A)

avec

A = \{a, b, c\}

, et

\varphi(X) = \{a\} \cup (X \cap \{b\})

, qui est croissante. Les flèches vertes vont de

X

\varphi(X)

lorsque

X

n'est pas fixe, et les deux points fixes

\{a\}

\{a, b\}

sont entourés. La zone bleue est

S = \{X : X \subset \varphi(X)\}

; sa borne supérieure

s = \{a, b\}

, en rouge, est le plus grand point fixe.

Le plus petit point fixe s'obtient en appliquant ce résultat à l'ordre opposé, qui fait encore de $E$ un treillis complet (Treillis complets) et de $\varphi$ une application croissante.

□

Remarque

La démonstration du théorème de Cantor-Bernstein en est le cas particulier où $E = {\mathcal P}(A)$ . C'est l'ordre qui fait le travail, et non une énumération : aucun entier n'intervient.

Remarque

En logique et en informatique, ce théorème justifie les définitions « par le plus petit ensemble stable » : par exemple, l'ensemble des formules d'un langage est le plus petit point fixe d'une opération de construction (Formules).

Repose sur

Treillis et treillis complets Applications croissantes, isomorphismes d'ordres

Sert à

Aucune fiche de ce graphe ne l'utilise encore.